[FOM] Turing machines, algorithms, and category theory

[Paul Hollander]

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

Turning to category theory, a non-objectualist interpretation of the 
identity morphism 1x such that '1x: y → z' is true, is available by 
interpreting the triple <x, y, z> in terms of the algorithm <a3, a2, a1>.

In other words, the symbols 'a1' through 'a3', provide an interpretation 
for category theory expressions of the form '1x:y → z'., where

     a3 encodes 'x',

     <a2, a1> encodes the inference to |- (x = z) from |- (x = y).

The result of this re-interpretation of category theory is that each 
identity morphism 1x encodes the algorithm <a3, a2, a1>. Operations on 
1x generate encodings of Turing machines <a4, a3, a2, a1>,. and vice versa.

A more explicit representation is this:  '1x: y → z' encodes the 
algorithm such that

     [(1x |- (x = y)) => (1x |- (x = z))].

So 1x defines a set of identity sentences about x that is closed under 
deduction.

This provides a non-objectualist interpretation of category theory.

I would appreciate any feedback from FOM.

Sincerely,

Paul Hollander