CHURCH - TURING THESIS

Posted by Jennifer G. Santiago

I. TURING MACHINES

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'.

* Formal Definition of Turing Machine

A Turing Machine is a 7-tuple (Q,Σ, Γ, δ, q0, qaccept, qreject),where
  • 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.

* Examples of Turing Machine

The following table is Turing's very first example (Turing 1937):
"1. A machine can be constructed to compute the sequence 0 1 0 1 0 1..." (0 1 0...)
ConfigurationBehavior
m-configuration
(state)
Tape symbolTape operationsFinal m-configuration
(state)
bblankP0, Rc
cblankRe
eblankP1, Rf
fblankRb

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":

Current m-configuration (instruction)Tape symbolOperations on the tapeFinal m-configuration (instruction)
bNoneP0b
b0R, R, P1b
b1R, R, P0b

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):

Current m-configuration (Turing state)Tape symbolPrint-operationTape-motionFinal m-configuration (Turing state)
q1blankP0Rq2
q2blankP blank, i.e. ERq3
q3blankP1Rq4
q4blankP blank, i.e. ERq1

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 Sj 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:

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

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:

SequenceInstruction identifierHead


..................
11..................
22.....0............
33......0...........
44.....1.0..........
51......1.0.........
62.....0.1.0........
73......0.1.0.......
84.....1.0.1.0......
91......1.0.1.0.....
102.....0.1.0.1.0....
113......0.1.0.1.0...
124.....1.0.1.0.1.0..
131......1.0.1.0.1.0.




















142.....0.1.0.1.0.1.0

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 {s1, s2, s3, s4, s5}. 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
Initial m-configuration (current instruction)Tape symbolPrint operationTape motionFinal m-configuration (next instruction)
s10NNH
s11ERs2
s20ERs3
s21P1Rs2
s30P1Ls4
s31P1Rs3
s40ELs5
s41P1Ls4
s50P1Rs1
s51P1Ls5
H---

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

SequenceInstruction identifier




Head




1s100001100000
2s200000100000
3s200000010000
4s300000001000
5s400001010000
6s500010100000
7s500101000000
8s100010110000
9s200001001000
10s300000100100
11s300000010010
12s400001100100
13s400011001000
14s500110010000
15s100011011000
16H00011011000

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.

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.

Tape symbolCurrent state ACurrent state BCurrent state C

Write symbolMove tapeNext stateWrite symbolMove tapeNext stateWrite symbolMove tapeNext state
01RB1LA1LB
11LC1RB1NHALT

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:

location: right

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

SequenceInstruction identifier





Head






1A00000000000000
2B00000001000000
3A00000110000000
4C00001100000000
5B00011100000000
6A00111100000000
7B00011111000000
8B00001111100000
9B00000111110000
10B00000011111000
11B00000001111100
12A00000111111000
13C00001111110000
14H00001111110000


II. VARIANTS OF TURING MACHINE


* Multitape Turing Machine

A k-tape Turing machine can be described as a 6-tuple M=\langle Q, \Gamma, s, b, F, \delta \rangle where

  • Q is a finite set of states
  • Γ is a finite set of the tape alphabet
  • s \in Q is the initial state
  • b \in \Gamma is the blank symbol
  • F \subseteq Q is the set of final or accepting states
  • \delta: Q \times \Gamma^k \rightarrow Q \times  (\Gamma \times \{L,R,S\})^k is a partial function called the transition function, where L is left shift, R is right shift, S is no shift.
A multitape TM is like an ordinary TM with several tapes:
  • Each tape has its own head for reading/writing
  • Initially the input is on tape 1 and other are blank
  • Transition function allow for reading, writing,and moving the heads on all tapes simultaneously
Theorem (3.8) 3.13 Every multitape Turing machine has an equivalent single tape Turing machine.

Proof:
we show how to convert a multitape TM into a single tape TM. The key idea is to show how to simulate M with S Corollary 3.15 A language is Turing recognizable iff some multitape Turing machine recognizes it

Proof:
  • 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.
* Nondeterministic Turing Machines

A nondeterministic Turing machine can be formally defined as a 6-tuple M=(Q, \Sigma, \iota, \sqcup, A, \delta), where

  • Q is a finite set of states
  • Σ is a finite set of symbols (the tape alphabet)
  • \iota \in Q is the initial state
  • \sqcup \in \Sigma is the blank symbol
  • A \subseteq Q is the set of accepting states
  • \delta \subseteq \left(Q \backslash A \times  \Sigma\right) \times \left( Q \times \Sigma \times \{L,R\} \right) is a relation on states and symbols called the transition relation.
A non-Deterministic Turing Machine N allows more than one possible action per given state-tape symbol pair. N is always called a non-deterministic recognizer and is said to recognize L(N); furthermore, if in addition for all inputs and all computation branches, N always halts, then N is called a non-deterministic decider and is said to decide L(N).

* Enumerators

A TM with an attached printer.

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

* Equivalence with Other Models

Theorem 1.

The following classes of functions are equivalent:
a) the computable functions
b) functions computable by NICE programs, andc) functions computable by SMALL
programs.

Theorem 2.

For every SMALL program there is a Turing machine which computes exact function.
An interesting question about our translation of programs into Turing machinesi nvolves complexity. The previous transformation changed a SMALL programi nto a larger Turing machine and it is obvious that the machine runs for al onger period of time than the program. An intellectually curious reader might work out just what the relationship between the execution times might be.The last step in establishing the equivalence of our three models of computation is to show that NICE programs are at least as powerful as Turing machines. This also will be carried out by a construction, in this case, one that transforms Turing machines into programs.

A Turing machine is equivalent to a Push down automaton that has been made more flexible and concise by relaxing the lat-in-first-out requirement of its stack. (Interestingly, this seemingly minor relaxation enables the Turing machine to perform such a wide variety of computations that it can serve as a clearer model for the computational capabilities of all modern computer software.)

At the other extreme, some very simple models turn out to be Turing-equivalent, i.e. to have the same computational power as the Turing machine model.

Common equivalent models are the multi-tape Turing machine, multi-track Turing machine, machines with input and output, and the non-deterministic Turing machine (NDTM) as opposed to the deterministic Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.

Read-only, right-moving Turing Machines are equivalent to NDFA's (as well as DFA's by conversion using the NDFA to DFA conversion algorithm).

For practical and didactical intentions the equivalent register machine can be used as a usual assemblyprogramming language.

CONTEXT-FREE LANGUAGES

Posted by Jennifer G. Santiago

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


G = (Vt,Vn,P,S) where:

  • 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.
* Examples of Context-Free Grammar

- Example 1:

The canonical example of a context free grammar is parentheses matching, which is representative of the general case. There are two terminal symbols ( and ) and one nonterminal symbol S.

- Example 2:

A second canonical example is two different kinds of matching nested parentheses, described by the productions:

S → SS
S → ()
S → (S)
S → []
S → [S]


with terminal symbols [ ] ( ) and nonterminal S.

- Example 3:

The terminals here are a and b, while the only non-terminal is S. The language described is all nonempty strings of as and bs that end in a.This grammar is regular: no rule has more than one nonterminal in its right-hand side, and each of these nonterminals is at the same end of the right-hand side.

S → a
S → aS
S → bS


- Example 4:

In a context-free grammar, we can pair up characters the way we do with
brackets. The simplest example:

S → aSb
S → ab

This grammar generates the language , which is not regular The special character ε stands for the empty string. By changing the above grammar to

S → aSb ε

we obtain a grammar generating the language instead. This differs only in that it contains the empty string while the original grammar did not.

- Example 5:

Here is a context-free grammar for syntactically correct infix algebraic
expressions in the variables x, y and z:
S → x
S → y
S → z
S → S + S
S → S - S
S → S * S
S → S / S
S → ( S )

- Example 6:

A context-free grammar for the language consisting of all strings over {a,b}
containing an unequal number of a's and b's:

S → U V
U → TaU TaT
V → TbV TbT
T → aTbT bTaT ε

- Example 7:

Another example of a non-regular language is . It is context-free as it can be
generated by the following context-free grammar:
S → bSbb A
A → aA ε

* Designing Context-Free Grammar
• Some basic techniques:

1. Matching – enforcing the fact that your grammar generates matching pairs of symbols.

2. Using recursive relationships – when you can represent strings in the language interms of shorter strings in the language.
3. Thinking of each nonterminal A as representing a language of all strings w deriv-able from A. Then, combining these languages into one, using the rules.


* Ambiguity
A grammar that generates a sentence for which there are two or more distinct parse trees are
said to be ambiguous. The ambiguity occurs because the grammar specifies slightly less syntactic
structure.

* Chomsky Normal Form

In computer science, a context-free grammar is said to be in Chomsky normal form if all of its
production rules are of the form:

ABC or
Aα or


where A, B and C are nonterminal symbols, α is a terminal form (a symbol that represents a constant value), S is the start symbol, and ε is the empty string. Also, neither B nor C may be the start symbol.


II. PUSHDOWN AUTOMATA

* Formal Definition of Pushdown Automata



A NPDA W can be defined as a 7-tuple W = (Q,Σ,Φ,σ,s,Ω,F) where
• Q is a finite set of states
• Σ is a finite set of the input alphabet
• Φ is a finite set of the stack alphabet
• σ (or sometimes δ) is a finite transition relation (Q x (Σ U {ε} x Ø) ----> P (Q x Ø)
• s is an element of Q the start state
• Ω is the initial stack symbol
• F is subset of Q, consisting of the final states.
* Examples of Pushdown Automata
The following is the formal description of the PDA which recognizes the language by final state:
PDA for (by final state) M = (Q, Σ , Γ , δ , p , Z, F), where

Q = {p,q,r}
Σ = {0,1}
Γ = {A,Z}
F = {r}

δ consists of the following six instructions:

(p,0,Z,p,AZ), (p,0,A,p,AA), (p,ε,Z,q,Z), (p,ε,A,q,A), (q,1,A,q,ε), and (q,ε,Z,r,Z).

In words, in state p for each symbol 0 read, one A is pushed onto the stack. Pushing symbol A on
top of another A is formalized as replacing top A by AA. In state q for each symbol 1 read one A
is popped. At any moment the automaton may move from state p to state q, while it may move
from state q to accepting state r only when the stack consists of a single Z.

There seems to be no generally used representation for PDA. Here we have depicted the
instruction (p,a,A,q,α) by an edge from state p to state q labelled by a;A / α (read a; replace A
by α)

* Equivalence of Context-Free Grammars with Pushdown Automata
  • CFG and PDA are equivalent in power: a CFG generates a context-free language and
    a PDA recognizes a context-free language.
  • We show here how to convert a CFG into PDA that recognizes the language specified
    by the CFG and vice versa
  • Application: this equivalence allows a CFG to be used to specify a programming language and the equivalent PDA to be used to implement its compiler.

Theorem 2.0 A language is context-free iff some pushdown automaton recognizes it.

Note: This means that:

1. if a language L is context-free then there is a PDA ML that recognizes it.

2. if a language L is recognized by a PDA GL that generates L.

Lemma 2.21 If a language is context-free then some pushdown automaton recognizes it.

Proof idea:

1. Let A be a CFL. From the definition we know that A has a CFG G,
that generates it.

2. We will show how to convert G into a PDA P that accepts strings if w generates if G generates w.

3. P will work by determining a derivation of w.