<p>You might be interested in <a href="http://www.sciencedirect.com/science/article/pii/S0168007208000948">Turing categories</a> by Robin Cockett and Pieter Hofstra. From the point of view of category theory the question "what is <em>the</em> category of Turing machines" is less interesting than "what is the categorical structure which underlies computation". Thus, Robin and Pieter identify a general kind of category that is suitable for developing computability theory. Then, there are several possibilities for defining such a category starting from Turing machines. Why have one category when you can have a whole category of them?</p>

CC BY-SA 3.0
2017-01-20T08:15:02.620Z
2017-01-20T08:15:02.620Z
Andrej Bauer
<p>If your objects are Turing machines, there are several reasonable possibilities for morphisms. For example:</p>

<p>1) Consider Turing machines as the automata they are, and consider the usual morphisms of automata (maps between the alphabets and the states that are consistent with one another) which also either preserve the motions of the tape head(s), or exactly reverse them (e.g. whenever the source TM goes left, the target TM goes right and vice versa).</p>

<p>2a) Consider simulations or <a href="https://en.wikipedia.org/wiki/Bisimulation">bisimulations</a>.</p>

<p>2b) Along similar lines, you can consider when one TM can be transformed (by a computable function) to simulate the other one. This can be done at the level of step-wise behavior, or as Yuval suggested in the comments, at the level of input-output, that is, a morphism from $T_1$ to $T_2$ (or maybe the other way around) is a computable $f$ such that $T_1(x) = T_2(f(x))$ for all $x$. </p>

<p>3) Consider the transition graph of the Turing machine (each vertex is a complete description of the state of the machine and the tapes, with directed edges corresponding to the transitions the TM would make) and consider morphisms of graphs. For TMs this is a very coarse relationship, however, as it essentially ignores the local nature of computation (it ignores, for example, what the contents of the tapes are).</p>

<p>I think the real question is: what is it you want to <em>know</em> about TMs or to <em>do</em> with them? In the absence of this, it's hard to give arguments for any one definition over another, beyond naturality (in the usual sense of the word, not the categorical sense).</p>

CC BY-SA 3.0
2017-01-19T19:00:31.607Z
I'm very new to this kind of math. I have read in the past about complexity theory but only recently I've picked it up again after I saw someone on the internet claiming that somehow cohomological techniques would enter complexity theory in the next century and it got me interested. After some reading I realized that beyond some superficial understanding of the definition of a turing machine I have basically no idea what it encodes exactly. That's how I arrived at the question. So you could say that at a very rudimentary level i'm trying to imagine how cohomology can enter complexity theory.
Saal Hardali
CC BY-SA 3.0
2017-01-19T19:03:40.603Z
I realise this is extremly premature for someone like me who understands very little about this topic still I wanted to play a bit with this idea in my head of "doing homotopy theory on the category of turing machines". Your answer is nice and I certainly aim to read more into aspects of it. Thank you.
Saal Hardali
CC BY-SA 3.0
2017-01-20T00:30:01.003Z
@SaalHardali: I am curious where you read that cohomology will enter complexity theory? I can think of two ways, but I don't yet see a route via homotopy type theory (perhaps because I don't yet understand HoTT well enough yet). The two ways I can see: (1) in distributed computing this has *already* happened, viz. Herlihy and Rajsbaum, and (2) via geometric complexity theory.
Joshua Grochow
CC BY-SA 3.0
2017-01-20T00:36:31.650Z
By homotopy theory i was reffering to the general idea of studying categories with weak equivalences and not so much HoTT. I read it in a poll about P=?NP it's not hard to find I think it was linked to from one of the questions on this site. I guess my first guess (as an outsider) was that maybe there's some kind of interesting weak equivalence on some category of a model of computation that corresponds to complexity classes somehow and then studying functors invariant under those weak equivalence will constitue what I call a "homotopy theory" this is probably very naive and total miss though.
Saal Hardali
CC BY-SA 3.0
2017-01-20T09:11:45.857Z
In case your interest is complexity theory rather than computability theory, maybe this answer is  helpful to you: http://cstheory.stackexchange.com/a/3422/4896
Sasho Nikolov
CC BY-SA 3.0
2017-01-19T18:47:57.693Z
2017-01-19T18:47:57.693Z
Joshua Grochow
<p>Saal Hardali mentioned that he wanted a category of Turing machines to do geometry (or at least homotopy theory) on. However, there are a lot of different ways to achieve similar aims.</p>
<ul>
<li><p>There is a very strong analogy between computability and topology. The intuition is that termination/nontermination is like the Sierpinski space, since termination is finitely observable (i.e., open) and nontermination isn't (not open). See Martin Escardo's lecture notes <a href="https://www.cs.bham.ac.uk/%7Emhe/papers/entcs87.pdf" rel="nofollow noreferrer"><em>Synthetic topology of data types and classical spaces</em></a> for a moderately gentle but comprehensive introduction to these ideas.</p>
</li>
<li><p>In concurrent and distributed computation, it is often useful to think of the possible executions of a program as a space, and then various synchronization constraints can be expressed as homotopical properties of the space. (The fact that execution has a time order seems to call for directed homotopy theory, rather than ordinary homotopy theory.)</p>
<p>See Eric Goubault's article <a href="https://projecteuclid.org/journals/homology-homotopy-and-applications/volume-5/issue-2/Some-geometric-perspectives-in-concurrency-theory/hha/1088453323.full" rel="nofollow noreferrer"><em>Some Geometric Perspectives on Concurrency Theory</em></a> for more details. Also see Maurice Herlihy and Nir Shavit's Goedel-prize winning paper, <a href="https://cs.brown.edu/%7Emph/HerlihyS99/p858-herlihy.pdf" rel="nofollow noreferrer"><em>The Topological Structure of Asynchronous Computability</em></a>, which settled some long-standing open problems in the theory of distributed programming.</p>
</li>
<li><p>A third idea comes via homotopy type theory, via the discovery that Martin-Löf type theory is (likely?) a syntactic presentation (in the sense of generators and relations) of the theory of omega-groupoids -- ie, the models of abstract homotopy theory. The best introduction to these ideas is the <a href="https://homotopytypetheory.org/book/" rel="nofollow noreferrer">homotopy type theory book</a>.</p>
</li>
</ul>
<p>Note that all of these ideas are very different from each other, but all still use geometric intuitions! And there are still others, which I don't know, like the uses that arise in geometric complexity theory, and the way that the theories of circuits can be described in terms of <a href="http://128.2.67.219/johnbaez/show/Circuit%20theory#chain_complexes_from_circuits" rel="nofollow noreferrer">the (co)homology theory of graphs</a>.</p>
<p>Basically, when you are doing CS, geometry is a <em>tool</em> -- you use it to formalize your intuitions, so that you can get leverage via the enormous body of work that has been done on it. But it's an idea amplifier, not a substitute for having ideas!</p>

CC BY-SA 4.0
2017-01-20T16:35:45.080Z
2022-04-19T09:41:38.997Z
2022-04-19T09:41:38.997Z
Neel Krishnaswami
<p><em>Disclaimer: I know very little about complexity theory.</em></p>

<p>I'm sorry but there is really no way to ask this question without being (terribly) concise: </p>

<blockquote>
  <p><strong>What should be the morphisms in "the" category of Turing machines?</strong></p>
</blockquote>

<p>This is obviously subjective and depends upon one's interpretation of the theory, so an answer to this question should ideally give some evidence and reasoning supporting the answer as well.</p>

<p>I'd like to emphasis the point that i'm looking for a category of <strong>Turing machines</strong> and not of <strong>formal languages</strong> for example. In particular I think my morphisms should contain finer information then reductions or anything like that (I'm not sure though).</p>

<p>Of course if there's already a well known and used category in the literature i'd like to know what it is.</p>

CC BY-SA 3.0
2017-01-18T16:34:50.010Z
You said it yourself - computable functions.
Yuval Filmus
CC BY-SA 3.0
2017-01-18T21:20:18.353Z
If you can define a thing mathematically, there are infinitely many different ways to define the same thing. (The set of computable functions is a great example!) Maybe there is a "smallest" category in some sense.
Raphael
CC BY-SA 3.0
2017-01-18T21:25:42.087Z
@Raphael the thing is you never really define a structure until you put it in a category. That's when the  inessential features of the specific definition are stripped away.
Saal Hardali
CC BY-SA 3.0
2017-01-18T21:32:14.323Z
@SaalHardali Keep in mind that not everybody subscribes to the promise of salvation made by category theorists. In fact, many roll their eyes.
Raphael
CC BY-SA 3.0
2017-01-18T21:33:40.407Z
@Raphael I was making a much simpler point. to any definition you can just add a set of random elements that does nothing.
Saal Hardali
CC BY-SA 3.0
2017-01-19T18:48:50.363Z
@Yuval: What would it mean to have a computable function "between two Turing machines"? The goal is to have the *objects* of the category be TMs.
Joshua Grochow
CC BY-SA 3.0
2017-01-19T18:50:59.403Z
@JoshuaGrochow There is a morphism labeled $f$ from $T_1$ to $T_2$ if $f$ reduces $T_2$ to $T_1$ (or perhaps the other way around), that is $T_1(x) = T_2(f(x))$. This is, say, for machines which on every input either halt or not, but don't have any further output.
Yuval Filmus
CC BY-SA 3.0
2017-01-20T10:04:51.220Z
See also https://cstheory.stackexchange.com/questions/12207/is-there-a-theory-that-combines-category-theory-abstract-algebra-and-computation
Martin Berger
CC BY-SA 3.0
2017-01-20T10:05:21.857Z
Aside: why should TMs be objects? They could also be morphisms.
Martin Berger
<cc.complexity-theory><turing-machines><ct.category-theory>
"The" category of Turing machines?
Saal Hardali
# "The" category of Turing machines?

(Asked by: username_0 on 2017-01-18)

*Disclaimer: I know very little about complexity theory.*

I'm sorry but there is really no way to ask this question without being (terribly) concise:

> **What should be the morphisms in "the" category of Turing machines?**

This is obviously subjective and depends upon one's interpretation of the theory, so an answer to this question should ideally give some evidence and reasoning supporting the answer as well.

I'd like to emphasis the point that i'm looking for a category of **Turing machines** and not of **formal languages** for example. In particular I think my morphisms should contain finer information then reductions or anything like that (I'm not sure though).

Of course if there's already a well known and used category in the literature i'd like to know what it is.

**Tags:** cc.complexity-theory, turing-machines, ct.category-theory

> **Comments:**
> **username_1**: You said it yourself - computable functions.  
> **username_2**: If you can define a thing mathematically, there are infinitely many different ways to define the same thing. (The set of computable functions is a great example!) Maybe there is a "smallest" category in some sense.  
> **username_0**: @username_2 the thing is you never really define a structure until you put it in a category. That's when the  inessential features of the specific definition are stripped away.  
> **username_2**: @SaalHardali Keep in mind that not everybody subscribes to the promise of salvation made by category theorists. In fact, many roll their eyes.  
> **username_0**: @username_2 I was making a much simpler point. to any definition you can just add a set of random elements that does nothing.  
> **username_3**: @Yuval: What would it mean to have a computable function "between two Turing machines"? The goal is to have the *objects* of the category be TMs.  
> **username_1**: @JoshuaGrochow There is a morphism labeled $f$ from $T_1$ to $T_2$ if $f$ reduces $T_2$ to $T_1$ (or perhaps the other way around), that is $T_1(x) = T_2(f(x))$. This is, say, for machines which on every input either halt or not, but don't have any further output.  
> **username_4**: See also https://cstheory.stackexchange.com/questions/12207/is-there-a-theory-that-combines-category-theory-abstract-algebra-and-computation  
> **username_4**: Aside: why should TMs be objects? They could also be morphisms.  

---

## 3 answers

### Answer by username_7 on 2017-01-20. Score: 14 | Accepted answer

username_0 mentioned that he wanted a category of Turing machines to do geometry (or at least homotopy theory) on. However, there are a lot of different ways to achieve similar aims.

* There is a very strong analogy between computability and topology. The intuition is that termination/nontermination is like the Sierpinski space, since termination is finitely observable (i.e., open) and nontermination isn't (not open). See Martin Escardo's lecture notes [*Synthetic topology of data types and classical spaces*](https://www.cs.bham.ac.uk/%7Emhe/papers/entcs87.pdf) for a moderately gentle but comprehensive introduction to these ideas.
* In concurrent and distributed computation, it is often useful to think of the possible executions of a program as a space, and then various synchronization constraints can be expressed as homotopical properties of the space. (The fact that execution has a time order seems to call for directed homotopy theory, rather than ordinary homotopy theory.)

  See Eric Goubault's article [*Some Geometric Perspectives on Concurrency Theory*](https://projecteuclid.org/journals/homology-homotopy-and-applications/volume-5/issue-2/Some-geometric-perspectives-in-concurrency-theory/hha/1088453323.full) for more details. Also see Maurice Herlihy and Nir Shavit's Goedel-prize winning paper, [*The Topological Structure of Asynchronous Computability*](https://cs.brown.edu/%7Emph/HerlihyS99/p858-herlihy.pdf), which settled some long-standing open problems in the theory of distributed programming.
* A third idea comes via homotopy type theory, via the discovery that Martin-Löf type theory is (likely?) a syntactic presentation (in the sense of generators and relations) of the theory of omega-groupoids -- ie, the models of abstract homotopy theory. The best introduction to these ideas is the [homotopy type theory book](https://homotopytypetheory.org/book/).

Note that all of these ideas are very different from each other, but all still use geometric intuitions! And there are still others, which I don't know, like the uses that arise in geometric complexity theory, and the way that the theories of circuits can be described in terms of [the (co)homology theory of graphs](http://128.2.67.219/johnbaez/show/Circuit%20theory#chain_complexes_from_circuits).

Basically, when you are doing CS, geometry is a *tool* -- you use it to formalize your intuitions, so that you can get leverage via the enormous body of work that has been done on it. But it's an idea amplifier, not a substitute for having ideas!


---

### Answer by username_5 on 2017-01-20. Score: 15

You might be interested in [Turing categories](http://www.sciencedirect.com/science/article/pii/S0168007208000948) by Robin Cockett and Pieter Hofstra. From the point of view of category theory the question "what is *the* category of Turing machines" is less interesting than "what is the categorical structure which underlies computation". Thus, Robin and Pieter identify a general kind of category that is suitable for developing computability theory. Then, there are several possibilities for defining such a category starting from Turing machines. Why have one category when you can have a whole category of them?


---

### Answer by username_3 on 2017-01-19. Score: 15

If your objects are Turing machines, there are several reasonable possibilities for morphisms. For example:

1) Consider Turing machines as the automata they are, and consider the usual morphisms of automata (maps between the alphabets and the states that are consistent with one another) which also either preserve the motions of the tape head(s), or exactly reverse them (e.g. whenever the source TM goes left, the target TM goes right and vice versa).

2a) Consider simulations or [bisimulations](https://en.wikipedia.org/wiki/Bisimulation).

2b) Along similar lines, you can consider when one TM can be transformed (by a computable function) to simulate the other one. This can be done at the level of step-wise behavior, or as Yuval suggested in the comments, at the level of input-output, that is, a morphism from $T\_1$ to $T\_2$ (or maybe the other way around) is a computable $f$ such that $T\_1(x) = T\_2(f(x))$ for all $x$.

3) Consider the transition graph of the Turing machine (each vertex is a complete description of the state of the machine and the tapes, with directed edges corresponding to the transitions the TM would make) and consider morphisms of graphs. For TMs this is a very coarse relationship, however, as it essentially ignores the local nature of computation (it ignores, for example, what the contents of the tapes are).

I think the real question is: what is it you want to *know* about TMs or to *do* with them? In the absence of this, it's hard to give arguments for any one definition over another, beyond naturality (in the usual sense of the word, not the categorical sense).

> **Comments:**
> **username_0**: I'm very new to this kind of math. I have read in the past about complexity theory but only recently I've picked it up again after I saw someone on the internet claiming that somehow cohomological techniques would enter complexity theory in the next century and it got me interested. After some reading I realized that beyond some superficial understanding of the definition of a turing machine I have basically no idea what it encodes exactly. That's how I arrived at the question. So you could say that at a very rudimentary level i'm trying to imagine how cohomology can enter complexity theory.  
> **username_0**: I realise this is extremly premature for someone like me who understands very little about this topic still I wanted to play a bit with this idea in my head of "doing homotopy theory on the category of turing machines". Your answer is nice and I certainly aim to read more into aspects of it. Thank you.  
> **username_3**: @SaalHardali: I am curious where you read that cohomology will enter complexity theory? I can think of two ways, but I don't yet see a route via homotopy type theory (perhaps because I don't yet understand HoTT well enough yet). The two ways I can see: (1) in distributed computing this has *already* happened, viz. Herlihy and Rajsbaum, and (2) via geometric complexity theory.  
> **username_0**: By homotopy theory i was reffering to the general idea of studying categories with weak equivalences and not so much HoTT. I read it in a poll about P=?NP it's not hard to find I think it was linked to from one of the questions on this site. I guess my first guess (as an outsider) was that maybe there's some kind of interesting weak equivalence on some category of a model of computation that corresponds to complexity classes somehow and then studying functors invariant under those weak equivalence will constitue what I call a "homotopy theory" this is probably very naive and total miss though.  
> **username_6**: In case your interest is complexity theory rather than computability theory, maybe this answer is  helpful to you: http://cstheory.stackexchange.com/a/3422/4896  

---

