[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 Paul Hollander
> Sent: Sunday, April 30, 2017 12:56
> To: Foundations of Mathematics <fom at cs.nyu.edu>
> Subject: [FOM] Turing machines, algorithms, and category theory
> 
> [NOTE: contains typographical corrections.]
> 
> A Turing machine may be encoded using the concatenation of four symbols,
> 'a1' through 'a4', such that the quadruple,
> 
>      <a4, a3, a2, a1>,
> 
> is interpreted as follows:
> 
>      a4 encodes the current machine state,
> 
>      a3 encodes a recursive symbol,
> 
>      a2 encodes the next machine state, and
> 
>      a1 encodes the action to be performed to get to the next state.
> 
> On this view, the set of Turing machines is a subset of the set (N x N x
> N x N), where N is the set of natural numbers {0, 1, 2, ... }.
> 
> The same interpretation of 'a1' through 'a3' licenses encoding
> algorithms as triples,
> 
>      <a3, a2, a1>
> 
> in which each symbol encodes the same as in the Turing machine, but
> there is no current machine state.  Here, the set of algorithms is a
> subset of the set (N x N x N).
[orcmid] 

I don't see how that reduction is workable.  A state typically has several distinct rules for determining an input-determined action and next state.  In removing state, the resulting <a3, a2, a1> no longer distinguish the possibility of different states having some identical rules but not others.  While state reduction is a possibility, not attaching the transition rules to any state makes no sense when next-state (a2) is material to the functioning of the specific Turing Machine. 

Simple example,

     <0, 0, 1, 1>
     <0, 1, 2, 1>
     <1, 0, 1, 1>
     <1, 1, 3, 1>
      ...
where leading 0 marks are scanned and the state reached after the first 1 is different depending on whether there was a preceding 0 or not.  (Action 1 is taken to mean move the tape one position in the forward direction.)
> 
[ ... ]