[FOM] Turing machines, algorithms, and category theory
Paul Hollander
paul at personalit.net
Wed May 3 15:55:11 EDT 2017
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
>
More information about the FOM
mailing list