Turing Machines

A Turing machine is similar to a finite automaton with

supply of unlimited memory. 22c:135 Theory of Computation
A Turing machine can do everything that any computing
device can do. Hantao Zhang
http://www.cs.uiowa.edu/∼ hzhang/c135
There exist problems that even a Turing machine
cannot solve. The University of Iowa
Department of Computer Science

Theory of Computation – p.2/?? Theory of Computation – p.1/??

TM versus FA, PDA Tape of a Turing Machine (TM)

1. write: A TM can both write on the tape and read from it; Memory is modeled by a tape of symbols.
The input tape is read-only and the head moves from Initially the tape contains only the input string and is
left to right. blank everywhere else.
The stack tape can be write and read: when the head
moves right, it writes; when the head moves left, it If a TM needs to store info, it may write on the tape.
erases the current symbol. To read the info that it has written, TM can move its
2. size: The tape of a TM is infinite; the input tape of FA head back.
and PDA is finite; the stack tape of PDA is infinite. TM continues to move until it enters a state whose next
3. accept: FA and PAD accept a string when it has scanned move is not defined.
all the input symbols and enters a final state; TM
accepts a string as long as it enters a final state (one
suffices).

Theory of Computation – p.4/?? Theory of Computation – p.3/??

 Example TM computation Example TM computation
Construct a TM M1 that tests the membership in the Construct a TM M1 that tests the membership in the
language L1 = {w#w | w ∈ {0, 1}∗ } language L1 = {w#w | w ∈ {0, 1}∗ }
In other words: we want to design M1 such that
s0 : if first symbol is 0 or 1, replace it by x, remember it as
a; if it is #, goto s5 ; else reject; M1 (w) = accept iff w ∈ L1

s1 (a): move right until #; if no # before ⊔, reject;

s2 (a): move right until 0 or 1; if the current symbol is the
same as a, then replace it by x; else reject;
s3 : move left until #;
s4 : move left until x and goto s0 ;
s5 : move right until 0, 1, or ⊔; accept if ⊔; reject if 0, 1.

Theory of Computation – p.6/?? Theory of Computation – p.5/??

Computations Formal definition

M = (Q, Σ, Γ, δ, q0 , qaccpt , qreject ) computes as follows: A Turing machine is a 7-tuple
M receives as input w = a1 a2 . . . an ∈ Σ∗ , ai ∈ Σ, written on the M = (Q, Σ, Γ, δ, q0 , qaccpt , qreject ) where Q, Σ, Γ are finite sets
leftmost squares of the tape and the rest of the tape is blank (i.e., and
filled with ⊔) 1. Q is a set of states
The head starts on the leftmost square of the tape. 2. Σ is the input alphabet and ⊔ 6∈ Σ
The first blank encountered shows the end of the input. 3. Γ is the tape alphabet, ⊔ ∈ Γ, Σ ⊂ Γ
Once it starts, it proceeds by the rules defined by δ. 4. δ : Q × Γ → Q × Γ × {L, R} is the transition function
If M ever tries to move to the left of the leftmost square the head 5. q0 ∈ Q is the initial state
stays in the leftmost square even though δ indicate L. 6. qaccept ∈ Q is the accept state (sometimes denoted qa )
The computation continues until M cannot move; if M enters qaccept , 7. qreject ∈ Q is the reject state (sometimes denoted qr )
the input string is accepted. M may go on forever as long as δ is
defined.
Note: qreject is optional in the definition.

Theory of Computation – p.8/?? Theory of Computation – p.7/??

 Example TM computation Example TM computation
s3 : move left until #; s0 : if first symbol is 0 or 1, replace it by x, remember it as
δ(s3 , a) = hs3 , a, Li, where a ∈ {0, 1, x}, δ(s3 , #) = hs4 , #, Li a; if it is ⊔, goto s5 ; else reject;
s4 : move left until x and goto s0 ; δ(s0 , 0) = hs1 (0), x, Ri, δ(s0 , 1) = hs1 (1), x, Ri, δ(s0 , #) =
δ(s4 , a) = hs4 , a, Li, where a ∈ {0, 1}, δ(s4 , x) = hs0 , x, Ri hs5 , x, Ri

s5 : move right until 0, 1, or ⊔; accept if ⊔; reject if 0, 1. s1 (a): move right until #; if no # before ⊔, reject;
δ(s5 , x) = hs5 , x, Ri, δ(s5 , ⊔) = hsa , ⊔, Li δ(s1 (a), 0) = hs1 (a), 0, Ri, δ(s1 (a), 1) =
hs1 (a), 1, Ri, δ(s1 (a), #) = hs2 (a), #, Ri
s2 (a): move right until 0 or 1; if the current symbol is the
same as a, then replace it by x; else reject;
δ(s2 (a), x) = hs2 (a), x, Ri, δ(s2 (0), 0) =
hs3 , x, Li, δ(s2 (1), 1) = hs3 , x, Li;

Theory of Computation – p.10/?? Theory of Computation – p.9/??

Formalizing TM computation Configuration

A configuration C1 yields a configuration C2 if the TM can A configuration C of M is a tuple C = hu, q, vi, where q ∈ Q,
legally go from C1 to C2 in a single computation step uv ∈ Γ∗ is the tape content and the head is pointing to the
Formally: suppose a, b, c ∈ Γ, u, v ∈ Γ∗ and qi , qj ∈ Q. first symbol of v .
1. We say that ua qi bv yields uac qj v if Configurations are used to formalize machine
δ(qi , b) = (qj , c, R); (machine moves rightward) computation and therefore are represented by special
2. We say that ua qi bv yields u qj acv if symbols.
δ(qi , b) = (qj , c, L); (machine moves leftward) Tape contains only ⊔ following the last symbol of v .

Theory of Computation – p.12/?? Theory of Computation – p.11/??

 Example 2 Head at one input end
n
M2 is a Turing machine that decides A = {02 | n ≥ 0}. Given M = (Q, Σ, Γ, δ, q0 , qaccpt , qreject )
some elementary
M2 ="On input string w For the left-hand end:
the configuration qi bv yields qj cv if the transition is left moving,
1. Sweep left to right across the tape, crossing off every other 0; if the
i.e., δ(qi , b) = (qj , c, L)
number of 0 is odd, reject;
the configuration qi bv yields c qj v for the right moving transition,
2. If in stage 1 the tape contained a signle 0, accept.
i.e., δ(qi , b) = (qj , c, R)
3. Return the head to the left-hand end of the tape.
For the right-hand end:
4. Go to stage 1.”
the configuration ua qi is equivalent to ua qi ⊔ because we
assume that blanks follow the part of the tape represented in
configuration. Hence we can handle this case as the previous

Theory of Computation – p.14/?? Theory of Computation – p.13/??

Special configurations Example 2

If the input of M is w and initial state is q0 then q0 w is 1. Sweep left to right across the tape, crossing off every other 0; if the
the start configuration number of 0 is odd, reject;
(a) Mark the first 0 by ⊔: δ(q1 , 0) = hq2 , ⊔, Ri
ua qaccept bv is called accepting configuration
(b) Cross off the next 0 after ⊔: δ(q2 , 0) = hq3 , x, Ri
ua qreject bv is called rejecting configuration
(c) Pass 0 at odd position; cross off 0 at even position.
Accepting and rejecting configurations are also called δ(q3 , 0) = hq4 , 0, Ri, δ(q4 , 0) = hq3 , x, Ri, δ(q, x) = hq, x, Ri for
halting configurations q ∈ {q2 , q3 , q4 }.
(d) If the number of 0 is odd, reject: (δ(q4 , ⊔) = hqr , ⊔, Ri)
2. If in stage 1 the tape contained a signle 0, accept: δ(q2 , ⊔) = hqa , ⊔, Ri
3. Return the head to the left-hand end of the tape: δ(q3 , ⊔) = hq5 , ⊔, Li,
δ(q5 , a) = hq5 , a, Li for a ∈ {0, x}.
4. Go to stage 1 (b): δ(q5 , ⊔) = hq2 , ⊔, Ri.

Theory of Computation – p.16/?? Theory of Computation – p.15/??

 Language of M Accepting an input w
L(M ) = {w ∈ Σ∗ | M accepts w} A Turing machine M accepts the input w if a sequence of
configurations C1 , C2 , . . . , Cn exists such that:
Turing-recognizable language:A language L is 1. C1 is the start configuration, C1 = (ǫ, q0 , w)
Turing-recognizable if there is 2. Each Ci yields Ci+1 , i = 1, 2, . . . , n − 1
a Turing machine M that recognizes it. 3. Cn is an accepting configuration.

Theory of Computation – p.18/?? Theory of Computation – p.17/??

Fail to accept Note

TM fails to accept w by entering qreject and thus When we start a TM on an input w three cases can happen:
rejecting, or by looping 1. TM may accept w
Sometimes it is difficult to distinguish a machine that fail 2. TM may reject w
to accept from one that merely takes long-time to halt.
3. TM may loop indefinitely, i.e., TM does not halt.

Note:looping does not mean that machine repeats the same steps over
and over again; looping may entail any simple or complex behavior that
never leads to a halting state.

Question: is this real? I.e., can you indicate a computation that takes infinite

many steps without repetition?

Theory of Computation – p.20/?? Theory of Computation – p.19/??

 Turing-decidability Decider
A decider that recognizes some language is also said to A TM that halts on all inputs is called a decider.
decide that language
A language is called Turing-decidable or simple
decidable if some TM decides it.

Theory of Computation – p.22/?? Theory of Computation – p.21/??

Higher Level Descriptions Note

We can give a formal description of a particular TM by Any regular language is Turing-decidable.
specifying each of its seven components Any context-free language is Turing-decidable.
Defining δ can become cumbersome. To avoid this we Every decidable language is Turing-recognizable (a
use higher level descriptions which are precise enough language is Turing-recognizable if it is recognized by a
for the purpose of understanding TM).
We want be sure that every higher level description is Certain Turing-recognizable languages are not
actually just a short hand for its formal counterpart. decidable (to be decidable means to be decided by a
TM which halts on all inputs)

Theory of Computation – p.24/?? Theory of Computation – p.23/??

 Analyzing M3 Example 3
In stage 1 M3 operates as a finite automaton; no writing M3 is a Turing machine that performs some elementary
is necessary as the head moves from left to right: arithmetic. It decides the language
1. δ(q0 , ⊔) = (qa , ⊔, R), δ(q0 , b) = (q4 , b, R) C = {ai bj ck | i × j = k, i, j, k ≥ 0}
2. δ(q0 , a) = (q1 , A, R),δ(q1 , b) = (q2 , b, R), δ(q1 , ⊔) = (qa , ⊔, R)
M3 ="On input string w
3. δ(q2 , b) = (q2 , b, R), δ(q2 , c) = (q3 , c, R)
1. Scan the input from left to right to be sure that it is a member of
4. δ(q3 , c) = (q3 , c, R)
a∗ b∗ c∗ ; reject if it is not; accept if it is ǫ, a+ or b+ .
5. δ(q4 , b) = (q4 , b, R), δ(q4 , ⊔) = (qa , ⊔, R),
2. Set the head pointing at the first a on the tape
3. Cross off an a and scan to the right until a b occurs. Shuttle between
the b’s and c’s crossing off one of each until all b’s are gone
4. Restores the crossed off b’s and repeat stage 2 if there is another a
to cross off. If all a’s are crossed off, check on whether all c’s are
crossed off. If yes accept, otherwise reject."

Theory of Computation – p.26/?? Theory of Computation – p.25/??

Stage 3 cross a Stage 2 finding the first a

δ(q5 , A) = (q6 , ⊔, R) δ(q3 , ⊔) = (q5 , ⊔, L)
δ(q6 , a) = (q7 , A, R) δ(q5 , x) = (q5 , x, L) for x ∈ {a, b, c}
δ(q6 , b) = (q8 , b, L), δ(q8 , ⊔) = (q7 , E, R)
δ(q7 , a) = (q7 , a, R), δ(q7 , B) = (q7 , B, R),
δ(q7 , b) = (q9 , B, R)
δ(q9 , b) = (q9 , b, R), δ(q9 , C) = (q9 , C, R),
δ(q9 , c) = (q10 , C, L)

Theory of Computation – p.28/?? Theory of Computation – p.27/??

 Example 4 Element distinctness problem
M4 = (Q, Σ, Γ, δ, qs , qa , qr ) is the TM that solves the element Given a list of strings over {0, 1} separated by #, determine
distinctness problem if all strings are different.
A TM that solves this problem accepts the language
M4 works by comparing x1 with x2 , . . . , xk , then by comparing
E = {#x1 #x2 # . . . #xk | xi ∈ {0, 1}∗ , xi 6= xj f or i 6= j}
x2 with x3 , . . . , xk , and so on

Theory of Computation – p.30/?? Theory of Computation – p.29/??

Marking tape symbols Informal description

In stage two the machine places a mark above a M4 ="On input w :
symbol, # in this case. 1. Place a mark on top of the leftmost tape symbol. If that symbol was a
In the actual implementation the machine has two blank, accept. If that symbol was a # continue with the next stage.
• Otherwise reject.
different symbols, # and # in the tape alphabet Σ
2. Scan right to the next # and place a second mark on top of it. If no #
Thus, when machine places a mark above symbol x it is encountered before a blank symbol, only xk was present, so accept
actually write the marked symbol of x at that location
3. By zig-zagging, compare the two strings to the right and to the left of
Removing the mark means write the symbol at the the marked #. If they are equal, reject
location where the marked symbol was.
4. Move the rightmost of the two marks to the next # symbol to the
Assumption: all symbols of the tape alphabet have right. If no # symbol is encountered before a blank symbol, move the
marked versions too leftmost mark to the next # to its right and the rightmost mark to the
# after that. This time if no # is available for the rightmost mark, all
strings have been compared, so accept.
5. Go to stage 3"
Theory of Computation – p.32/?? Theory of Computation – p.31/??
 Standardizing our model High level operations of TMs
Question: what is the right level of detail to give when Compare if two strings are the same or not.
describing a Turing machine algorithm? Compute the addtion, substraction, multiplication,
division, power, log, etc. of numbers in unary form.
Note: this is a common question asked especially when
Shift a string right (or left).
preparing solutions to various problems such as exercises
Maintain a base-b counter.
and problems given in assignments and exams during the
process of learning Theory of Computation

Theory of Computation – p.34/?? Theory of Computation – p.33/??

Equivalence of TMs Answer

To show that two models of TM are equivalent we need to The three possibilities are:
show that we can simulate one by another. 1. Formal description: spells out in full all 7 components of a Turing
machine. This is the lowest, most detailed level of description.
2. Implementation description: use English prose to describe the way
Turing machine moves its head and the way it stores data on its tape.
No details of state transitions are given
3. High-level description: use English prose to describe the algorithm,
ignoring the implementation model. No need to mention how
machine manages its head and tape.

Theory of Computation – p.36/?? Theory of Computation – p.35/??

 Multitape Turing Machines Variants of Turing Machine
A multitape TM is like a standard TM with several tapes Transition function of a standard TM in our definition forces
Each tape has its own head for reading/writing the head to move to the left or right after each step. Let us
vary the type of transition function permitted.
Initially the input is on tape 1 and other tapes are blank
Transition function allow for reading, writing, and Suppose that we allow the head to stay put, i.e.;
moving the heads on all tapes simultaneously, i.e., δ : Q × Γ → Q × Γ × {L, R, S}
δ : Q × Γk → Q × Γk × {L, R}k , where k is the number of S transition can be represented by two standard
tapes. transitions: one that move to the left followed by one
δ(qi , a1 , . . . , ak ) = (qj , b1 , . . . , bk , L, R, . . . , L) means that if that moves to the right.
the machine is in state qi and heads 1 though k are Since we can convert a TM which stay put into one that
reading symbols a1 through ak the machine goes to doesn’t have this facility, the extension does not
state qj , writes b1 through bk on tapes 1 through k, increase its power.
respectively, and moves each head to the left or right as
specified.
Theory of Computation – p.38/?? Theory of Computation – p.37/??

Simulating M with S Theorem 3.13

Assume that M has k tapes Every multitape Turing machine has an equivalent single
S simulates the effect of k tapes by storing their tape Turing machine.
information on its single tape
Proof: We show how to convert a multitape TM M into a
S uses a new symbol # as a delimiter to separate the
contents of different tapes single tape TM S . The key idea is to show how to simulate
S keeps track of the location of the heads by marking M with S .
with a • the symbols where the heads would be.

Theory of Computation – p.40/?? Theory of Computation – p.39/??

 General Construction Example simulation
S = "On input w = a1 a2 . . . an Figure ?? shows how to represent a machine with 3 tapes
1. Put S(tape) in the format that represents M (tapes):
by a machine with one tape.
• • •
S(tape) = # a1 . . . an # ⊔ . . . # ⊔ # ?
0 1 0 1 0 ⊔ ...
2. Scan the tape from the first # (which represent the left-hand end) to
?
the (k + 1)-st # (which represent the right-hand end) to determine M b a ⊔ ...

the symbols under the virtual heads. Then S makes the second pass ?
b a ⊔ ...
over the tape to update it according to the way M ’s transition function
?
dictates.
3. If at any time S moves one of the virtual heads to the right of # it
S •
# 0 1 • # • a #
0 1 0 # b a b
...

means that M has moved on the corresponding tape onto the unread
blank portion of that tape. So, S writes a ⊔ on this tape cell and shifts Figure 1: Multitape machine simulation
the tape contents from this cell until the rightmost #, one unit to the
right. Then it continues to simulates as before".

Theory of Computation – p.42/?? Theory of Computation – p.41/??

Nondeterministic TM Corollary 3.15

A NTM is defined in the expected way: at any point in a A language is Turing recognizable iff some multitape Turing
computation the machine may proceed according to machine recognizes it
several possibilities Proof:
Formally, δ : Q × Γ → P(Q × Γ × {L, R}) a Turing recognizable language is recognized by an
if:
Computation performed by a NTM is a tree whose ordinary Turing machine, which is a special case of a
branches correspond to different possibilities for the multitape Turing machine.
machine follows from the equivalence of a Turing multitape
only if:
If some branch of the computation tree leads to the machine M with the Turing machine S that simulates it.
accept state, the machine accepts the input That is, if L is recognized by M then L is also recognized by S

Theory of Computation – p.44/?? Theory of Computation – p.43/??

 More on NTM simulation Theorem 3.16
N ’s computation on an input w is a tree, N (w). Every nondeterministic Turing machine, NTM, has an
Each branch of N (w) represents one of the branches of equivalent deterministic Turing machine, DTM.
the nondeterminism Proof idea: show that we can simulate a NTM N with DTM,
Each node of N (w) is a configuration of N . D.

The root of N (w) is the start configuration Note: in this simulation D tries all possible branches of N ’s
computation. If D ever finds the accept state on one of these
Note: D searches N (w) for an accepting configuration
branches then it accepts. Otherwise D simulation will not
terminate

Theory of Computation – p.46/?? Theory of Computation – p.45/??

A better idea A tempting bad idea

Design D to explore the tree by using a breadth-first search Design D to explore N (w) by a depth-first search

This strategy explores all branches at the same depth before A depth-first search goes all the way down on one branch
going to explore any branch at the next depth. Hence, this before backing up to explore next branch. Hence, D could
method guarantees that D will visit every node of N (w) until go forever down on an infinite branch and miss an accepting
it encounters an accepting configuration configuration on an other branch

Theory of Computation – p.48/?? Theory of Computation – p.47/??

Deterministic simulation of NTM Formal proof

input tape
D has three tapes, Figure ??:
...
0 0 1 0 ⊔ 1. Tape 1 always contains the input (and the code of N )
6 simulation tape and is never altered.
-x
D x # 1 x ⊔ ...
2. Tape 2 (called simulation tape) maintains a copy of the
? address tape
N ’s tape on some branch of its nondeterministic
1 2 3 3 2 3 1 2 1 1 3 ⊔ ...
computation
3. Tape 3 (called address tape) keeps track of D’s location
Figure 2: Deterministic TM D simulating N in N ’s nondeterministic computation tree

Theory of Computation – p.50/?? Theory of Computation – p.49/??

Note Address tape

Each symbol in a node address tells us which choice to Every node in N (w) can have at most b children, where
make next when simulating a step in one branch in N ’s b is the size of the largest set of possible choices given
nondeterministic computation by N ’s transition function
Sometimes a symbol may not correspond to any choice Hence, to every node we assign an address that is a
if too few choices are available for a configuration. In that string in the alphabet Σb = {1, 2, . . . , b}.
case the address is invalid and doesn’t correspond to any node
Example: we assign the address 231 to the node reached by
Tape 3 contains a string over Σb which represents a starting at the root, going to its second child and then going to that
branch of N ’s computation from the root to the node node’s third child and then going to that node’s first child
addressed by that string, unless the address is invalid.
The empty string ǫ is the address of the root.

Theory of Computation – p.52/?? Theory of Computation – p.51/??

 Corollary 3.18 The description of D
A language is Turing-recognizable iff some nondeterministic 1. Initially tape 1 contains w and tape 2 and 3 are empty
TM recognizes it. 2. Copy tape 1 over tape 2
Proof: 3. Use tape 2 to simulate N with input w on one branch of its
any deterministic TM is automatically an
if: nondeterministic computation.
nondeterministic TM Before each step of N , consult the next symbol on tape 3 to
determine which choice to make among those allowed by N ’s
follow from the fact that any NTM can be
only if:
transition function
simulated by a DTM
If no more symbols remain on tape 3 or if this nondeterministic
choice is invalid, abort this branch by going to stage 4.
If a rejecting configuration is reached go to stage 4; if an
accepting configuration is encountered, accept the input
4. Replace the string on tape 3 with the next string as if it is a counter
and go to stage 2.

Theory of Computation – p.54/?? Theory of Computation – p.53/??

Enumerators Corollary 3.19

An enumerator is a variant of a TM with an attached A language is decidable iff some NTM decides it.
printer (or an output tape)
The enumerator uses the printer as an output device to
print strings
Every time the TM wants to add a string to the list of
recognized strings it sends it to the printer

Note: Some people use the term recursively enumerable language for lan-

guages recognized by enumerators

Theory of Computation – p.56/?? Theory of Computation – p.55/??

 Theorem 3.21 Computation of an Enumerator
A language is Turing-recognizable iff some enumerator An enumerator starts with a blank input tape
enumerates it If the enumerator does not halt it may print an infinite
Proof: list of strings
if:if we have an enumerator E that enumerates a The language recognized by the enumerator is the
language A then a TM M recognizes A. M works as collection of strings that it eventually prints out.
follows:
M = "On input w: Note: an enumerator may generate the strings of the lan-
1. Run E. Every time E outputs a string x, compare it with w.
guage it recognizes in any order, possibly with repetitions.
2. If w = x, M accept; else go to 1.

Clearly M accepts those strings that appear on E ’s list.

Theory of Computation – p.58/?? Theory of Computation – p.57/??

Another Proof Proof, continuation

If M recognizes a language A, we can construct an
only if: If M recognizes a language A, we can construct an
only if:
enumerator E for A. For that consider s1 , s2 . . . . , the list of enumerator E for A. For that consider s1 , s2 . . . . , the list of
all possible strings in Σ∗ , where Σ is the alphabet of M . all possible strings in Σ∗ , where Σ is the alphabet of M .
Given a pair of integers hi, ji, define Next(hi, ji) = if (i = 1) E="
then hj + 1, 1i else hi − 1, j + 1i. 1. Let i = 1.
E="
2. For j = 1 to i, simulate M on sj at most i steps.
1. Let hi, ji = h1, 1i.
3. If M accepts sj with i steps or less, prints out sj .
2. Simulate M on sj at most i steps.
4. i = i + 1, go to 2.”
3. If M accepts sj with exactly i steps, prints out sj .
4. hi, ji = Next(hi, ji), go to 2.” Note: a string may print out multiple times.

Note: no string prints out more than once.

Theory of Computation – p.60/?? Theory of Computation – p.59/??

 Algorithms Equivalence with other models
Informally speaking an algorithm is a collection of There are many other models of general purpose
simple instructions for carrying out a task. computation. Example: recursive functions, normal
In everyday life algorithms are called procedures or algorithms, semi-Thue systems, λ-calculus, etc.
recipes. Some of these models are very much like Turing
Algorithms abound in contemporary mathematics. machines; other are quite different
All share the essential feature of a TM: unrestricted
access to unlimited memory
All these models turn out to be equivalent in
computation power with TM

Theory of Computation – p.62/?? Theory of Computation – p.61/??

Church-Turing Thesis Algorithm as a Turing Machine

Other formal definitions of algorithms have been Alonzo Church and Alan Turing in 1936 came with
provided by: Kleene using recursive functions, Markov formal definitions for the concept of algorithm.
using rewriting (derivation) rules with a grammar called Church used a notational system called λ-calculus to
normal algorithms. define algorithms.
Essentially all these formal concepts of algorithm are Turing used his “Turing Machines" to define algorithms.
equivalent among them and are equivalent with Turing
Machines. These two definitions were shown to be equivalent.
Church-Turing Thesis:
Every computing device can be
simulated by a Turing machine.

Theory of Computation – p.64/?? Theory of Computation – p.63/??

 Encoding and Decoding Objects Formal Definition
Our notation for encoding an object O into its string an algorthm is a decider TM in the standard
Definition:
representation is hOi. representation.
If we have several objects O1 , O2 , . . ., Ok we denote
their encoding into a string by hO1 , O2 , . . . , Ok i. The input to a Turing machine is always a string.
Encoding itself can be done in many ways. It doesn’t If we want an object, other than a string as input, we
matter which encoding we pick because a Turing must first represent that object as a string.
machine can always translate one encoding into Strings can easily represent polynomials, graphs,
another. grammars, automata, and any combination of these
A (part of) Turing machine may be programmed to objects.
decode the input representation so that it can be
interpreted the way we intend.

Theory of Computation – p.66/?? Theory of Computation – p.65/??

A TM deciding A Example TM
M = “On input hGi, the encoding of G Let A be the language consisting of all strings
representing undirected graphs that are connected.
1. Select the first node of G and mark it.
Recall:a graph is connected if every node can be reached from
2. Repeat the following stage until no new nodes are marked.
every other node.
3. For each node in G, mark it if it is attached by an edge to a node
Notation: A = {hGi | G is a connected undirected graph}
that is already marked.
4. Scan all the nodes of G to determine whether they all are marked. If
they are accept; otherwise reject."
.

Theory of Computation – p.68/?? Theory of Computation – p.67/??

 Graph encoding, hGi Implementation details
The encoding hGi of a graph as a string is a list of Consider the graph in Figure ??
nodes followed by a list of edges. 4j
Each node is a decimal number, and each edge is a
1j
pair of decimal numbers that represent the nodes that
 S
edge. connects 
 SS
3j 2j
Example encoding: the graph in Figure ?? is encoded by the string:
hGi = (1, 2, 3)((1, 2), (2, 3), (3, 1), (1, 4)).
Figure 3: A connected graph

Theory of Computation – p.70/?? Theory of Computation – p.69/??

Checking the encoding

When M receives the input hGi it first checks to determine
that the input is a proper encoding of some graph:
1. Scan the tape to be sure that there are two lists and that they are in
proper form.
2. The first list should be a list of distinct decimal numbers; the second
list should be a list of pairs of decimal numbers.
3. The list of decimal numbers should contain no repetitions.
4. Every node on the second list should appear in the first list too.

Note: element distinctness problem can be used to formate the lists and to

implement the checks above.

Theory of Computation – p.71/??