ATC- MODULE 5 2017-18

MODULE 5
9.7 VARIANTS OF TURING MACHINES
The Turing machine we have introduced has a single tape. δ(q, a) is either a single triple
(p, y, D), where D = R or L, or is not defined. We introduce two new models of TM:
(i) TM with more than one tape- called as multitape TM, and
(ii)TM where δ(q, a) ={(p1, y1, D1), (p2, y2, D2), •••• (pr , yr , Dr)} – called as nondeterministic TM.

(i) Multitape TM: A multitape TM has :

a finite set Q of states.
an initial state qo.
a subset F of Q called the set of final states.
a set P of tape symbols.
a new symbol b, not in P called the blank symbol.

There are k tapes, each divided into cells. The first tape holds the input string w.
Initially, all the other tapes hold the blank symbol.
Initially the head of the first tape (input tape) is at the left end of the input w. All
the other heads can be placed at any cell initially.
δ is a partial function from Q x Гk into Q x Гk x {L, R, S}k.
A move depends on the current state and k tape symbols under k tape heads.
In a typical move:
(i) M enters a new state.
(ii) On each tape, a new symbol is written in the cell under the head.
(iii) Each tape head moves to the left or right or remains stationary. The heads
move independently: some move to the left, some to the right and the remaining
heads do not move.

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 1

ATC- MODULE 5 2017-18

The initial ID has the initial state qo, the input string w in the first tape (input
tape), empty strings of b's in the remaining k - 1 tapes. An accepting ID has a final
state, some strings in each of the k tapes.

Theorem 9.1: Every language accepted by a multitape TM is acceptable by

some single-tape TM (that is, the standard TM).
Proof: Suppose a language L is accepted by a k-tape TM M. We simulate M with a
single-tape TM with 2k tracks. The second. fourth, ..., (2k)th tracks hold the
contents of the k-tapes. The first. third, ... , (2k - l)th tracks hold a head marker
(a symbol say X) to indicate the position of the respective tape head. We give an
'implementation description' of the simulation of M with a single tape TM M1. We
give it for the case k =2. The construction can be extended to the general case.
Figure 9.9 can be used to visualize the simulation. The symbols A2 and B5 are the
current symbols to be scanned and so the head marker X is above the two
symbols.

Initially the contents of tapes 1 and 2 of M are stored in the second and fourth tracks of
MI' The head markers of the first and third tracks are at the cells containing the first
symbol.
To simulate a move of M, the 2k-track TM M1 has to visit the two head markers and
store the scanned symbols in its control. Keeping track of the head markers visited and
those to be visited is achieved by keeping a count and storing it in the finite control of
M1' Note that the finite control of M1 has also the information about the states of M and
its moves. After visiting both head markers. M1 knows the tape symbols being scanned
by the two heads of M.
M1 revisits each of the head markers:

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 2

ATC- MODULE 5 2017-18

(i) It changes the tape symbol in the corresponding track of M1 based on the
information regarding the move of M corresponding to the state (of M) and the tape
symbol in the corresponding tape M.
(ii) It moves the head markers to the left or right.
(iii) M1 changes the state of M in its control.
This is the simulation of a single move of M.

Theorem 9.2: If M1 is the single-tape TM simulating multitape TM M, then

the time taken by M1 to simulate n moves of M is O(n2).

(ii) Non Deterministic TM:

Theorem 9.3: If M is a nondeterministic TM, there is a deterministic TM M1

such that T(M) = T(M1)
Proof: We construct M1 as a multitape TM. Each symbol in the input string leads
to a change in ID. M1 should be able to reach all IDs and stop when an ID
containing a final state is reached. So the first tape is used to store IDs of M as a
sequence and also the state of M. These IDs are separated by the symbol *

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 3

ATC- MODULE 5 2017-18

(included as a tape symbol). The current ID is known by marking an x along with

the ID-separator * (The symbol * marked with x is a new tape symbol.)
All IDs to the left of the current one have been explored already and so can be
ignored subsequently. Note that the current ID is decided by the current input
symbol of w.
Figure 9.10 illustrates the deterministic TM M1.
1. M1 examines the state and the
scanned symbol of the current ID.
Using the knowledge of moves of
M stored in the finite control of M1,
it checks whether the state in the
current ID is an accepting state of
M. In this case M1 accepts and
stops simulating M.

2. If the state q say in the current ID xqay, is not an accepting state of M1 and δ(q,
a) has k triples, M1 copies the ID xqay in the second tape and makes k copies of
this ID at the end of the sequence of IDs in tape 2.
3. M1 modifies these k IDs in tape 2 according to the k choices given by δ(q, a).
4. M1 returns to the marked current ID. erases the mark x and marks the next ID-
separator * with x. Then M1 goes back to step 1.

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 4

ATC- MODULE 5 2017-18

9.8 LINEAR BOUNDED AUTOMATON

This model is important because:
(a) the set of context-sensitive languages is accepted by the model.
(b) the infinite storage is restricted in size but not in accessibility to the storage in
comparison with the Turing machine model. It is called the linear bounded automaton
(LBA) because a linear function is used to restrict (to bound) the length of the tape.

In this section we define the model of linear bounded automaton and develop the relation
between the linear bounded automata and context-sensitive languages. It should be
noted that the study of context-sensitive languages is important from practical point of
view because many compiler languages lie between context-sensitive and context-free
languages.

A linear bounded automaton is a nondeterministic Turing machine which has a single

tape whose length is not infinite but bounded by a linear function of the length of the
input string. The models can be described formally by the following set format:

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 5

ATC- MODULE 5 2017-18

All the symbols have the same meaning as in the basic model of Turing machines with
the difference that the input alphabet L contains two special symbols ¢ and $. ¢ is called
the left-end marker which is entered in the leftmost cell of the input tape and prevents
the R/W head from getting off the left end of the tape. $ is called the right-end marker
which is entered in the rightmost cell of the input tape and prevents the R/W head from
getting off the right end of the tape. Both the end markers should not appear on any
other cell within the input tape, and the RIW head should not print any other symbol
over both the end markers.

Let us consider the input string w with |w|= n-2. The input string w can be recognized
by an LBA if it can also be recognized by a Turing machine using no more than kn cells
of input tape, where k is a constant specified in the description of LBA. The value of k
does not depend on the input string but is purely a property of the machine. Whenever
we process any string in LBA, we shall assume that the input string is enclosed within
the end markers ¢ and $.

The above model of LBA can be represented by the block diagram of Fig. 9.11.
There are two tapes: one is called the input tape, and the other, working tape.
On the input tape the head never prints and never moves to the left. On the working
tape the head can modify the contents in any way, without any restriction.

In the case of LEA, an ID is denoted by (q, w. k), where q € Q. w € Г and k is some integer
between 1 and n. The transition of IDs is similar except that k changes to k - 1 if the RIW
head moves to the left and to k + 1 if the head moves to the right.

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 6

ATC- MODULE 5 2017-18

Relation between LBA and context-sensitive languages:

The set of strings accepted by nondeterministic LBA is the set of strings generated by
the context-sensitive grammars, excluding the null strings, now we give an important
result:
If L is a context-sensitive language, then L is accepted by a linear bounded automaton.
The converse is also true.

CHAPTER 10

DECIDABILITY/RECURSIVELY ENUMERABLE LANGUAGES

10.1 THE DEFINITION OF AN ALGORITHM

Algorithm is a procedure (finite sequence of instructions which can be mechanically
carried out) that terminates after a finite number of steps for any input. The earliest
algorithm one can think of is the Euclidean algorithm, for computing the greatest
common divisor of two natural numbers. In 1900, the mathematician David Hilbert, in
his famous address at the International congress of mathematicians in Paris, averred
that every definite mathematical problem must be susceptible for an exact settlement
either in the form of an exact answer or by the proof of the impossibility of its solution.
He identified 23 mathematical problems as a challenge for future mathematicians; only
ten of the problems have been solved so far.

Hilbert's tenth problem was to devise 'a process according to which it can be determined
by a finite number of operations', whether a polynomial over Z has an integral root. This
was not answered until 1970.

The formal definition of algorithm emerged after the works of Alan Turing and Alanzo
Church in 1936. The Church-Turing thesis states that any algorithmic procedure
that can be carried out by a human or a computer, can also be carried out by a
Turing machine. Thus the Turing machine arose as an ideal theoretical model for an
algorithm. The Turing machine provided machinery to mathematicians for attacking the
Hilberts' tenth problem, The problem can be restated as follows: does there exist a TM
that can accept a polynomial over n variables if it has an integral root and reject the
polynomial if it does not have one, In 1970, Yuri Matijasevic. after studying the work of
Martin Davis, Hilary Putnam and Julia Robinson showed that no such algorithm (Turing
machine) exists for testing whether a polynomial over n variables has integral roots. Now

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 7

ATC- MODULE 5 2017-18

it is universally accepted by computer scientists that Turing machine is a mathematical

model of an algorithm.

10.2 DECIDABILITY
Now these terms are also 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 10.3 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 10.4 A problem/language is undecidable if it is not decidable.

10.3 DECIDABLE LANGUAGES

Proof: To prove the theorem, we have to construct a TM that always halts and also
accepts ADFA We describe the TM M using high level description. Note that a DFM B
always ends in some state of B after n transitions for an input string of length n.
We define a TM M as follows:
1. Let B be a DFA and w an input string. (B, w) is an input for the Turing machine M.
2. Simulate B and input H' in the TM M.
3. If the simulation ends in an accepting state of B. then M accepts w.
If it ends in a non accepting state of B, then M rejects w.
We can discuss a few implementation details regarding steps 1. 2 and 3 above. The input
(B, w) for M is represented by representing the five components Q, ∑, δ, qo, f by strings
of ∑* and input string W € ∑*. M checks whether (B, w) is a valid input. If not, it rejects
(B, w) and halts. If (B, w) is a valid input, M writes the initial state qo and the leftmost

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 8

ATC- MODULE 5 2017-18

input symbol of w. It updates the state using 0 and then reads the next symbol in w.
This explains step 2.
If the simulation ends in an accepting state w then M accepts (B, w). Otherwise, M rejects
(B, w). This is the description of step 3. It is evident that M accepts (B,w) if and only if w
is accepted by the DFA B.

Proof: We convert a CFG into Chomsky normal form. Then any derivation of w of length
k requires 2k - 1 steps if the grammar is in CNF. So for checking whether the input
string w of length k is in L(G), it is enough to check derivations in 2k - 1 steps. We know
that there are only finitely many derivations in 2k - 1 steps. Now we design a TM M that
halts as follows.
1. Let G be a CFG in Chomsky normal form and w an input string. (G, w) is an input for
M.
2. If k = 0, list all the single-step derivations. If k ≠ 0, list all the derivations with 2k - 1
steps.
3. If any of the derivations in step 2 generates the given string w, M accepts (G, w).
Otherwise M rejects.
(G, w) is represented by representing the four components VN, ∑, P, S of G and input
string w. The next step of the derivation is got by the production to be applied.
M accepts (G, w) if and only if w is accepted by the CFG G.
In Theorem 4.3, we proved that a context-sensitive language is recursive. The main idea
of the proof of Theorem 4.3 was to construct a sequence {wo, w1 ...wk} of subsets of (V
U∑)*, that terminates after a finite number of iterations. The given string w € ∑* is in
L(G) if and only if w € wk. With this idea in mind we can prove the decidability of the
context sensitive language.

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 9

ATC- MODULE 5 2017-18

10.4 UNDECIDABLE LANGUAGES

Theorem 10.4 There exists a language over 2: that is not recursively enumerable.

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 10

ATC- MODULE 5 2017-18

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 11

ATC- MODULE 5 2017-18

10.5 HALTING PROBLEM OF TM

In this section we introduce the reduction technique. This technique is used to prove the
undecidability of halting problem of Turing machine. We say that problem A is reducible
to problem B if a solution to problem B can be used to solve problem A.

10.6 THE POST CORRESPONDENCE PROBLEM

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 12

ATC- MODULE 5 2017-18

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 13

ATC- MODULE 5 2017-18

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 14

ATC- MODULE 5 2017-18

10.7 SUPPLEMENTARY EXAMPLES

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 15

ATC- MODULE 5 2017-18

CHAPTER 12
COMPLEXITY
When a problem/language is decidable, it simply means that the problem is
computationally solvable in principle, It may not be solvable in practice in the sense that
it may require enormous amount of computation time and memory, In this chapter we
discuss the computational complexity of a problem, The proofs of
decidability/undecidability are quite rigorous, since they depend solely on the definition
of a Turing machine and rigorous mathematical techniques. But the proof and the
discussion in complexity theory rests on the assumption that P≠NP. The computer
scientists and mathematicians strongly believe that P≠NP. But this is still open.
This problem is one of the challenging problems of the 21st century. This problem carries
a prize money of $lM. P stands for the class of problems that can be solved by a
deterministic algorithm (i.e. by a Turing machine that halts) in polynomial time: NP
stands for the class of problems that can be solved by a nondeterministic algorithm (that
is, by a nondeterministic TM) in polynomial time; P stands for polynomial and NP for
nondeterministic polynomial. Another important class is the class of NP-complete
problems which is a subclass of NP.

12.1 GROWTH RATE OF FUNCTIONS

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 16

ATC- MODULE 5 2017-18

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 17

ATC- MODULE 5 2017-18

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 18

ATC- MODULE 5 2017-18

12.2 CLASSES P AND NP

Ex: Construct the time complexity T(n) for the Turing machine M ={0n1n:n>=1}

Ex: Find the running time for the Euclidean algorithm for evaluating gcd(a. b)
where a and b are positive integers expressed in binary representation.

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 19

ATC- MODULE 5 2017-18

12.8 QUANTUM COMPUTATION

In the earlier sections we discussed the complexity of algorithm and the dead end was
the open problem P = NP. Also the class of NP-complete problems provided us with a
class of problems. If we get a polynomial algorithm for solving one NP-complete problem
we can get a polynomial algorithm for any other NP-complete problem.

In 1982. Richard Feynmann, a Nobel laurate in physics suggested that scientists should
start thinking of building computers based on the principles of quantum mechanics.
The subject of physics studies elementary objects and simple systems and the study
becomes more intersting when things are larger and more complicated. Quantum
computation and information based on the principles of Quantum Mechanics will
provide tools to fill up the gulf between the small and the relatively complex systems in
physics. In this section we provide a brief survey of quantum computation and
information and its impact on complexity theory.

Quantum mechanics arose in the early 1920s, when classical physics could not explain
everything even after adding ad hoc hypotheses. The rules of quantum mechanics were
simple but looked counterintuitive, and even Albert Einstein reconciled himself with
quantum mechanics only with a pinch of salt.

Quantum mechanics is real black magic calculus.

-A. Einstein

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 20

ATC- MODULE 5 2017-18

12.8.1 QUANTUM COMPUTERS

We know that a bit (a 0 or a 1) is the fundamental concept of classical computation and
information. Also a classical computer is built from an electronic circuit containing wires
and logical gates. Let us study quantum bits and quantum circuits which are analogous
to bits and (classical) circuits.
A quantum bit, or simply qubit can be described mathematically as
|ψ> = α|0> + β|0>

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 21

ATC- MODULE 5 2017-18

12.8.2 CHURCH-TURING THESIS

Since 1970s many techniques for controlling the single quantum systems have been
developed but with only modest success. But an experimental prototype for performing
quantum cryptography, even at the initial level may be useful for some real-world
applications.

Recall the Church-Turing thesis which asserts that any algorithm that can be performed
on any computing machine can be performed on a Turing machine as well.
Miniaturization of chips has increased the power of the computer. The growth of
computer power is now described by Moore's law, which states that the computer power
will double for constant cost once in every two years. Now it is felt that a limit to this
doubling power will be reached in two or three decades, since the quantum effects will
begin to interfere in the functioning of electronic devices as they are made smaller and
smaller. So efforts are on to provide a theory of quantum computation which will
compensate for the possible failure of the Moore's law.

As an algorithm requiring polynomial time was considered as an efficient algorithm, a

strengthened version of the Church-Turing thesis was enunciated. Any algorithmic
process can be simulated efficiently by a Turing machine. But a challenge to the strong
Church-Turing thesis arose from analog computation. Certain types of analog computers
solved some problems efficiently whereas these problems had no efficient solution on a
Turing machine. But when the presence of noise was taken into account, the power of
the analog computers disappeared.

In mid-1970s, Robert Solovay and Volker Strassen gave a randomized algorithm for
testing the primality of a number. (A deterministic polynomial algorithm was given by

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 22

ATC- MODULE 5 2017-18

Manindra Agrawal. Neeraj Kayal and Nitein Saxena of IIT Kanpur in 2003.) This led to
the modification of the Church thesis.

Strong Church-Turing Thesis

An algorithmic process can be simulated efficiently using a nondeterministic Turing
machine.
In 1985, David Deutsch tried to build computing devices using quantum mechanics.

Computers are physical objects, and computations are physical processes. What
computers can or cannot compute is determined by the law of physics alone, and not by
pure mathematics.
-David Deutsch
But it is not known whether Deutsch's notion of universal quantum computer will
efficiently simulate any physical process. In 1994, Peter Shor proved that finding the
prime factors of a composite number and the discrete logarithm problem (i.e. finding the
positive value of s such that b =as for the given positive integers a and b) could be solved
efficiently by a quantum computer. This may be a pointer to proving that quantum
computers are more efficient than Turing machines (and classical computers).

******************************************************************************

Prepared by: Roopa GK, Dept. of CSE, VCET Puttur Page 23