Geometric Interpretation of Computation

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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:

• Computational Structures for Modelling Space, Time and Causality, Dagstuhl Seminar 06341, August 20–25, 2006

• Key Martin and Prakash Panangaden: Spacetime geometry from causal structure and a measurement

Answer 5

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

Answer 6

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.