Variant of Turing Machine

1. Multiple track Turing Machine:

that
.Ak-track Turing machine(for some k>0) has k-tracks and one RW head
reads and writes all of them one by one.
.Ak-track Turing Machine can be simulated by a single track Turing machine
2. Two-way infinite Tape Turing Machine:
unbounded in both
Infinite tape of two-way infinite tape Turing machine is
directions left and right. one-way infinite
Two-way infinite tape Turing machine can be simulated by
Turing machine (standard Turing machine).
3. Multi-tape Turing Machine:
It has multiple tapes and is controlled by a single head. Turing machine but
The Multi-tape Turing machine is different from k-track
expresSive power is the same.
Turing machine.
" Multi-tape Turing machine can be simulated by single-tape
4. Multi-tape Multi-head Turing Machine:
heads
The multi-tape Turing machine has multiple tapes and multiple
Each tape is controlled by a separate head
Multi-Tape Multi-head Turing machine can be simulated by a standard
Turing machine.
5. Multi-dimensional Tape Turing Machine:
in any direction that
It has multi-dimensional tape where the head can move
is left, right, up or down. one-dimensional
Multi dimensional tape Turing machine can be simulated by
Turing machine
6. Multi-head Turing Machine:
more heads to read the
" A multi-head Turing machine contains two or
symbols on the same tape.
step all the heads sense the scanned symbols and move or write
" In one
independently. head Turing
Multi-head Turing machine can be simulated by a single
machine.
7. Non-deterministic Turing Machine:

Anon-deterministic Turing machine has a single,

one-way infinite tape.
 For a given state and input symbol has at least one choice to move(finite
number of choices for the next move), each choice has several choices of
the path that it might follow for a given input string.
Anon-deterministic Turing machine is equivalent to the deterministic Turing
machine.

Universal Turing Turing

Machine
Machine which when supplied with an
AUniversal Turing Machine is a
appropriate descriptionof a Turing Machine Mand an inputstring w, can
simulate the computation of w.
M,W Turing Machine Responseas M response with W
UTM

Construction of UTM
Without loss of generality, we assume the following for M:
Q={q1, q2, ....qn} where q1=initial state and q2=Final State
T={o1, ¡2,,...on} where o represent blanks
Select an encoding on which q1 is representable by 1, q2 by 11, and so on.
Similarly, o1 is encoded as 1, o2 as 11, etc.
for
Finally, let us represent RW head directions by 1 forL (Left) and 11
R(Right).
" The symbol 0 will be used as aseparator between 1s.
With this scheme, any transition of Mcan be given as :

O (q3,1) =(q4, ¡3,L) willappear as

011101011110111010
Turing machine as Enumerator
An enumerator is a Turing machine with an attached printer. The Turing machine can use that
printer as an output device to print strings. Every time the Turing machine wants to add a string to
the list, it sends the string to the printer. Enumerator is a type of Turing machine variant and is
equivalent with Turing machine.
 An Enumerable Language is Turing
Recognizable
I's very easy to construct a Turing
Machine that recognizes the enumerable language
We can have two tapes. On one tape we take the input string and on
the other tape, we Tun ag
enumerator to enumerate the strings in the language one after another. Once a string 15peu
the second tape we compare it with the input in the first tape. If its a match, then we acoept ue pes
else reject.

Undecidability-A problem is undecidable if there is

no Turing machine which will alwavs halt in finite amount of time
togive answer as 'yes' or 'no', An undecidable problem has no
algorithmto determine the answer for agiven input.

Decidable Problems
Aproblem is decidable if we can construct a Turing machine which will halt in
finite amount of time for every input and give answer as 'yes' or 'no'. A
deeidable problem has an algorithm to determine the answer for a given input.
Examples
" Equivalence of two regular languages: Given two regular languages,
there is an algorithm and Turing machine to decide whether two regular
languages are equal or not.
Finiteness of regular language: Given a regular language, there is an
algorithm and Turing machine to decide whether regular language is finite or
not.
Emptiness of context free language: Given a context free language, there
is an algorithm whether CFL is empty or not.
Undecidable Problems
Aproblem is undecidable if there is no Turing machine which willalways halt in
finite amount of time to give answer as 'yes' or 'no'. An undecidable problem
has no algorithm to determine the answer for a given input.
Examples
Ambiguity of context-free languages: Given a context-free language,
there is no Turing machine which will always halt in finite amount of time and
give answer whether language is ambiguous or not.
Equivalence of two context-free languages: Given two context-free
languages, there is no Turing machine which will always halt in finite amount
of time and give answer whether two context free languages are equal or
not.
 Given a CFG and input alphabet,
Everything or completeness of CFG: strings
whether CFG will generate all possible of input alphabet (?")is
undecidable.
CFL CSL, REC or REC,
.Regularity of CFL,CSL, REC and REC: Given a
determining whether this language is regular is undecidable.

lurmg mschine cannot be

dacidable
lodecidalile bangung)

Tring nlachie always Turing machine

mayimay not halt
halts(decidakle language)
(Semi decidable)

decidablity,semidecidablity and undecidalblity

Relation between

Rice's Theorem
on Recursive Enumerable
Every non-trivial (answer is not known) problemRecursive Enumerable, its
languages is undecidable.e.g.; If a language is undecidable.
complement will be recursive enumerable or not is
Reducibility and Undecidability
Language Ais reducible to language B(represented as A?B) if there exists a
function f which will convert strings in A to strings in B as:
w?A <=> f(w) ?B
Theorem 1: If A?B and B is decidable then A is also decidable.
Theorem 2: If A?B andA is undecidable then B is also undecidable.

Church-TuringThesis
Turing machine is defined as an abstract representation of a computing device
such as hardware in computers. Alan Turing proposed Logical Computing
Machines (LCMs), i.e. Turing's expressions for Turing Machines. This was done
to define algorithms properly. So, Church made a mechanical method named as
M for manipulation of strings by using logic and mathematics. This method M
mustpass the following statements:
.Number of instructions in Mmust be finite.
To
ed up

l .Output should be produced after performing finite numberof steps.

can be made in real life.
It should not be imaginary, ie. understanding.
. I t should not require any complex
proposed a hypothesis called
Using these statements Church the
stated as: "The assumption thatrecursive
Church's Turing thesis that can be
notion of computable functions canbe identified with partial
intuitive
functions."
that "Every computation that can be carried out
say
Or in simple words we can performed by a Turing Machine."
in the real world can be effectively

thesis says that every solvable decision problemn can be

The Church-Turing
transformed into an equivalent Turing machine problem.

It can be explained in two ways, as given below -

The Church-Turing thesis for decision problems.

The extended Church-Turing thesis for decision problems.
The Church-Turing thesis for decision problems

There is some effective procedure to solve any decision problem if and only if
there is a Turing machine which halts for all input strings and solves the
problem.

Theextended Church-Turing thesis for decision problems

Adecision problem Qis said to be partially solvable if and only if there is a

Turing machine which accepts precisely the elements of Qwhose answer is yes.
Proof

Aproof by the Church-Turing thesis is a shortcut often taken in establishing the

existence of adecision algorithm.
For any decision problem, rather than constructing a
Turing machine solution,
let us describe an effective procedure which solves
the problem.
 if
thesis explains that a decision problem Q has a solution
The Church-Turing answer for every qe
that determines the
and only if there is a Turing machine
Turing machine exists, the problem is said to be undecidable.
Q. Ifno such