[FOM] Turing machines, algorithms, and category theory

[Paul Hollander]

I made a mistake.  I apologize.  I believe this is correct

         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 at the next state.

Cheers,

Paul Hollander







On 5/1/17 07:55, Dennis E. Hamilton wrote:
>
>> -----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.)
> [ ... ]
>
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
>