# Geometric Interpretation of Computation

Being from Physics, I have been trained to look into a lot of problems from a geometrical point of view. For example the differential geometry of manifolds in dynamical systems etc. When I read the foundations of computer science, I always try to find geometric interpretations. Like a plausible geometric interpretation of recursively enumerable sets (I worked on a part where I tried to connect them with Algebraic Geometry by exploiting equivalence with Diophantine Sets but the connection seemed forced and I could not find a "natural" expression of the facts in that formulation) or a beautiful geometric result for a simple algorithm for sorting numbers. Though I am not an expert I have read surveys on Geometric Complexity Theory and it is surely an interesting program but I am more interested in having a geometric view of extremely fundamental concepts like the dynamics of a Turing Machine, Lambda Calculus or the structure of (un)computable sets (rather than specific problems). Is it a hopeless job to find geometrical structure in these objects or can one expect some intricate results? Is there any formulation of TCS which treats it geometrically?

• I think the question too wordy and not very clear and needs to be improved. It seems to me that in essence you are asking a reference request question about geometric formulation and treatment of TCS. – Kaveh Sep 20 '13 at 2:33
• If you are looking for them to be able to learn computability theory then you are not going to be very lucky as these works usually are written for people who are well versed in the classic treatment of computability theory. You have to learn the new language if you want to learn computability theory. That said, there are categorical treatments of computability theory (but as I said they are written for people who know computability theory). – Kaveh Sep 20 '13 at 2:35
• @Kaveh, It would be extremely helpful if you can provide me a reference to a Categorical treatment of Computability Theory. Though as you said, it may not be understandable without a rigorous understanding of classical treatment of computability, I am trying my best to get there. – swarnim_narayan Sep 20 '13 at 4:43
• Can you clarify what you mean by geometry in the context of your question? – Martin Berger Sep 20 '13 at 13:47
• @wang, I think "reference request for computability from category theory perspective" can be a new separate question, and there are others like Andrej (e.g. see this) who can answer it much better than I can. – Kaveh Sep 21 '13 at 3:11

The semantics of computer programs can be understood geometrically in three distinct (and apparently incompatible) ways.

• The oldest approach is via domain theory. The intuition behind domain theory arises from the asymmetry behind termination and nontermination.

When treating programs extensionally (ie, only looking at their I/O behavior, and not their internal structure), it is always possible to confirm in finite time that a program halts -- you just wait until it stops. However, it's not possible to confirm that a program doesn't halt, because no matter how long you wait, there is always a halting program that will run for a few more steps than you waited.

As a result, halting and looping can be viewed as forming a topological space (the Sierpiński space). This lifts to richer notions of observation (via the Scott topology), and you can thereby interpret programs as elements of topological spaces. These spaces are generally quite surprising from a traditional point of view -- domains are generally not Hausdorff.

The best topological introduction I know to these ideas is Steve Vickers' short and extremely accessible Topology via Logic. It can be understood as a sort of warm-up for Peter Johnstone's significantly more formidable Stone Spaces.

If you are looking for online lecture notes, let me suggest Martin Escardo's Synthetic Topology of Data Types and Classical Spaces.

• Another view arises from concurrency theory. A concurrent program can be understood as having multiple valid executions (sequences of states), depending on how races are resolved. Then, the set of executions can be viewed as a space, with each possible sequence of states understood as a path through this space. Then, methods from algebraic topology and homotopy theory can be applied to derive invariants about the program execution.

Nir Shavit and Maurice Herlihy uses this idea to prove the impossibility of certain distributed algorithms, for which they won the 2004 Gödel prize. (See The Topological Structure of Asynchronous Computation.) Eric Goubault has a survey paper explaining the relevant ideas in Some Geometric Perspectives in Concurrency Theory.

• Most recently, it has been observed that the structure of the identity type in dependent type theory corresponds very closely with the notion of homotopy type in homotopy theory -- so closely, in fact, that dependent type theory can actually be seen as a sort of "synthetic homotopty theory"! (Vladimir Voevodsky has joked that he spent several years developing a new calculus for homotopy theory, only to discover that his colleagues in the CS department were already teaching it to undergraduates.)

See cody's link above to the homotopy type theory book.

Interestingly, these three views seem incompatible with each other, or at least very difficult to reconcile. Dependent type theory is a total language, so nontermination (and the Scott topology) does not arise in it. It is also confluent, so the view of computations-as-spaces doesn't arise either. Similarly, formulating concurrency in terms of domain theory has proved ferociously difficult, and a completely satisfactory account is still an open problem.

• "As a result, halting and looping can be viewed as forming a topological space (the Sierpiński space). This lifts to richer notions of observation (via the Scott topology), and you can thereby interpret programs as elements of topological spaces. " what is a good reference for this that is available online? – 1.. Sep 21 '13 at 16:10
• @JAS: I added a link to some of Martin Escardo's lecture notes on the subject. – Neel Krishnaswami Sep 24 '13 at 12:14

As it just so happens, there have been recent development in the theory of dependent types, in which a types, which traditionally represent a static invariant for a computer program, can be interpreted to be a topological space, or rather an equivalence class of such spaces (a homotopy type).

This has been the subject of intense research over the last few years, which culminated in a book.

Older work has attempted to give a description of models of computation systems, like the pure $\lambda$-calculus, in terms of certain topological spaces called domains. The Wikipedia article gives a good overview.

You are aware of GCT, but you might not be aware of Mulmuley's earlier work on showing a separation between a subset of PRAM-computations and P, which uses geometric ideas of how a computation can be viewed as carving up a space.

Many lower bounds for problems in the algebraic decision tree model reduce to reasoning about the topology of underlying spaces of solutions (Betti numbers show up as a relevant parameter).

In one sense, ALL of optimization is geometric: linear programs involve finding the lowest point of a polytope in high dimensions, SDPs are linear functions over the space of semidefinite matrices, and so on. Geometry is used heavily in the design of algorithms here.

On that theme, there's a long and deep connection between our ability to optimize certain functions on graphs and our ability to embed metric spaces in certain normed spaces. This is a vast literature now.

Finally, in recent years there's been a great deal of interest in so-called "lift-and-project" mechanisms for solving optimization problems, and these make heavy use of the underlying geometry and lifts to higher dimensional spaces: notions from algebraic geometry play an important role here.

• ".... algebraic decision tree model reduce to reasoning about the topology of underlying spaces of solutions " Is it true that many results about computations can be reduced to finding information about connected sets? Or is this result special? – 1.. Sep 21 '13 at 16:08
• @JAS: There are a handful of results that can be reduced to bounding the number of connected components, but I wouldn't say "many." In algebraic complexity the most common technique (at least in the last 10-15 years) is to bound the dimensions of various spaces of partial derivatives and related spaces. This can be viewed as finding equations that vanish on certain algebraic varieties, which is in some sense "geometric." But I still wouldn't say this covers "most" results, esp. Boolean complexity results, which use a variety of (at least seemingly-)non-geometric techniques. – Joshua Grochow Sep 21 '13 at 21:28
• @JoshuaGrochow Yah I have not seen much of topological work as much as classical AG even in partial derivatives. I was thinking about the answers to this question here cstheory.stackexchange.com/questions/5907/… when I saw this question. – 1.. Sep 21 '13 at 23:05

Computation is about information processing. The intrinsic nature of information and information processing naturally leads to topological notions (see Neel's answer about domain theory), but these are not directly of a geometric nature, as the resulting topological spaces tend not to be Hausdorff (or even $T_1$). They are "directed" in a sense, so one would have to come up with directed geometry to account for the phenomenon. And there are tricks to be played which symmetrize the situation (essentially you stand on your head).

One way to understand the relationship between information processing (also known as "computation") and geometry is that information processing is preceeds geometry. This view should be familiar from certain parts of physics. For instance in relativity theory we study both the causal structure of spacetime (its information processing) as well as its geometric structure. Many would consider the latter to be more basic than the former.

These connections have been noticed in the past and several years ago there was an effort to connect the information-theoretic aspects of computer science with relativity theory. One of the tasks people wanted to solve was: starting from the causality structure of spacetime (which is just a partial order on spacetime), reconstruct the topology of spacetime, or possibly the geometry as well. Recovering topology from a partial order is the sort of thing that domain theory is good at, so there was some success.

References:

Nielsen et al. showed that quantum computing has a geometrical interpretation. Specifically, they showed that finding a short quantum circuit to perform a target unitary $U$ is equivalent to finding a short geodesic in a particular curved geometry. See the following papers for details: http://arxiv.org/abs/quant-ph/0603161 and http://arxiv.org/abs/quant-ph/0701004

creatively interpreting your question, some possibilities other than GCT as you mention come to mind. one way is to look for undecidable problems (aka Turing completeness) which are quite ubiquitous.

• aperiodic Tiling the plane & Penrose tiling. its been proven that the question of whether there is an aperodic tiling of the plane is undecidable.

• Cellular automata which also increasingly are shown to have deep connections to physics, many related undecidable problems, proven TM complete, and they're naturally interpreted as (and converted between) TM computational tableaus.

• algorithms as Fractals. a more undeveloped (ie active/ongoing research!) area, but various undecidable questions, such as given a complex point $(x,y)$ is it in the Mandelbrot set?

• Undecidability in dynamical systems (Hainry), again sometimes closely connected to physics. dynamical systems generally have a multidimensional geometric interpretation.

• Visual programming languages. a program can be seen as a type of (directed?) graph with different types of vertices (eg conditional, arithmetic operation) etc.

• re cellular automata, see also game of life. conway is usually given credit for proving it Turing complete although an exact ref seems to be hard to come by. its probably also the earliest proof of Turing completeness associated with CAs. – vzn Sep 20 '13 at 15:03