[FOM] Turing machines, algorithms, and category theory

[Dennis E. Hamilton]

> -----Original Message-----
> From: fom-bounces at cs.nyu.edu [mailto:fom-bounces at cs.nyu.edu] On Behalf
> Of Patrik Eklund
> Sent: Monday, May 1, 2017 00:08
> To: Foundations of Mathematics <fom at cs.nyu.edu>
> Subject: Re: [FOM] Turing machines, algorithms, and category theory
> 
[ ... ]
> 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.
[ ... ]

[orcmid] 

I think there are some terminology glosses here.  I am not certain what adding precision does for any connection with category theory, but it might be helpful.

 1. I am unaware of any forced connection between context-free languages (Chomsky level 2) and "imperative languages".  Also, although context-free grammars are often used to characterize actual programming languages, the additional (and essential) context-sensitive constraints tend to be handled by side-conditions.  When formal grammars are also used to capture those conditions, the result is not a context-free language.   [The same is true for standard FOL notation - the binding of variables and scoping of quantifiers is not context-free, for starters, although parsing is easy and the context-sensitivity is quite regular.]

 2. The use of "algorithm" in this context is puzzling.  While one can say that a Turing Machine can represent an algorithm (given the additional representation details and constraints), and a Universal Turing Machine can represent (i.e., simulate) all Turing Machines, including the ones that embody algorithms, I fail to see how that is tied to some sort of "context-free level."  The state-table specification of a Turing Machine is not context-free.  I think it is safe to conclude the same for the UTM, as it can be instructed to simulate itself.

 3. One can consider a quasi-context-free language of Turing Machine descriptions that are well-formed when the contextual constraints are satisfied. It will be decidable whether such a description is syntactically well-formed or not. It won't be decidable which well-formed ones are for algorithms if one includes halting as a condition of algorithm-hood.  I mention this to emphasize the lack of any strict connection between (quasi-)context-freeness of the description and the elaboration of operations involved in carrying out the represented algorithm for a given input.

> 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
[orcmid]

I suspect that my observations, above, do not interfere with Patrik's conclusion in any manner.

 - Dennis