CS 231 AUTOMATA AND FORMAL LANGUAGES

A Turing machine is a theoretical device that manipulates symbols contained on a strip of tape. Despite its simplicity, a Turing machine can be adapted to simulate the logic of any computer algorithm, and is particularly useful in explaining the functions of a CPU inside of a computer. The "Turing" machine was described by Alan Turing in 1937,who called it an "a(utomatic)-machine". Turing machines are not intended as a practical computing technology, but rather as a thought experiment representing a computing machine. They help computer scientists understand the limits of mechanical computation.

A Turing machine that is able to simulate any other Turing machine is called a Universal Turing Machine (UTM, or simply a universal machine). A more mathematically-oriented definition with a similar "universal" nature was introduced by Alonzo Church, whose work on lamda calculus intertwined with Turing's in a formal theory of computation known as the Chuch Turing Thesis The thesis states that Turing machines indeed capture the informal notion of effective method in logic and mathematics, and provide a precise definition of an algorithm or 'mechanical procedure'.

• Q is a finite set of states
• Σ is an input alphabet, ⊔ / ∈ Σ
• Γ is a tape alphabet, ⊔ ∈ Γ, and Σ ⊂ Γ
• δ : Q × Γ → (Q ∪ {qaccept, qreject}) × Γ × {L,R} is the transition function
• q0inQ is the start state
• qaccept, qreject are the accept and reject states, respectively.

"1. A machine can be constructed to compute the sequence 0 1 0 1 0 1..." (0 1 0...)

With regard to what actions the machine actually does, Turing (1936) states the following:

"This [example] table (and all succeeding tables of the same kind) is to be understood to mean that for a configuration described in the first two columns the operations in the third column are carried out successively, and the machine then goes over into the m-configuration in the final column."

He makes this very clear when he reduces the above table to a single instruction called "b" (Undecidable p. 120), but his instruction consists of 3 lines. Instruction "b" has three different symbol possibilities {None, 0, 1}. 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

Turing proposed that his table be further atomized by allowing only a single print/erase followed by a single tape movement L/R/N. He gives us this example of the first little table converted (Undecidable, p. 127):

Turing's statement still implies five atomic operations. At a given instruction (m-configuration) the machine:

1. observes the tape-symbol underneath the head
2. based on the observed symbol goes to the appropriate instruction-sequence to use
3. prints symbol S_j or erases or does nothing
4. moves tape left, right or not at all
5. 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:

(q_i) Test tape-symbol under head: If the symbol is S₀ go to q_i.01, if symbol S₁ go to q_i.11, if symbol S₂ go to q_i.21, etc.

(q_i.01) print symbol S_j0 or erase or do nothing then go to q_i.02

(q_i.02) move tape left or right nor not at all then go to qm0

(q_i.11) print symbol S_j1 or erase or do nothing then go to q_i.12

(q_i.12) move tape left or right nor not at all then go to qm1

(q_i.21) print symbol S_j2 or erase or do nothing then go to q_i.22

(q_i.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"

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:

A close look at the table reveals certain problems with Turing's own example—not all the symbols are accounted for.

For example, suppose his tape was not initially blank. What would happen? The Turing machine would read different values than the intended values.

2. A copy of Subroutine

This is a very important subroutine used in the "multiply" routine.

The example Turing machine handles a string of 0s and 1s, with 0 represented by the blank symbol. Its task is to double any series of 1s encountered on the tape by writing a 0 between them. For example, when the head reads "111", it will write a 0, then "111". The output will be "1110111".

In order to accomplish its task, this Turing machine will need only 5 states of operation, which are called {s₁, s₂, s₃, s₄, s₅}. Each state does 4 actions:

1. Read the symbol under the head
2. Write the output symbol decided by the state
3. Move the tape to the left or to the right decided by the state
4. Switch to the following state decided by the current state

A "run" of the machine sequences through 16 machine-configurations (aka Turing states):

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

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

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

3. The 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 (1937) 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:

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

• if: a Turing recognizable language is recognized by an ordinary TM. But an ordinary TM is a special case of a multitape TM.
  

• only if: This part follows from the equivalence of a Turing multitape machine with the Turing machine M that simulates it. That is, if L is recognized by M then L is also recognized by the TM s that simulates M.
  

A nondeterministic Turing machine can be formally defined as a 6-tuple , where

• Q is a finite set of states
• Σ is a finite set of symbols (the tape alphabet)
• is the initial state
• is the blank symbol
• is the set of accepting states
• is a relation on states and symbols called the transition relation.

• Start with a blank input tape
• The language enumerated is all the strings it prints out.

I. CONTEXT - FREE GRAMMAR

* Definition of Context-Free Grammar

Just as any formal grammar, a context-free grammar G can be defined as a 4-tuple

• Vt is a finite set of terminals
• Vn is a finite set of non-terminals
• P is a finite set of production rules
• S is an element of Vn, the distinguished starting non-terminal and elements of P are of the form.