Introduction to Computability Theory
Turing Machines
Prof. Amos Israeli
1
Introduction and Motivation
In this lecture we introduce Turing Machines and discuss some of their properties.
2
Turing Machines
A Turing Machine is a finite state machine augmented with an infinite tape.
The tape head can go in both directions. It can read and write from/to any cell of the semi-infinite tape.
Once the TM reaches an accept (reject resp.) state it accepts (rejects resp.) immediately.
3
Schematic of a Turing Machine
The tape head can go in both directions. It can read and write from/to any cell of the semi-infinite tape. The _ symbol marks the input’s end.
4
Finite control
a
b
a
a
c
input
_
_
_
TM – A Formal Definition
A Turing Machine is a 7-tuple , where:
5
TM – A Formal Definition
A Turing Machine is a 7-tuple , where:
6
The Transition Function - Domain
Let M be a Turing machine defined by � . at any given time M is in some state, , and its head is on some tape square containing some tape symbol .�The transition function , depends on the machine state q and on the tape symbol .
7
The Transition Function - Range
The range of the transition function are triples of the type , where is M’s next state, is the symbol written on the tape cell over which the head was at the beginning of the transition (namely is replaced with ) and is the direction towards which the tape head has made a step.
8
Turing machine – A Computation
Computation of M always starts at state , and the input is on the leftmost n cells where n is the input’s length. The tape’s head is over the tape’s cell 0 – the leftmost cell.
Computation of M ends either when it reaches� - this is an Accepting Computation. Or when it reaches - this is a Rejecting Computation.
9
Configurations
A configuration of a Turing machine M is a concise description M’s state and tape contents. It is written as C=uqv . and its meaning is:
10
Configurations
Configuration of M yields Configuration , if� M can legally go from to in a single step.�For example: �Assume that , , and .�We say that yields , if , for a leftward movement of the head.�We say that yields , if , for a rightward movement of the head.
11
Configurations – Special Cases
Configuration yields , if the head is at the beginning of the tape and the transition is left-moving, because the head cannot go off the left-hand end of the tape.
Configuration is equivalent to , because the empty part of the tape is always filled out with blanks.
12
Computations
The start Configuration of M on input w is , which indicates that M is at its initial state, ,�it’s head is on the first cell of its tape and the tape’s content is the input w.
Any configuration in which of M reaches state � , is an accepting configuration.
Any configuration in which M reaches state� ,is a rejecting configuration.
13
Computations
Accepting and rejecting configurations are halting configurations.
A TM M accepts word w if there exists a computation (a sequence of configurations) of M, satisfying:
14
Computation Outcomes
A Computation of a Turing machine M may result in three different outcomes:
Note: When M is running, it is not clear whether it is looping . Meaning M may stop eventually but nobody can tell.
15
Turing Recognizers
The collection of strings that M accepts is the language of M , denoted .
A language is Turing Recognizable if there exists a Turing machine that recognizes it.
16
Turing Deciders
Since it is hard to tell whether a running machine is looping, we prefer machines that halt on all inputs. These machines are called deciders.
A decider that recognizes a language L is said to decide L.
A language is Turing decidable if there exists a Turing machine that decides it.
17
An Example
Consider the language containing strings of 0-s whose length is an integral power of 2.
Obviously, the language L is neither regular nor CFL (why?).
In the next slide we present a high level description of TM to decide L. The description format follows the text book.
18
An Example
“On input string w:�1. Sweep the tape left to right, crossing every � second 0.�2. If in stage 1 the tape has a single 0, accept.�3. If in stage 1 the tape has an odd number of � 0-s greater than 1, reject. �4. Return the head to the left-hand end of the � tape.�5. Go to stage 1. “
19
Explanation
works as follows:�Each iteration of stage 1 cuts the number of 0-s in half. As the sweeps across its tape on stage 1 it “calculates” whether the number of 0-s it sees is odd or even. If the number of 0-s is odd and greater than 1, the input length cannot be a power of 2, so it rejects. If the number of 0-s is 1, the input length is a power of 2 and it accepts.
20
An Example
In the following slide the transition function of � is presented. �Note: , .
21
An Example
22
Example2
Consider the language .�A simple method to check whether a string w is in L is: Read the first character of w, store it, and mark it off. Then scan w until the character # is found, if the first character past # is equal to the stored character, cross it and go back to the last crossed character, On the tape’s beginning.
23
Example2
Repeat this procedure until all the string w is scanned. If an unexpected character is found, reject. Otherwise, accept.
In the next slide we present a high level description of TM to decide L. The description format follows the text book.
24
Example2
“On input string w:�1. Store the leftmost symbol on the tape and cross it out by writing x.�2. Go right past #, if # not found, reject. �3. compare the leftmost non x symbol to the � stored symbol. If not equal, reject. �4. Cross out the compared symbol. Return the � head to the left-hand end of the tape. �5. Go to stage 1. “
25
Example2
In the following slide the transition function of � is presented.
Note:
1. , .
2. In this description, state and all its incoming transitions are omitted. Wherever there is a missing transition, it goes to .
26
27
Example2
Note: states and “store” the bit 0, while states and “store” the bit 1.� In other words: These two segments are identical, but when the merge each segments uses the value it stored.�
28
Introduction and Motivation
There are many alternative definitions of Turing machines. Those are called variants of the original Turing machine. Among the variants are machines with many tapes and non deterministic machines.
29
Introduction and Motivation
A computational model is robust if the class of languages it accepts does not change under variants.
We have seen that DFA-s are robust for non determinism.
The robustness of Turing Machines is by far greater than the robustness of DFA-s and PDA-s.
30
Introduction and Motivation
In this lecture we introduce several variants on Turing machines and show that all these variants have equal computational power.
In fact: All the “reasonable” variants have the same computational power.
31
Introduction and Motivation
When we prove that a TM exists with some properties, we do not deal with questions like:�How large is the TM?�Or �How complex is it to “program” that TM?�At this point we only seek existential proofs.
32
Example: Stayers1
A Stayer is Turing Machine whose head can stay on the same tape cell in a transition. The definition of the transition function for such a machine looks like this: , where s stands for staying.
1. This is a special name only for this lecture
33
Stayer Power Equal to Ordinary TM
We say that the computational power of two models is equal if they recognize the same class of languages.
Since each normal TM can be easily simulated by a “stayer which chooses not to stay”, the computational power of a stayer is at least as strong as the power of a normal machine.
34
Stayer Power Equal to Ordinary TM
In order to prove that the computational power of a stayer is not greater than the power of a normal machine we show that for any stayer there exists a normal TM recognizing the same language. The easiest way to prove this is to assume that M is a stayer and to present an ordinary TM M’ that simulates M.
35
Simulation of Stayer-s
The machine M’ is defined just like M, except that each staying transition of M is replaced by a double transition in which M’ first goes to a special additional state while moving its head right and then returns to the original state while moving its head left.
36
Simulation of Stayer-s
Now, It is very easy to prove that M and M’ recognize exactly the same language. In fact, computations of M’ are very similar to computations of M, and M’ is said to simulate M.
In general, when we want to prove that two variants have the same power we show that they can simulate each other.
37
Implementing Memory
In many occasions a TM is required to store information that it reads from its tape. Recall that we encountered similar situations when designed DFA-s or NFA-s. The way we tackled these problems was to use states in order to store the information. Here we adopt the same technique:
38
Implementing Memory (cont.)
Assume for instance that TM M needs to read the first 2 input bits from its tape and write these bits beyond the input’s end, where the two leftmost blanks are. One way to do this is to start by devising a TM M’ that reads the first 2 input bits, searches for the input’s left end and write 00 there.
39
Implementing Memory (cont.)
Once M’ is devised we can proceed as follows:
40
Implementing Memory (cont.)
Note: This technique can be used to store any finite amount of data.
For Example: If we want M to store a sequence of k symbols of , we should copy M times. A copy for each possible sequence, and move to the replica corresponding the sequence read while scanning it.
41
Multitape Turing Machines
A multitape Turing machine is an ordinary Turing machine with several tapes. Initially, the input appears on tape 1 and the other tapes are blank. The transition function allows each head to behave independently:
�where k is the number of tapes.
42
Multitape Turing Machines
The expression:
�means that if the k – tape machine M is at state , and head i, , reads symbol � , then the new state of M is , the new symbol written by head i is and head i, moves in the designated direction.
43
Multitape Turing Machines
Multitape TM-s appear to be stronger than ordinary TM-s. The following theorem shows that these two variants are equivalent.
Theorem
Every multitape TM has an equivalent single-tape TM.
44
Proof
Say that M is a k- tape machine. Now we present an ordinary TM S that simulates M: The TM S stores the content of M’s k tapes on its single tape, one after the other. Every pair of consecutive tape contents are separated by a special tape symbol of S, say #, which does not belong to M’s tape alphabet.
45
Proof (cont.)
In order to keep the location of head i, �we do the following: Let be a tape alphabet symbol of M. The TM S has two symbols corresponding to , denoted by and . The “.” signals that the head of the tape on which resides is above the symbol � . A pictorial description on the next slide.
46
Simulating Three Tapes by One
47
v
1
#
1
a
b
#
u
_
#
Finite control of� M
Tape1
a
_
b
_
_
_
_
u
_
v
_
_
_
_
1
_
1
_
_
_
_
_
_
_
Finite control of� S
Tape2
Tape3
Description of S
The observers of this proof should verify to themselves that all steps can be carried out by an ordinary TM.
Recall that M gets its input on its first tape and the other tapes are blank.
Here we assume that S gets M’s input on its single tape.
48
Description of S
TM S starts its simulation of M, by preparing its tape to the described format. The tape should look like this:���Note that the leftmost blank on S’s tape appears right after the k+1 instance of #.
49
.
#
_
#
.
.
#
#
tape1
tape2
tapes 3-k
Description of S (cont.)
After preparing the its tape S proceeds to scan its tape from the beginning to the first blank. During this scan S “stores” (in the way described previously) all k symbols on which its k heads reside.
Following that S makes a second pass to update its tapes according to M’s transition function.
50
Description of S (cont.)
In its second pass S writes over all doted symbols and “moves the dots” to the new locations of the respective k heads.
In case a one of M’s heads moves to the rightmost blank on its tape, the virtual head (dot) on S’s corresponding tape segment would end up on the delimiting # .
51
Description of S (cont.)
In this case, S should shift the entire suffix of its tape, starting from the dotted delimiting # and ending on the k+1 #, one step right.
After this shift is completed, S writes a “dotted blank” symbol where the # symbol previously resided.
52
Description of S (cont.)
Following the update of its tape, including the necessary shifts, S returns to its first tape cell and assumes a state corresponding to M’s next state.
53
Corollary
A language is Turing-recognizable if and only if some multitape Turing machine recognizes it.
Proof: A Turing-recognizable language is recognized by an ordinary (single tape) TM which is a special case of a multitape TM. This proves one direction.
The other direction follows from the Theorem.
54
Nondeterministic Turing Machines
The transition function of a Turing machine:
The transition function of a Nondeterministic Turing machine:
This definition is analogous to NFA-s and PDA-s.
55
Computations of Nondet. TM-s
Each computation of a Nondeterministic Turing machine is a tree, where each branch of the tree is looks like a computation of an ordinary TM.
If a single branch reaches the accepting state – the Nondeterministic machine accepts, even if other branches reach the rejecting state.
56
Power of Nondeterministic TM-s
Nondeterministic TM-s appear to be stronger than ordinary TM-s. The following theorem shows that these two variants are equivalent.
Theorem
Every Nondeterministic TM has an equivalent deterministic (ordinary) TM.
57
Proof
We look at N’s computation as a (possibly infinite) tree whose nodes are configurations of N. Each branch of the tree represents a possible computation of N with input w. We will show that there exists an ordinary Turing machine D that simulates N.
58
Proof (cont.)
The idea of the proof is that for each input w, D should go through all possible computations of N with w and accept only if N accepts on any of its computations. Otherwise N loops.
59
Proof (cont.)
Some of N’s computations may be infinite, hence its computation tree has some infinite branches.
If D starts its simulation by following an infinite branch D may loop forever even though N’s computation may have a different branch on which it accepts.
60
Proof (cont.)
In order to avoid this unwanted situation, we want D to execute all of N’s computations simultaneously.
To do that, D goes on N’s computation tree in a BFS ordering, as detailed in the next slide:
61
Proof (cont.)
…
i. Execute the first i steps of all computations. If any of them accepts – accept.
62
Proof (cont.)
The actual simulation is carried out by a 3-tape TM D.
Recall that we just showed that any 3-tape machine can be simulated by an ordinary TM.
The 1st tape of D holds the input for N.
The 2nd and third tapes are blank.
63
Proof (cont.)
The simulation of N by D proceeds as follows:
64
Proof (cont.)
In order to complete the simulation’s description we have to explain how the “computation line” is kept:
Since N is nondeterministic, it has some configurations in which it has several possible transitions:
65
Proof (cont.)
For every configuration of N, TM D encodes all possible N’s transitions and all these transitions are enumerated.
Let b be the largest number of transitions out of any of N’s configurations.
66
Proof (cont.)
Let be an i prefix of some computation of N on some input I. can be encoded by a string of i b-ary digits, as follows:
TM N starts is in its initial configuration. Digit �is the number of the actual transition made by N on its 1st step of .
67
Proof (cont.)
For , is the number of the actual transition made by N on its jth step of � . �
68
Proof (cont.)
For example: The string 421 encodes a prefix of length 3 in which on the 1st step N takes the 4th enumerated choice, on its second step it takes the 2nd enumerated choice and on its third step it takes the 1st enumerated choice.
Note: Some configurations may have less b choices, hence not every b-ary number represents a computation prefix.
69
Proof (cont.)
The simulation of N by D proceeds as follows:
70
The Church-Turing thesis
In this lecture we showed several variants of TM-s are equivalent. Over the years it has been proved that many similar and even not so similar computational models are equivalent, namely they have the same computational power. One particular model is called -calculus of Church.
71
The Church-Turing thesis
The -calculus of Church and Turing machines are the first 2 formal models for a mathematical notion that was informal, intuitive and vague for centuries:
The notion of an
A L G O R I T H M
72
The Church-Turing thesis
Furthermore: It has been shown that these two definitions are equivalent:
The Church Turing Thesis says that
Intuitive Notion of Algorithm �equals
Turing Machines or -Calculus
73