[FOM] Turing machines, algorithms, and category theory
Dennis E. Hamilton
dennis.hamilton at acm.org
Mon May 1 20:02:31 EDT 2017
> -----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
[ ... ]
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".
I suspect that my observations, above, do not interfere with Patrik's conclusion in any manner.
More information about the FOM