THEORY OF COMPUTATION
Dr. K. Ananthajothi M.E.,Ph.D.,
UNIT IV:
TURING MACHINE
Definition of Turing Machine
Church-Turing Thesis
Programming Techniques for Turing Machine
Construction
Modifications of the Basic Turing Machine Model
Multi Tape
Multihead
Non-deterministic Turing Machines
Chomskian hierarchy of languages
Problems in Turing Machine
TURING MACHINE
Turing machine can solve any problem that a
modern computer can [Link] Turing machine
can be formally defined as follows,
M= (Q, ∑, Γ, δ, q0, ∆ or B, F)
Q- Finite set of states
∑- Finite set of input alphabets
Γ- Set of all tape symbols or External symbols
δ - Transition function
q0-Starting state
∆- Blank symbol or End marker
F- Set of final or accepting states
CHURCH-TURING THESIS
Any mechanical computation can be performed by a
Turing Machine
There is a TM-n corresponding to every computable
problem
We can model any mechanical computer with a TM
The set of languages that can be decided by a TM is
identical to the set of languages that can be decided by
any mechanical computing machine
If there is no TM that decides problem P, there is no
algorithm that solves problem P.
All of these statements are implied by the Church-Turing thesis
PROGRAMMING TECHNIQUES FOR
TURING MACHINE CONSTRUCTION
These are the four different techniques used to construct
an efficient Turing machine which functions as powerful
as conventional computer.
Storage in the state
Multiple tracks
Subroutines
Checking of symbols
STORAGE IN THE STATE OR FINITE
CONTROL
MULTIPLE TRACKS
SUBROUTINES
Some tasks need to be performed repeatedly which can
be done using subroutines.
The subroutines are also called as function.
The set of states in the subroutine has one start state and
another state namely the return state.
The subroutines of the Turing machine perform some
task simultaneously.
CHECKING OF SYMBOLS
The checking of symbols is an effective way of
recognizing the language by Turing machine. The Turing
machine can be extended by using checking off symbols.
The input symbol is placed in the input tape and the tape
head is moved either left or right.
The symbol which is read is marked by special character.
This method is used by the Turing machine for the
languages that contains the repeated strings and to
compare the length of the two strings.
MODIFICATIONS OF THE BASIC
TURING MACHINE MODEL
MULTI TAPE
The Multi-tape Turing machine has a finite control state and
finite number of tapes. Each tape in the multi-tape Turing
machine is divided into cells and each cell can hold any
symbol.
The finite sequence of input symbols is placed on the input
tape.
All other cells of all the tapes hold blank symbols.
The finite control is in the initial state and the control head
of the first tape is at the left end of the input.
MULTI TAPE
The moves of Multi-tape Turing machine depend on the following
factors.
State of the finite control
Symbol scanned by each tape head
MULTI HEAD
A Multi-head Turing machine is a single tape TM having N
heads reading symbols on the same tape.
In one steps all the heads sense the scanned symbols and
move or write independently.
In one move the heads may move left, right or remain
stationary.
MULTI HEAD
NON DETERMINISTIC TURING
MACHINE
It is similar to deterministic Turing machine except that for
any input symbol and current state it has number of choices.
A string is accepted by a Non deterministic Turing machine
If there is a sequences of moves that heads to a final state.
CHOMSKIAN HIERARCHY OF
LANGUAGES
CHOMSKIAN HIERARCHY OF
LANGUAGES
CHOMSKIAN HIERARCHY OF
LANGUAGES
CHOMSKIAN HIERARCHY OF
LANGUAGES
CHOMSKIAN HIERARCHY OF
LANGUAGES
CHOMSKIAN HIERARCHY OF
LANGUAGES
PROBLEMS ABOUT TURING MACHINE
1. Construct a Turing machine M for the language
L = {an bn | n ≥ 1}.
2. Explain Turing machine as a computer of integer
functions with an example. or Design a Turing machine that
computes x+y where x and y are positive integers.
3. Design a Turing machine which reverses the given
string {abb}.
4. Construct a Turing machine to perform proper
subtraction.
5. Design a Turing Machine for checking the palindrome of
the string of even length.