Turing machine examples

Turing machine examples

The following are examples to supplement the article Turing machine.

Turing's very first example

The following table is Turing's very first example (Turing 1936)::"1. A machine can be constructed to compute the sequence 0 1 0 1 0 1..." ("Undecidable" p. 119)

Turing's statement still implies five atomic operations. At a given instruction (m-configuration) the machine:
# observes the tape-symbol underneath the head
# based on the observed symbol goes to the appropriate instruction-sequence to use
# prints symbol Sj or erases or does nothing
# moves tape left, right or not at all
# goes to the final m-configuration for that symbol

Because a Turing machine's actions are not atomic, a simulation of the machine must atomize each 5-tuple into a sequence of simpler actions. One possibility — used in the following examples of "behaviors" of his machine — is as follows::(qi) Test tape-symbol under head: If the symbol is S0 go to qi.01, if symbol S1 go to qi.11, if symbol S2 go to qi.21, etc.

::(qi.01) print symbol Sj0 or erase or do nothing then go to qi.02::(qi.02) move tape left or right nor not at all then go to qm0

::(qi.11) print symbol Sj1 or erase or do nothing then go to qi.12::(qi.12) move tape left or right nor not at all then go to qm1

::(qi.21) print symbol Sj2 or erase or do nothing then go to qi.22::(qi.22) move tape left or right nor not at all then go to qm2

: (etc — all symbols must be accounted for)

So-called "canonical" finite state machines do the symbol tests "in parallel"; see more at microprogramming.

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." (Undecidable p. 121) Thus when printing he skips every other square. The printed-on squares are called F-squares; the blank squares in between may be used for "markers" and are called "E-squares" as in "liable to erasure." The F-squares in turn are his "Figure squares" and will only bear the symbols 1 or 0 — symbols he called "figures" (as in "binary numbers").

In this example the tape starts out "blank", and the "figures" are then printed on it. For brevity only the TABLE-states are shown here:

The behavior of this machine can be described as a loop:it starts out in s1, replaces the first 1 with a 0, then uses s2 to move to the right, skipping over 1s and the first 0 encountered. s3 then skips over the next sequence of 1s (initially there are none) and replaces the first 0 it finds with a 1. s4 moves back to the left, skipping over 1s until it finds a 0 and switches to s5. s5 then moves to the left, skipping over 1s until it finds the 0 that was originally written by s1.

It replaces that 0 with a 1, moves one position to the right and enters s1 again for another round of the loop.

This continues until s1 finds a 0 (this is the 0 in the middle of the two strings of 1s) at which time the machine halts.

Alternative description

Another description sees the problem as how to keep track of how many "1"'s there are. We can't use one state for each possible number (a state for each of 0,1,2,3,4,5,6 etc), because then we'd need infinite states to represent all the natural numbers, and the state machine is "finite" - we'll have to track this using the tape in some way.

The basic way it works 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. In more detail, it carries each "1" across to the other side, by recognizing the separating "0" in the middle, and recognizing the "0" on the other side to know it's reached the end. It comes back using the same method, detecting the middle "0", and then the "0" on the original side. This "0" on the original side is the key to the puzzle of how it keeps track of the number of 1's.

The trick is that before carrying the "1", it marks that digit as "taken" by replacing it with an "0". 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". This is how it keeps track of how many "1"'s it has taken across.

Interestingly, when it returns, the marker "0" looks like the end of the collection of "1"s to it - any "1"s that have already been taken across are invisible to it (on the other side of the marker "0") and so it is as if it is working on an (N-1) number of "1"s - similar to a proof by Mathematical induction.

A full "run" showing the results of the intermediate "motions". To see it better click on the image, then click on the higher resolution download:

3-state Busy Beaver

The following Turing table of instructions was derived from Peterson (1988) page 198, Figure 7.15. Peterson moves the head; in the following model the tape moves.

The "state" drawing of the 3-state busy beaver shows the internal sequences of events required to actually perform "the state". As noted above Turing 1936 makes it perfectly clear that this is the proper interpretation of the 5-tuples that describe the instruction ("Undecidable", p. 119). For more about the atomization of Turing 5-tuples see Post-Turing machine:

The following table shows the "compressed" run — just the Turing states:

The full "run" of the 3-state busy beaver. The resulting Turing-states (what Turing called the "m-configurations" — "machine-configurations") are shown highlighted in grey in column A, and also under the machine's instructions (columns AF-AU)):

Wolfram Turing machine examples

In 1985, Stephen Wolfram conjectured that a one-dimensional two-state cellular automaton he later called Rule 110 was Turing complete (universal). Matthew Cook verified that conjecture in 2000. Wolfram's book "A New Kind of Science" gives useful examples of how Turing machines can be visually represented, and further conjectured that an even simpler 2-state 3-symbol Turing machine might also be universal. In October 2007, Wolfram Research awarded Alex Smith a $25,000 prize for verifying the second conjecture.

References

For references see Turing machine.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Turing machine equivalents — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Turing machine — For the test of artificial intelligence, see Turing test. For the instrumental rock band, see Turing Machine (band). Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine… …   Wikipedia

  • Non-deterministic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Multi-track Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Probabilistic Turing machine — Turing machine(s) Machina Universal Turing machine Alternating Turing machine Quantum Turing machine Read only Turing machine Read only right moving Turing Machines Probabilistic Turing machine Multi track Turing machine Turing machine… …   Wikipedia

  • Universal Turing machine — This article is a supplement to the article Turing machine. Alan Turing s universal computing machine (alternately universal machine , machine U , U ) is the name given by him (1936 1937) to his model of an all purpose a machine (computing… …   Wikipedia

  • Wolfram's 2-state 3-symbol Turing machine — In his A New Kind of Science , Stephen Wolfram found a universal 2 state 5 color Turing machine, and [http://www.wolframscience.com/nksonline/page 709 conjectured] that a particular 2 state 3 color Turing machine (hereinafter (2,3) Turing… …   Wikipedia

  • Post–Turing machine — The article Turing machine gives a general introduction to Turing machines, while this article covers a specific class of Turing machines. A Post–Turing machine is a program formulation of an especially simple type of Turing machine, comprising a …   Wikipedia

  • Turing tarpit — Turing tar pit is a general term for a programming language designed to be Turing complete while in some sense simplifying to the greatest extent possible both the syntax and the semantics of the language. Such a language gives up certain… …   Wikipedia

  • Turing's proof — First published in January 1937 with the title On Computable Numbers, With an Application to the Entscheidungsproblem , Turing s proof was the second proof of the assertion (Alonzo Church proof was first) that some questions are undecidable :… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”