Module-5

TURING MACHINE

Problems that Computer Cannot Solve

Consider a simple C program with a simple print statement:

It is easy to discover that this program prints hello, world and

terminates.

However, we may have another program that might print hello, world
as shown below. It takes an input n, and looks for positive integer
solutions to the equation xn+yn=zn. If it finds one, it prints hello, world.
If it never finds integers x, y, and z to satisfy the equation, then it
continues searching forever and never prints hello, world.
 • Hypothetical tester: If a problem has an algorithm like H that
always tells correctly whether an instance of the problem has
answer “yes” or “no” then the problem is said to be “decidable”.
Otherwise, the problem is “undecidable”.

The hypothetical tester is a conceptual tool introduced in the study of

undecidable problems to illustrate why certain problems cannot be
solved by any algorithm. In this context, the "hypothetical tester" is
designed to determine whether a given program, when executed with
specific input, will output a particular result—in this case, whether it
prints "hello, world" as its first output.
This program, denoted as H, takes two inputs:
1. A program P (the code to be tested).
2. An input I (the input to the program P).
The goal of H is to decide if the program P with input I will produce the
output "hello, world" as the first set of characters it prints.

Expected Behavior of H:
• If P with input I prints "hello, world" as its first output, H should
return "yes".
• Otherwise, it should return "no".
The challenge arises because:

• A program P may take an infinite amount of time to decide its

output. For instance:
• If P is searching for a mathematical solution (like Fermat's Last
Theorem) before it prints anything, H cannot predict whether it
will eventually find a solution and print "hello, world" or loop
indefinitely.
• Even for programs that terminate, analyzing the behavior of
every possible program P with every possible input I is non-
trivial and undecidable.

The hypothetical tester is a classic example used to demonstrate:

1. Limits of Computation: Some problems, even simple-sounding

ones, are fundamentally unsolvable by any algorithm.
2. Undecidability: The inability to solve a problem algorithmically
is a critical concept in theoretical computer science and is at the
core of problems like the Halting Problem.

The Halting Problem is a fundamental concept in computer science

and computational theory. It addresses whether it's possible to design
an algorithm that can determine, for any given program and input,
whether the program will eventually stop running (halt) or continue
running forever.

Reducing one problem to another: A problem that cannot be solved

by computer is called undecidable. A reduction technique is used to
prove the undecidability of a halting problem. It is sufficient to show
that if we could solve the new problem, then we could use that solution
to solve a problem we already know is undecidable. The strategy is
suggested in the figure given below. The technique is called the
reduction of P1 to P2.
Using this technique, a problem P1 is reducible to problem P2 if a
solution to the problem P2 can be used to solve the problem P1. Thus,
➢ if P1 is reducible to P2 and P2 is decidable, then P1 is decidable
➢ If P1 is reducible to P2 and P2 is undecidable, then P1 is
undecidable.

What is Turing Machine?

In 1936, Alan M Turing proposed the Turing machine as a model of

any possible computation. This model is computer like, rather than
program like, even though true electronic, or even electromechanical
computers were several years in the future.

A Turing machine is a computational model, like Finite Automata

(FA), Pushdown automata (PDA), which works on unrestricted
grammar. The Turing machine is the most powerful computation model
when compared with FA and PDA. Instead of using stack as in PDA,
the Turing Machine (TM) uses the tape to store the symbols.

Church-Turing thesis
Any algorithmic procedure that can be carried out by a human or a
computer, can also be carried out by a Turing machine. Now it is
universally accepted by computer scientists that TM is a Mathematical
model of an algorithm. TM has an algorithm and an algorithm has a
TM. If there is an algorithm problem is decidable, TM solves that
problem. This is known as Church-Turing thesis.

Notation of Turing Machine:

(Q. Explain the Turing Machine model working principle. (4M))

The Turing machine consists of a finite control, which can be in any of
a finite set of states. There is a tape divided into squares or cells, each
cell can hold any one of a finite number of symbols.

• Initially, the input, which is a finite length string of symbols

chosen from the input alphabet, is placed on the tape. All other
tape cells, extending infinitely to the left and right, initially hold
a special symbol called the blank. The blank is a tape symbol,
but not an input symbol, and there may be other tape symbols
besides the input symbols and the blank, as well.

• There is a tape head that is always positioned at one of the tape

cells. The Turing machine is said to be scanning that cell.
Initially, the tape head is at the leftmost cell that holds the input.

• A move of the Turing machine is a function of the state of the

finite control and the tape symbol scanned. In one move, the
Turing machine will,

a) Change state: The next state optionally may be the same as

the current state.
b) Write a tape symbol in the cell scanned. This tape symbol
replaces whatever symbol was in that cell. Optionally, the
symbol written may be the same as the symbol currently
there.
c) Move the tape head left or right. In our formalism we require
a move, and do not allow the head to remain stationary. This
 restriction does not constrain what a Turing machine can
compute, since any sequence of moves with a stationary head
could be condensed, along with the next tape head move, into
a single state change, a new tape symbol, and a move left or
right.

Definition of Turing Machine:

(Q. Define Turing machine-2M)

A Turing machine M is a 7-tuple, namely (Q, Σ, Г, δ, qo, B, F),

where,
• Q: is the finite nonempty set of states.
• Г is a finite nonempty set of tape symbols,
• B ∈ Г is the blank.
• Σ is a nonempty set of input symbols and is a subset of Г and
B ∉ Σ.
• δ is the transition function.

The arguments of δ (q, X) are a state q and a tape symbol X.

The value of δ(q, X) is a triple (p, Y, D) where:
• p is the next state, in Q.
• Y is the symbol in Г, written in the cell being scanned,
replacing whatever symbol was there.
• D is the direction, either L or R, standing for “left” or
“right” specifying the direction in which the R/W head
moves.
• qo ∈Q is the initial state, and
• F ⊆ Q is the set of final or accepting states.
Instantaneous Description (IDs) of Turing Machine:
In Turing Machine, the instantaneous description is defined on the
whole string and the current state of the machine.
Thus, we shall use the string X1X2,…….Xi-1 qXiXi+1…….Xn to
represent an ID in which,
 1. q is the state of the Turing machine.
2. The tape head is scanning the ith symbol from the left.
3. X1X2,….Xn is the portion of the tape between the leftmost and
the right most nonblank. As an exception, if the head is to the left
of the leftmost nonblank or to the right of the rightmost nonblank,
then some prefix or suffix of X1X2,….Xn will be blank.

Thus, the ID is as given in Fig. 9.3.

Designing Turing Machine:

1. Let us design a Turing machine and see how it behaves on a
typical input. The TM we construct will accept the language
L={0n 1n:n>=1}

Initially, it is given a finite sequence of 0’s and 1’s on its tape, preceded
and followed by an infinity of blanks. Alternately, the TM will change
a 0 to an X and then a 1 to a Y, until all 0’s and 1’s has been matched.

The formal specification of the TM M is,

This table is called as transition table.

Transition Diagrams for Turing Machines:

A transition diagram for TM consists of a set of nodes corresponding

to the states of the TM. An arc from state q to state p is labeled by one
or more items of the form X/Y, D where X and Y are tape symbols, and
D is a direction, either L or R. That is, whenever δ(q,X)=(p, Y, D), we
find the label X/Y, D on the arc from q to p.
Let show the IDs for the input strings 0011 and 0010.

Example 2:
Construct a T.M. to accept the language L= {0n 1n 2n: n>=1}.
Ans:
The Turing machine works similar with the above example: it marks
the first 0 as X, the first 1 as Y, the first 2 as Z; then it goes back to the
second 0, and marks it as X, the second 2 as Y, the second 2 as Z, and
so on.
Example 3:
Obtain a TM to accept a string of a’s and b’s such that na(w)=nb(w).
Ans:
The general procedure: When TM is in initial state q0, first symbol of
the input string can be either a or b. Replace the first symbol a (or b) by
X and search for next symbol b (or a) and replace it by symbol Y. Repeat
this until blank symbol B is scanned.
Example 4: Obtain a TM to accept a palindrome constisting of a’s
and b’s of any length.
Ans: General idea is to place the given string in between blank symbols.
For string to be palindrome, its first and last, second and last but one
and so oon should match. If we found match, replaced matched symbols
by blank symbol B.
The transistion diagram is,

therefore, M=(Q, ∑, Г,δ, q0, B, F) where,

 Q={q0,q1,q2,q3,q4,q5,q6,qf}
∑={a,b}
Г={a,b,B}
δ is shown in the transition diagram
q0 is the initial state
B is the blank symbol
F={qf}

Example 5: Obtain a TM to accept the language L={wwR: wϵ

(a+b)*}
Ans: wwR is also a palindrome problem only, but length of the
palindrome must be even. Hence TM is same as previous but no
transition required from q3 and q6 towards the final state.
Therefore, the transition diagram is,

Example 6: Let x and y are two positive integers. Obtain a turing

machine to perform x+y. (Addition operation on TM)

Ans: Let us represent the numbers on the tape using unary

representation 1’. Let 0 be the separator.
Ex: x=5 can be represented as 11111 and y=3 can be represented as 111
Then 5+3 can be represented on the tape together with 0 as a separated,

111110111
Then output should be of the form:
111111110
ic, read all 1’s until we encounter the 0. Then change 0 to 1 and keep
moving right until blank symbol is encounter. Once found move left
and change 1 to 0 and keep moving right read sum from leftmost blank
symbol.
The transition diagram is,

Example 7: Monus operation or propoer subtraction on TM.

Let us,

TM, M will start with a tape consisting of 0m 1 0n surrounded by blanks.

M halts with 0m-n on its tape, surrounded by blanks.
Ic, for example 5-3 can be represented as,
B000001000B
The result 5-3=2 will be represented on the tape as,
BBBBB00BBBB

The transition diagram is,

Here the symbol→ indicates R(right)

and  indicates L (left)
The Language of a Turing Machine
In TM the input string is placed on the tape, and the tape head begins at
the leftmost input symbol. If the TM eventually enters an accepting
state, then the input is accepted, and otherwise not.

More formally, let M= (Q, Σ, Г, δ, qo, B, F) be a Turing machine. Then

L(M) is the set of strings w in ∑* such that for some state p
in F and any tape strings α and β.

The set of languages we can accept using a Turing machine is often

called the recursively enumerable languages or RE languages.

Turing Machines and Halting Problem:

There is another notion of “acceptance” that is commonly used for
Turing machines “acceptance by halting”. We say a TM halts if it enters
a state q, scanning a tape symbol X, and there is no move in this
situation i_e, δ(q,X) is undefined.

DECIDABILITY
● The term decidability defined using Turing machines.
When a Turing machine reaches a final state, it halts.
● We can also say that a Turing machine M halts when M
reaches a state q and a current symbol ‘a’ to be scanned so
that δ(q, a) is undefined.
● There are TMs that never halt on some inputs in any one of
these ways. So, we make a distinction between the
languages accepted by a TM that halts on all input strings
and a TM that never halts on some input strings.

Definition of Recursively Enumerable Language:

“A language L⊆Ʃ* is recursively enumerable if there exists a
TM M, such that L= L(M)”.
Definition of Recursive Language:
A language L⊆Ʃ* is recursive if there exists some TM M that
satisfies the following two conditions.
i) If w ϵ L then M accepts w (that is, reaches an
accepting state on processing w) and halts.
ii) If w ∉L then M eventually halts without reaching an
accepting state
 Definition Decidable: A problem with two answers
(Yes/No) is decidable if the corresponding language is
recursive. In this case, the language L is also called
decidable.
Definition Undecidable: A problem/language is
undecidable if it is not decidable.

Programming Techniques for Turing Machines

The goal is to give a sense of how a Turing machine can be used to
compute in a manner not unlike that of a conventional computer.
Eventually, we want to convince you that a TM is exactly as powerful
as a conventional computer.

The transition diagram is,

Multiple Tracks
Another useful “trick” is to think of the tape of a Turing machine as
composed of several tracks. Each track can hold one symbol, and the
tape alphabet of the TM consists of tuples, with one component for each
“track”. Thus, for instance, the cell scanned by the tape head in Fig.
8.13 contains the symbol [X, Y, Z]. Like the technique of storage in the
finite control, using multiple tracks does not extend what the Turing
machine can do.

Extensions to the Basic Turing Machine:

a) Multi-tape Turing Machines
(Q. Write a short note on Multitape TM. (06M))
A multi-tape TM is as shown below. The device has a finite control
“state”, and some finite number of tapes. Each tape is divided into cells,
and each cell can hold any symbol of the finite tape alphabet.

As in the single tape TM, the set of tape symbols includes a blank, and
has a subset called the input symbols, of which the blank is not a
member. The set of states includes an initial state and some accepting
states. Initially,
• The input, a finite sequence of input symbols, is placed on the
first tape.
• All other cells of all the tapes hold the blank.
• The finite control is in the initial state.
• The head of the first tape is at the left end of the input
• All other tape heads are at some arbitrary cell. Since tapes other
than the first tape are completely blank, it does not matter where
the head is placed initially; all cells of these tapes, “look” the
same.
A move of the multitape TM depends on the state and the symbol
scanned by each of the tape heads. In one move, the multitape TM
does the following:
• The control enters a new state, which could be the same as the
previous state.
• On each tape, a new tape symbol is written on the cell scanned.
Any of these symbols may be the same as the symbol previously
there.
• Each of the tape heads makes a move, which can be either left,
right, or stationary. The heads move independently, so different
heads may move in different directions, and some may not move
at all.

Equivalence of one-tape TM and Multi-tape TM:

(Q. Prove that every language accepted by a multi-tape TM is
recursively enumerable.5M)
b) NONDETERMINISTIC TURING MACHINES
(Q. Write a short note on Nondeterministic TM)
In the case of standard Turing δ (q1, a) was defined for some elements
of Q x Г as an element of Q x Г x {L, R}. Now we extend the definition
of δ. In a nondeterministic TM, δ (q1, a) is defined as a subset of Q x Г
x {L R}.
Definition: A nondeterministic Turing machine is a 7-tuple (Q, Σ,
Г, δ, qo, B, F), where,
• Q is a finite nonempty set of states.
• Г is a finite nonempty set of tape symbols,
• B ∈ Г is the blank.
 • Σ is a nonempty set of input symbols and is a subset of Г and
B ∉ Σ.
• qo ∈Q is the initial state, and
• F ⊆ Q is the set of final states.
• δ is a partial function from Q x Г into the power set of Q x Г
x {L. R}.

Undecidability

We then divide problems that can be solved by a Turing machine

into two: classes, those that have an algorithm ic, a Turing machine
that halts whether or not it accepts its inputs, and those that are only
solved by Turing machines that may run forever on inputs they do not
accept.

A Language That Is Not Recursively Enumerable:

• A Language L is recursively enumerable (RE) if L=L(M) for

some TM M. A language is recursively enumerable if there exists
a Turing machine that will enumerate all the strings in the
language or accept strings in the language but may not halt for
strings not in the language.
• A language 𝐿 is recursive iff exists a Turing machine 𝑀 such that
i) 𝐿 = 𝐿(𝑀) and
ii) 𝑀 always halt (even if it does not accept).

Definition: A language 𝐿 is undecidable iff 𝐿 is not recursive.

Note: The term “recursive” as synonym for “decidable” comes from

Mathematics (prior to computers).

Non-Recursively Enumerable (Non-RE) Languages

Definition: A language is non-recursively enumerable if no Turing
machine exists that can enumerate or accept all strings in the language.
In other words, it is not possible to construct an algorithm to semi-
decide membership.
o These are the most complex and "unsolvable" problems.
o The language and its complement are both non-recursively
enumerable.

Following figure suggests the relationship among three classes of

languages:
 1. The recursive languages
2. The languages that are recursively enumerable but not recursive.
3. The non-recursively-enumerable(non-RE) languages.

Recursive ⊆ RE ⊆ Non-RE.

Undecidability often involves proving that certain problems cannot be

solved by any algorithm (or equivalently, any Turing machine).
• To analyze such problems, we need a formal way to represent
them as inputs to Turing machines. Binary coding provides a way
to encode:
o Strings in a language.
o Descriptions of Turing machines.
o Complex decision problems.
Example: The Halting Problem
• The Halting Problem asks whether a Turing machine halts on a
given input.
• To analyze it, both the Turing machine (its states and transitions)
and the input string are encoded into a single binary string. This
encoding allows us to reason about whether a universal Turing
machine (UTM) can solve the problem.

Codes for Turing Machines:

Let us devise a binary code for Turing machines so that
each TM with input alphabet {0, 1} may be thought of as a
binary string.
Complements of Recursive and RE languages:
(Q. Prove that complement of recursive language is recursive)

Theorem: If L is a recursive language, so is L

Q. Prove that complement of recursively enumerable language is

recursive.
The Universal Language:
A Turing machine could be used to simulate a computer that had been
loaded with an arbitrary program. That is to say, a single TM can be
used as a “stored program computer”, taking its program as well as its
data from one or more tapes on which input is placed.

We define Lu, the universal language, to be the set of binary strings that
encode, a pair (M,w), where M is a TM with, the binary input alphabet,
and w is a string in (0+1)* such that w is in L(M).

That is, Lu is the set of strings representing a TM and an input accepted

by that TM. We shall show that there is a TM U, often called the
universal Turing machine, such that Lu=L(U).

It is easiest to describe U as a multi-tape Turing machine. In the case of

U, the transitions of M are stored initially on the first tape, along with
the string w. A second tape will be used to hold the simulated tape of
M, using the same format as for the code of M. That is, tape symbol Xi
of M will be represented by 0i and tape symbols will be separated by
single 1’s. The third tape of U holds the state of M, with state qi
represented by i 0’s. A sketch of U is in Fig. 9.5
The operation of U can be summarized as follows:
*****************************************************