[FOM] Turing machines, algorithms, and category theory
peklund at cs.umu.se
Mon May 1 03:08:10 EDT 2017
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
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".
On 2017-04-30 22:56, Paul Hollander wrote:
> A Turing machine may be encoded ...
> This provides a non-objectualist interpretation of category theory.
More information about the FOM