Turing machine examples

Each possibility is followed by a sequence of actions until we arrive at the rightmost column, where the final m-configuration is "b": As observed by a number of commentators including Turing (1937) himself, (e.g., Post (1936), Post (1947), Kleene (1952), Wang (1954)) the Turing instructions are not atomic — further simplifications of the model can be made without reducing its computational power; see more at Post–Turing machine.

He gives us this example of the first little table converted:[4] Turing's statement still implies five atomic operations.

In the following example of what the machine does, we will note some peculiarities of Turing's models: The convention of writing the figures only on alternate squares is very useful: I shall always make use of it.

The example Turing machine handles a string of 0s and 1s, with 0 represented by the blank symbol.

In order to accomplish its task, this Turing machine will need only 5 states of operation, which are called {s1, s2, s3, s4, s5}.

The basic way it works is by copying each "1" to the other side, by moving back and forth - it is intelligent enough to remember which part of the trip it is on.

When it returns, it fills that "0" back in with a "1", then moves on to the next one, marking it with an "0" and repeating the cycle, carrying that "1" across and so on.

With each trip across and back, the marker "0" moves one step closer to the centre.

As noted above Turing (1937) makes it perfectly clear that this is the proper interpretation of the 5-tuples that describe the instruction.