[FOM] Turing machines, algorithms, and category theory

Dennis E. Hamilton dennis.hamilton at acm.org
Mon May 1 10:55:03 EDT 2017

> -----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).

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.)
[ ... ]

More information about the FOM mailing list