[FOM] Turing machines, algorithms, and category theory

[Patrik Eklund]

For categories, there is not a notion of recursion or recursive 
category, or something similar. Recursion resides in set theory, and 
cannot easily be abstracted away from it.

There is history behind "categories and machines". If we look at the 
name "automata", there was a name clash in the 1950s, when computers and 
automation enters the scene. Automata in the sense of dynamic systems, 
Kalman filters and such things, were almost confused with automata in 
the sense of Turing and Kleene. Arbib and Manes, and others tried to 
merge the the two under a notion of "category of machines". It's not 
successful, and on the Turing side it never reaches Turing machines, but 
remains on the finite-state machine/regular language level. When we come 
to context-free and pushdown, we have stacks, and the categorical 
modelling has failed so far. This is also clear in Manes' book and his 
treatment of machines.

A second remark is that we should not jump to Turing and recursively 
enumerable without passing through context-free. Note that "algorithm" 
resides well on the context-free level, as imperative languages are on 
this level. "Categorical programming" involving co-equalizers as 
unifiers turn up during the 1980s, but was not connected with pushdown 
automata.

So basically, the route to follow is, I think, to see the tensor in 
monoidal categories as a candidate for providing expressions, and from 
there try to identify what pushdown would be in a categorical model. 
Somewhere along that line, recursion and recursive enumerability must be 
unravelled in categorical terms.

Under the Catlist (Category theory mailing list) I expressed some views 
months ago on the "Turing category" as intuitively related to monoidal 
categories. On machines, languages and grammar we should indeed note how 
they are "monoidal", and how "computability" is in the sense only of 
"computable functions of natural numbers". Recursion is tricky as we now 
from the history of computability. Gödel had much respect for Herbrand's 
intuition about recursion residing in inference mechanisms, and the 
whole business related to self-referentiality is still subject to 
debate. And so and so forth.

In conclusion, my general suggestion is to try out a "categorical 
interpretation of computing" rather than aiming at a "computational 
interpretation of categories".

Best,

Patrik



On 2017-04-30 22:56, Paul Hollander wrote:

> A Turing machine may be encoded ...
> ...
> This provides a non-objectualist interpretation of category theory.