Church-Turing Thesis

**Turing Machines**

-Formal Definition of a Turing Machine

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,[1] 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. Turing gave a succinct definition of the experiment in his 1948 essay, "Intelligent Machinery". Referring to his 1936 publication, Turing wrote that the Turing machine, here called a Logical Computing Machine, consisted of: ...an infinite memory capacity obtained in the form of an infinite tape marked out into squares, on each of which a symbol could be printed. At any moment there is one symbol in the machine; it is called the scanned symbol. The machine can alter the scanned symbol and its behavior is in part determined by that symbol, but the symbols on the tape elsewhere do not affect the behavior of the machine. However, the tape can be moved back and forth through the machine, this being one of the elementary operations of the machine. Any symbol on the tape may therefore eventually have an innings[2]. (Turing 1948, p. 61)
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 lambda calculus intertwined with Turing's in a formal theory of computation known as the Church–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'.

Hopcroft and Ullman (1979, p. 148) formally define a (one-tape) Turing machine as a 7-tuple where Q is a finite set of states Γ is a finite set of the tape alphabet/symbols is the blank symbol (the only symbol allowed to occur on the tape infinitely often at any step during the computation) is the set of input symbols is a partial function called the transition function, where L is left shift, R is right shift. (A relatively uncommon variant allows "no shift", say N, as a third element of the latter set.) is the initial state is the set of final or accepting states. Anything that operates according to these specifications is a Turing machine. The 7-tuple for the 3-state busy beaver looks like this (see more about this busy beaver at Turing machine examples):
Q = { A, B, C, HALT }
Γ = { 0, 1 }
b = 0 = "blank"
Σ = { 1 }
δ = see state-table below
q0 = A = initial state
F = the one element set of final states {HALT}

-Examples of Turing machines

Example 1: Complement function

Symbols = {0, 1} and {B}States = {0, 1}End States = {1} 00 01R; When reading a "0" write a "1", move ahead01 00R; When reading a "1" write a "0", move ahead0B 1BS; When reading a blank (end of the string) change state to an End State. That’s all, the head travels through the tape turning each “0″ it finds to “1″ and each “1″ to “0″, Once it reads a blank the state changes to “finalize”.

Example 2: Marbles addition

The model input chain will be “11….111+111….1111″ and the result will have to be the addition of both sides of the “+” symbol. It’s equivalent to having two bowls filled with marbles, and having to determine the total number by placing all of them together. It’s quite simple too. Symbols = {1, +} and {B}States = {0, 1, 2}End States = {2} 01 01R; As long as there are only “1″ move to the right, don’t change anything0+ 01R; Found the sign, set it to “1″ (dirty trick)0B 1BR; Finished travelling the string; let’s erase the last “1″ because it was lent at the sign11 2BS; At state “1″ we know the end was already reached. When we find the first “1″ we delete it and set an End State (we’re done).

Example 3: Identify a pattern

This function is what is known as “decision”; it should set an end state if what was asked resulted true, and a different one if it was false. In this case the function will answer the question, “Does the input string has a pattern formed by a number of a symbol “0″ and exactly the same number of “1″ following it”?; for example, “0011″ returns “yes”, “0100″ returns “no”, “11110000″ returns “no”, etc.

Symbols = {0, 1, x, y, z} and {B}

States = {0, 1, 2, 3, 4, YES, NO}

End States = {YES, NO}

; Initial functions

00 1xR; Replace “0″ by “x” as a mark, move ahead01 NO;

the string begins with a “1″… Can’t match, end right away

; Move functions

10 10R; Found a “0″ right after another, keep travelling right until finding a “1″1y 1yR; Found a “y” after a “0″, it’s an already marked “1″, skip2y 2yL; Same as “1y”, but we’re travelling to the left in state 2 (see “11″)3y 3yR; Same as “1y”40 40L; See “20″, just go on to find the corner and the first “0″.

; Misc.

11 2yL; Found the first “1″ available when going to the right, mark it, turn around2x 3xR; Got an “x” mark when going to the left; turn around (it’s as good as the left side limit of the string)20 40L; Found the first “0″ while traveling to the left. Just go on until finding an “x” mark.4x 0xR; Just like on “00″, but after a few turns.

; End conditions

3B YES; The whole string is marked, get here from natural “10″, “1y” and “3y” conditions.31

NO; We found a “1″ when looking for a “0″, there are more “1″ than “0″ or the string is interleaved.01 NO; The string begins with a “1″, see above in “initial functions”.

How does it work: Find a “0″, mark it “x”; find a “1″, mark it “y”; repeat the process until running out of “0″, in that case, if there’s still a “1″ unmarked, answer “NO”; if we run out of “1″ first, we find that the program is incomplete (tee hee - not my program…); if only marks or a B can be found, answer “YES”.

**Variants of Turing Machine**

-Multitape Turing Machine

In practical analysis, various types of multi-tape Turing machines are often used. Multi-tape machines are similar to single-tape machines, but there is some constant k number of independent tapes. The TABLE has full independent control over all the heads, any of all of which move and print/erase their own tapes (cf Aho-Hopcroft-Ullman 1974 p. 26). Most models have tapes with left ends, right ends unbounded. This model intuitively seems much more powerful than the single-tape model, but any multi-tape machine, no matter how large the k, can be simulated by a single-tape machine using only quadratically more computation time (Papadimitriou 1994, Thrm 2.1). Thus, multi-tape machines cannot calculate any more functions than single-tape machines, and none of the robust complexity classes (such as polynomial time) are affected by a change between single-tape and multi-tape machines.

-Nondeterministic Turing Machine

A non-deterministic Turing machine (NTM), by contrast, may have a set of rules that prescribes more than one action for a given situation. For example, a non-deterministic Turing machine may have both "If you are in state 2 and you see an 'A', change it to a 'B' and move left" and "If you are in state 2 and you see an 'A', change it to a 'C' and move right" in its rule set. An ordinary (deterministic) Turing machine (DTM) has a transition function that, for a given state and symbol under the tape head, specifies three things: the symbol to be written to the tape, the direction (left or right) in which the head should move, and the subsequent state of the finite control. For example, an X on the tape in state 3 might make the DTM write a Y on the tape, move the head one position to the right, and switch to state 5. A non-deterministic Turing machine (NTM) differs in that the state and tape symbol no longer uniquely specify these things; rather, many different actions may apply for the same combination of state and symbol. For example, an X on the tape in state 3 might now allow the NTM to write a Y, move right, and switch to state 5 or to write an X, move left, and stay in state 3.

-Enumerators

Enumerators is a Turing Machine with an output printer. The Turing Machine can use the printer as an output device to print strings.

-Equivalence with Other Models

Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p. 159, cf Minsky). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the Church-Turing thesis hypothesizes this to be true: that anything that can be “computed” can be computed by some Turing machine.)

While none of the following models have been shown to have more power than the single-tape, one-way infinite, multi-symbol Turing-machine model, their authors defined and used them to investigate questions and solve problems more easily than they could have if they had stayed with Turing's a-machine model.

Context-Free Language

I. Context-Free Grammars

# Formal Definition of Context-Free Grammars

A context-free grammar is a grammar in which the left-hand side of each production rule consists of only a single nonterminal symbol. This restriction is non-trivial; not all languages can be generated by context-free grammars. Those that can are called context-free languages.

The language defined above is not a context-free language, and this can be strictly proven using the pumping lemma for context-free languages, but for example the language (at least 1 a followed by the same number of b's) is context-free, as it can be defined by the grammar G₂ with , , S the start symbol, and the following production rules:

1.

2.

A context-free language can be recognized in O(n³) time (see Big O notation) by an algorithm such as Earley's algorithm. That is, for every context-free language, a machine can be built that takes a string as input and determines in O(n³) time whether the string is a member of the language, where n is the length of the string.^[7] Further, some important subsets of the context-free languages can be recognized in linear time using other algorithms.

# Examples of Context-Free Grammars

For these examples, formal languages are specified using set-builder notation.

Consider the grammar G where , , S is the start symbol, and P consists of the following production rules:

1.

2.

3.

4.

Some examples of the derivation of strings in are:

• 
• 
• 

(Note on notation: reads "String P generates string Q by means of production i", and the generated part is each time indicated in bold type.)

This grammar defines the language where aⁿ denotes a string of n consecutive a's. Thus, the language is the set of strings that consist of 1 or more a's, followed by the same number of b's, followed by the same number of c's.

# Designing a Context-Free Grammars

Designing Context-Free Grammars.
• Some basic techniques:
– Matching – enforcing the fact that your grammar generates matching pairs of
symbols.
Example: L = {0n12n n ≥ 0}. The context-free grammar for L is
S → 0S11 "
The grammar forces every 0 to match to 11.
What about L = {0n1m 2n ≤ m ≤ 3n} ?
Another example: L = {w w ∈ {0, 1} and of even length }.
S → 0S0 0S1 1S0 1S1 "
The grammar forces every symbol to match to another symbol.
– Using recursive relationships – when you can represent strings in the language in
terms of shorter strings in the language.
Example: L – the language of all strings of balanced brackets. For example,
(()())() ∈ L, but (() /∈ L.
Every string w in L can be viewed as either
- uv, for u ∈ L, v ∈ L, or
- (u), for u ∈ L.
This gives the following grammar:
S → SS (S) "
– 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.
Example: L = {0n1m n 6= m}.
Let L1 = {0n1m n > m}, and L2 = {0n1m n <>

# Ambiguity

If a CFG generates the same string in several different ways, we say that the string is derived ambiguously in that grammar. If a CFG generates some string ambiguously we say that the grammar is ambiguous.

Example: the grammar G5, whose rules are:
E −→ E + E E ∗ E (E) a

generate ambiguously some arithmetic expressions.

# 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

Sε

where A, B and C are nonterminal symbols, α is a terminal symbol (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.

Every grammar in Chomsky normal form is context-free, and conversely, every context-free grammar can be transformed into an equivalent one which is in Chomsky normal form. Several algorithms for performing such a transformation are known. Transformations are described in most textbooks on automata theory, such as (Hopcroft and Ullman, 1979). As pointed out by Lange and Leiß, the drawback of these transformations is that they can lead to an undesirable bloat in grammar size. Using G to denote the size of the original grammar G, the size blow-up in the worst case may range from G ² to 2^{2 G} , depending on the used transformation algorithm (Lange and Leiß, 2009).

Another way to define Chomsky normal form (e.g., Hopcroft and Ullman 1979, and Hopcroft et al. 2006) is:

A formal grammar is in Chomsky normal form if all of its production rules are of the form:

ABC or

Aα

where A, B and C are nonterminal symbols, and α is a terminal symbol. When using this definition, B or C may be the start symbol.

             II. Pushdown Automata  

# Formal Definition of a Pushdown a Automation

A PDA is formally defined as a 7-tuple:

where

• is a finite set of states
• is a finite set which is called the input alphabet
• is a finite set which is called the stack alphabet
• is a finite subset of , the transition relation.
• is the start state
• is the initial stack symbol
• is the set of accepting states

An element is a transition of . It has the intended meaning that , in state , with on the input and with as topmost stack symbol, may read , change the state to , pop , replacing it by pushing . The letter (epsilon) denotes the empty string and the component of the transition relation is used to formalize that the PDA can either read a letter from the input, or proceed leaving the input untouched.

In many texts the transition relation is replaced by an (equivalent) formalization, where

• is the transition function, mapping into finite subsets of .

Here contains all possible actions in state with on the stack, while reading on the input. One writes for the function precisely when for the relation. Note that finite in this definition is essential.

# Examples of Pushdown Automation

The following is the formal description of the PDA which recognizes the language by final state:

PDA for (by final state)

, where

consists of the following six instructions:

, , , , , and .

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

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

# Equivalence with Context-Free Grammars

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