For more notes visit https://collegenote.pythonanywhere.

com
Automata Theory: Turing Machine

Introduction to Turing Machine

A Turing machine is an abstract machine, introduced by the English
mathematician Alan Turing – 1936.This is a model of computation which provides much
of the theoretical foundation for the modern computer.
Turing began by considering a human computer i.e. a human solving a problem with
pencil and paper. The method of solving could be assumed to operate under these three
rules
1. The only things written in paper are symbols from some fixed finite set –
Alphabet
2. Each step taken by the computer depends only on the symbol he is currently
examined – state of mind
3. His state of mind might change as a result of symbols he has seen or computation
he has made,
Turing then set out to build an abstract machine that obeys these rules and can
duplicate what he took to be the primitive steps carried out by a human computer during
computation;
1. Examining individual symbol on the paper
2. Erasing a symbol or replacing it by another.
3. Transferring attention from one part of the paper to another

A Turing Machine will have

• finite alphabet of symbols (two alphabets – an input alphabet and a possibly larger
alphabet for use during computation),
• A finite set of states, corresponding to the possible “state of mind” of human
computer.
• A linear “tape” which is potentially infinite to both end.

Finite
Control

… B X1 X2 … Xi … Xn B

The tape is marked off into squares, each of which can hold one symbol from the
alphabet. If square has no symbol in it, then it contains blank. We think, reading and
writing as being done by a tape head. A single move of TM is determined by the current
state and current tape symbol and consist of three things.
1. Replacing the symbol in the current square by another, possibly different symbol.
2. Moving the tape head one square right or left or leaving it where it is.
3. Moving from the current state to another, possibly different state.

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory: Turing Machine

The tape serves.

- The input device ( Input is simply the string assumed to finite )
- The memory available for use during computation
- The output device (output is the string of symbols left on the tape at the
end of computation)
The most significant difference between the Turing machine and the simpler
machine (FA or PDA) is that- In a Turing machine processing a string is no longer
restricted to a single left- to- right pass through the input. The tape head can move in both
directions and erase or modify any symbol it encounters. The machine can examine part
of the input , modify it , take time to execute some computation in a different area of the
tape, return to re- examine the input , repeat any of these actions and perhaps stop the
processing before it has looked at all the input.

Formal Definition of Turing Machine

A Turing Machine (TM) is a 7- tuple
M = (Q, ∑, Γ,δ , q0 , B, F) where.
Q : The finite set of states of the finite control / states
∑: The finite set of input symbols
Γ : The complete set of tape symbols; ∑ is always subset of Γ
δ : The transition function . defined by
Q × Γ → Q × Γ × ( R, L, S ) where R, L, S is the direction of movement of head – left
or right or stationary
i.e. δ ( q, x ) = δ ( P, Y , D ) means TM in state q and current tape symbol X, moves to next
state p replacing tape symbol X with Y and move the head either direction or remains
same cell of input tape.
q 0 :The start state , a member of Q
B : The blank symbol. This symbol B ∈ Γ, B ∉ ∑
F : The set of final or accepting states , F ⊆ Q.

Instantaneous Descriptions for TM:

The configuration of a TM is described by Instantaneous Description (ID) of TM like
PDA. A string X1 X2...Xi-1 q Xi Xi+1…..Xn represents the ID of TM in which
1. q is the state of TM
2. The tape head scanning the ith symbol from the left
3. X1 X2…..Xn is the portion of tape between the leftmost and rightmost non-blank.
If the head is to the left of leftmost nonblank or to the right of right most non-
blank then some prefix or suffix of X1 X2….Xn will be blank and i will be 1 or n
respectively.

Moves of TM : The moves of TM, M = ( Q , ∑ , Γ , δ , q 0 , B , F ) is

described by notation ├ for single move and ├* for Zero or more move as in PDA.
(a) For δ (q, X i ) = ( P, Y , L) i.e next move is leftward then
X 1 X 2 .... X i −1 qX i X i +1N ....... X n ├ X 1 X 2 .... X i − 2 pX i −1YX i +1 ....... X n

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory: Turing Machine

reflects the change of state from q to p and the symbol Xi is replaces with Y then tape
head is positional at i-1(next scan is Xi-1)

1. if i =1 , M moves to the blank to the left of X1 i.e.

X 1 X 2 .... X i −1 qX i X i +1n ... X n ├ pBYX 2 ..... X n
or qX 1 X 2 .... X i −1 X i X i +1 ... X n ├ pBYX 2 ..... X n
n

2. If i =n, Y=B, then M moves to the state p and the symbol B written over Xn joins
the infinite sequence of trailing blanks which does not appear in next ID as
X1 X 2 ....X n−1qXn ├ X 1 X 2 .... X n − 2 pX n −1
(b) if δ (q, X i ) = ( p, Y , R) i.e next move is rightward . then
X 1 X 2 .... X i −1 qX i X i +1n ... X n ├ X 1 X 2 .... X i −1YpX i +1 .... X n which reflects that symbol Xi is
replaced with Y and the head has moved to cell i+1 .
1. If i = n, then i+1 cell holds blank which is not part of previous ID
X 1 X 2 .... X n −1 pX n ├ X 1 X 2 .... X n −1YpB
2. If i =1, Y=B, then the symbol B written over Xi joins the infinite sequence of
leading blanks and does not appear in next ID qX 1 X 2 .... X n ├ pX 2 X 3 .... X n

Equivalently ID can be written as : (q, x a y) where q is a state. x and y are strings on

−

Γ, a ∈ Γ and underlined symbol represents the tape head position

An Example : A TM accepting language {0 n1n | n ≥ 1}

• Given finite sequence of 0’s and 1’s on its tape preceded and followed by
blanks.
• Alternatively, TM will change 0 to an X and then a 1 to a Y, until all 0’s &
1’s are matched .
• Starting at left end of the input, it repeatedly changes a 0 to an X and
moves to the right over whatever 0’s and Y’s it sees until comes to a 1.
• It changes 1 to a Y , and moves left, over Y’s and 0’s until it finds X. At
that point it looks for a 0 immediately to the right . If finds one 0 then
changes it to X and repeats the process changing a matching 1 to Y.

Now TM will have

M= ({ q 0 , q1 , q 2 ,q 3 , q 4 }, {0,1}, {0,1, X , Y , B}, δ , q 0 , B,{q 4 })
The transition rule for the move of M is described by following transition table .
State 0 1 X Y B
q0 (q1, X,R) – – (q3, Y, R) -
q1 (q1, 0,R) (q2, Y,L) – (q1, Y, R) –
q2 (q2, 0, L) – (q0, X, R) (q2, Y, L) –
q3 – – – (q3, Y, R) (q4, B, R)
q4 – – – –
Acceptance of 0011 by M is described by following sequence of moves

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory: Turing Machine

q00011├ Xq1 011 ├ X0q111 ├ Xq20Y1 ├ q2X0Y1

├ Xq0 0Y1 ├ XXq1Y1 ├ XXYq11├ XXq2YY

├ Xq2XYY ├ XXq0YY ├ XXYq3Y

├ XXYYq3B├ XXYYBq4B ( Halt and Accept )

For string 0110
q00110 ├ Xq2110 ├ q2XY10 ├ Xq0Y10 ├ XYq310 (Halt and reject)

Since state q3 has no move on symbol 1 .

Transition diagram : A transition diagram of TM consists of

• Set of nodes representing states of TM.
• An arc from state q to p is labeled by the item(s) of the form X/ YD where X and
Y are tape symbol and D is direction. L or R. In diagram direction is represented
by L or R( or ←(left arrow) or → right arrow.)

The transition diagram for the above TM is

0/Y →
0/0 →

Y/Y ←
0/Y ← 0/0 ←
0/X→
q0 q1 q2

Y/Y→

X/X→
q3
Y/Y→
B/B→

q4

The Language of Turing Machine: If T = (Q, Σ, Γ, δ , q0 , B, F ) is a Turing machine and

w ∈ Σ * then language accepted by T , L(T ) = {w | w ∈ Σ * and q0 w ├* αpβ } for some
p ∈ F and any tape strings α and β.

The set of languages that can be accepted using TM are called recursively
enumerable Languages or RE languages.

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory: Turing Machine

The Turing Machines are designed to perform at least the following three roles.
1. As a language recognizer: TM can be used for accepting a language like Finite
Automata and pushdown automata(PDA).

2. As a computer of functions: A Turing machine represents a particular function.

Initial input is treated as representing an argument of the function. And the final
string on the tape when the TM enters the Halt state treated as representative of
the value obtained by an application of the function to the argument represented
by the initial string.

3. As an enumerator of strings of a Language, that outputs the strings of a

language, one at a time in some systematic order that is as a list.

Turing Machine for computing a Function

A Turing Machine can be used to compute functions. For such TM we adopt the
following policy to input any string to a Turing Machine which is a input of the
computable function.

The string w is presented in to the form BwB, where B is a blank symbol, and
placed on to the tape, the head of Turing Machine is positioned at a blank symbol which
immediately follows by the string w.

We can show by underlining that symbol to show current position of machine

head in the tape as (q,BwB) . Or we can represent it by ID of TM in another format as
BwqB. Turing machine is said to halt on input w if we can reach to halting state after
performing some operations , that is if

TM = (Q, ∑, Γ, δ , q 0 , B,{q a }) is a Turing Machine them TM is said to halt to on

input w iff BwqB Yields to B α qaB for some string α ∈ Γ or equivalently we say
*

(q,BwB) ├ (qa, B α B).

Definition:

A function f ( x) = y is said to be computable by a TM (Q, ∑, Γ, δ , q 0 , B,{q a }) if

(q0 ,BxB) ├* (qa, ByB) where x may be in some alphabet ∑1 * and y may be in some
alphabet ∑ 2 * and ∑1 , ∑ 2 ⊆ ∑ . It means that if we give input x to the Turing Machine
TM , it gives output as a string if it computes the function f ( x) = y .

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory: Turing Machine

Example: Design a TM which compute the function f(x) = x +1 for each x that
belongs to the set of natural numbers.

Solution: Given function f(x) = x + 1. Here we represent input x on the tape by a number
of 1's on the tape.

For example x = 1, input will be B1B,

for x = 2 , input will be B11B,
for x = 3, input will be B111B and so on.

Similarly output can be seen by the number of 1s on the tape when machine halts.

Let TM = (Q, ∑, Γ, δ , q 0 , B,{q a }) where Q = {q0,qa} Γ

={1,B} and halt state qa . The
transition function is defined as

Q B 1
q0 (q0,1,N) (qa,1,R)
qa - -

Let input x = 4, that is input tape contains input as B1111B

So (q0,B1111B) ├(q0,B11111) ├ (qa,B11111B) Which means output is 5.

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory Turing Machine
Introduction of Turing Machine -2
Storage in the state: In Turing machine, any state represents the position in the computation .
But a state can also be used to hold a finite amount of data. The finite control of machine consists
of a state q and some data portion. In this case a state is considered as a tuple – (state,data).
Following Figure illustrates the model.
Finite
Control
A B

δ is defined by:
δ ([q, A], X ) = ([q1 , X ], Y , R) means q is the state and data portion of q is A. The symbol scanned
on the tape is copied into the second component of the state and moves right entering state q1 and
replacing tape symbol by Y.
Turing Machine with Multiple Tracks:
The tape of Turing machine can be considered as having multiple tracks. Each track can
hold one symbol and the tape alphabet of TM consists of tuples with one component for each
track. Following figure illustrates multiple track TM.

Finite
Control

Track 1 X
Track 2 Y
Track 3 Z

A TM with a tape with multiple tracks.

Tape alphabet Γ is a set consisting of tuples like
Γ ={(X,Y,Z),……………. }
The tape head moves up and down scanning symbols in the tape at one position.

Subroutine: A Complex Turing machine can be thought as built from a collection of interacting
components like a general program. Such components of Turing machine are called subroutines.
A Turing Machine subroutine is a set of states that performs some useful processes and can be
called in to another machine for the part of that computation.

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory Turing Machine
Extension of TM:
Modern computing devices are based on the foundation of TM computation models.
To simulate the real computers a TM can be viewed as multi-tape machine in which there are
more than one tape. Adding extra tape adds no power to the computational model only the ability
to accept the language is concerned.
1. Multi-tape Turing Machine:
• A multi-tape Turing machine consists of finite control and finite number of tapes.
Each tape is divided into cells and each cell can hold any symbol of finite tape
alphabets.
• TM has separate R/W head for each tape.
• The set of tape symbols includes a blank symbol( B) as in single tape machine.
• The tape symbol has a subset called input symbols i.e. we can say Σ ⊆ Γ .

Finite
Control

Tape 1 ….. ….

Tape 2

Tape 3

A multi-tape TM
In Multi-tape TM, Initially,
1. Input (Finite sequence of input symbols) w is placed on the first tape.
2. All other cell of the tapes hold blanks
3. TM is in the initial state – q0
4. The head of the first tape is at the left end of the input.
5. All other tape heads are at some arbitrary cell since all other tape except first tape
consists completely blank.

A move of multi-tape TM depends on the state and the symbol scanned by each of the tape head.
In one move the multi-tape TM does the following.
1. The control enters in a new state, which may be same previous state.
2. On each tape, a new symbol is written on the cell scanned, these symbol may be same as
the symbol previously there.
3. Each of the tape head make a move either left or right or remains stationary. Different
head may move different direction independently i.e. if head of first tape moves leftward
,at the same time other head can move another directions or remains stationary.

The formal notation of multi-tape TM is the generalization of one-tape TM. The initial
configuration(initial ID) of multi-tape TM with n-tapes is represented as:
(q0 ,ax, B,B,……..,B) – n+1 tuple. Where w = ax is an input string and head of first
tape is scanning first symbol of w.

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory Turing Machine
The notation of configuration at any instant of TM can be generalized as: (n+1) tuple for n-
tape TM.
(q, x1a1y1 , x2a2y2 , ……………………., xnanyn) Where each xis are the portion of string on
tapes before current head position, each ais are the symbol currently scanning in each tapes
and each yis are the portion of string in tapes just rightward the current head position. q is
the control state

Equivalence of One-tape and Multi-tape Turing Machine

Any recursively enumerable languages that are accepted by one-tape TMs are also accepted by
multi-tape TM. Any n-tape TM for n ≥ 2, are at least as powerful as 1-tape TMs.

Let n ≥ 2 and T1 = (Q1 , Σ, Γ1 , δ1 , q1 , B, F1 ) be an n-tape TM, then there is a 1-tape

TM T2 = (Q2 , Σ, Γ2 , δ 2 , q2 , B, F2 ) with Γ1 ⊆ Γ2 which satisfies following conditions.
1. L(T1) = L(T2 ) i.e. for any input w ∈ Σ * , T2 accepts iff T1 accepts.
2. For any w ∈ Σ * , if (q1,Bw, B,B,……..,B)├* (qa, x1a1y1 , x2a2y2 , ……………………., xnanyn) for
some ai ∈ Γ1 and xi,yi ∈ Γ1 * then, (q2, Bw) ├*(qa, yaz) for some a ∈ Γ2 and y ,z ∈ Γ2 *

Simulating Multi-tape Turing Machine with 1-tape Turing Machine

Theorem: Every Language accepted by a Multi-tape TM is recursively enumerable.

Or
Any languages that accepted by a Multi-tape Turing Machine are accepted by one-tape TM.

Proof:
o Let L is a language accepted by a n-tape TM T1 = (Q1 , Σ, Γ1 , δ1 , q1 , B, F1 ) . We simulate
T1 with one-tape Turing Machine T2 = (Q2 , Σ, Γ2 , δ 2 , q2 , B, F2 ) considering there are 2n
tracks in the tape of T2.
o Let us assume that n = 2 then for n>2 is generalization of this case.
o Now total no of tracks in T2 will be 2*2 = 4.The second and fourth tracks of T2 hold the
contents of first and second tapes of T1 and track 1 holds the head position of tape 1 and
track 3 holds the head position of tape 2 of T1 as in figure below.

Finite
Control

Finite Data

Track 1 X

Track 2 A1 A2 …….. Ai …. Aj ……

Track 3 X
Track 4 B1 B2 ……….. Bi …. Bj ….

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory Turing Machine

o To simulate a move of T1,

ƒ T2’s head must visit the n-head markers so that it must remember how many head
markers are to its left at all times, that count is stored as a component of T2’s
finite control.
ƒ After visiting each head marker and storing the scanned symbol in a component
of its finite control, T2 knows what tape symbols are being scanned by each of
T1’s heads.
ƒ T2 also knows the state of T1 and stores its own finite control. i.e. T2 knows what
move T1 will make.
o T2 now revisits each of head markers on its tape, changes the symbol in the track
representing corresponding tapes of T1 and moves the head marker left or right.
o Finally , T2 changes the state of T1 as recorded in its own finite control. Hence T2 has
simulated one move of T1.
o We select T2’s accepting states all those states that record T1’s state as one of the
accepting state of T1. Hence whatever T1 accepts T2 also accepts.
□

2. Non-deterministic Turing Machine:

A non- deterministic TM(NTM) T = (Q, Σ, Γ, δ , q0 , B, F ) is defined exactly the
same as an ordinary TM, except the value of transition function δ . In NTM , the values of the
transition function δ are subsets, rather than a single element of the set Q × Γ × {R, L, S }

The notation for a TM configuration is unchanged.

♦ xqay ├ wpbz , means , beginning in configuration xqay , there is at least one move that will take
TM in configuration wpbz.
♦ xqay ├* wpbz means there is at least one sequence of zero or more moves that take NTM from
first configuration to second.

♦ The addition of non-determinism to Turing machines does not alter the definition of
Turing-computable.

Turing Enumerable languages:

A language is enumerable if there is an algorithm for enumerating it. To
enumerate a set means to list the elements one at a time. Any languages that can be enumerated
by a TM are Turing Enumerable Languages.
Definition: Let T be a k-tape Turing machine(k ≥ 1) and L ⊆ Σ * . We say T enumerates L if it
operates so that the following conditions are satisfied.
1. The tape head on the first tape never moves to the left and no non-blank symbol printed on tape 1 is
subsequently modified or erased.
2. For every x ∈ L , there is some point in the operation of T when Tape 1 has contents
x1Bx2Bx3B……….BxnB
for some n ≥ 0, where the strings x1, x2, …………. Xn are distinct elements of L. If L is finite,
then nothing is printed after the B following the last element of L.

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory Turing Machine
Unrestricted Grammars: An unrestricted Grammar (also called phrase-structure
Grammar) is a 4-tuple G = (V,T,P,S) where V and T are disjoint sets of variables and terminals
respectively, S ∈ V is start symbol and P is a set of productions of the form α → β
Where α , β ∈ (V ∪ T ) * and α contatains at least one variable.
The productions are of the form.
αAβ → αγβ or αAβ → γ
An unrestricted Grammar are used to describe the languages that are not context-free. In fact the
languages described by unrestricted grammar can be accepted by a TM. Hence they are
recursively enumerable.

An unrestricted grammar generating {anbncn | n ≥ 1 }

S → FS1
S1 →ABCS1
S → ABC
BA → AB
CA → AC
CB → BC
FA → a
aA → aa
aB → ab
bB → bb
bC → bc
cC → cc

The string aabbcc can be derived as

S ⇒ FS1 ⇒ FABCS1 ⇒ FABCABC ⇒ FABACBC
⇒ FAABCBC ⇒ FAABBCC ⇒ aABBCC
⇒ aaBBCC ⇒ aabBCC ⇒ aabbCC
⇒ aabbcC ⇒ aabbcc
TM comuting a Function:
Let T= (Q,∑, T = (Q, Σ, Γ, δ , q 0 , B, F ) be a Turing Machine , let f be a partial function
on ∑* with values in Γ * We say that T computes f if for every x ∈ ∑* at which f is defined
(q0,Bx)├* (qa ,Bf(x))
and no other x ∈ ∑* is accepted by T.
A partial function f is Turing computable or simply computable if there is a Turing
machine computing f.

Partial Recursive Function:

A Partial Recursive Function is one which is allowed to have an infinite loop for some
input values.
A Recursive Function is called a Total Recursive Function that always returns a value
for all possible input values.

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory Turing Machine
Church- Turing Thesis
It is a mathematically un-provable hypothesis abut the computability. This hypothesis
simplify states that – "Any algorithmic procedure that can be carried out at all (by human, a team
of human or a computer ) can be carried out by a TM."

This statement was first formulated by Alonzo Church a logician, in 1930s and it is
referred to as Church Thesis or Church-Turing thesis. It is not a mathematically precise
statement so un-provable . Later the invention of Turing Machine has accumulated enough
evidence to accept this hypothesis. Following are the some of evidences.

1. In nature, a human normally works with 2D paper sheet, not 1D tape. The transfer of
attention is not adjacent block like TM. However transferring attention from one place to
another during computation can be simulated by Turing Machine as one human step by
multiple stapes.
2. Various extensions of Turing Machine Model has been suggested to make computation
efficient like doubly infinite tape, a tape with multiple tracks, multi-tape , non-
determinism etc. In each case the computational power reserved.
3. Other theoretical model have been suggested that are closer to modern computers in their
operation.( e.g. simple programming type language, grammars and others)
4. Since the introduction of the TM , no one has suggested any type of computation that
ought to be included in the category of "Algorithmic Procedure".

After adopting Church-Turing Thesis, we are giving a precise meaning of the term:
An algorithm is a procedure that can be executed on a Turing Machine.

Another use of Church-Thesis is that- When we want to describe a solution to a problem, we

will often satisfied with a verbal description of the algorithm, translating it into detailed
Turing Machine implementations.

HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory Universal Turing Machine

Universal Turing Machine:

A Turing machine is created to execute a specific algorithm. If we have a Turing

machine for computing one function , then for computing different function or doing some other
calculation, a different TM will be required. Originally electronic computers were limited in a
similar way , and changing the computation to be performed , requires rewriting the machine.

A Turing machine can, simulate a computer that had been loaded with an arbitrary
program . I.e. A – TM can be used as a “stored program computer ” taking its program as well as
data from one or more tapes on which it is placed .
Modern computer are completely flexible in which the task it performs is to execute the
instructions stored in its memory , and can represent an algorithm for computation . Turing
describes a “Universal Computing Machine ” that can be defined as:
Definition : A Universal Turing machine Tu is a TM whose input consist of program and a
data set for the program to process. The program takes the from of a string specifying some other
(special – purpose) TM T1 and the data set is second string w interpreted as input to T1. Tu then
simulates the processing of w by T1.

Encoding of TM:
For the representation of any arbitrary TM T1, and an input string w over an arbitrary alphabet
as strings e(T1) , e(w) over some fixed alphabet , a notational system should be formulated .
Encoding the TM T1 and input string w in to e (T1) and e (w) , it must not destroy any
information , for the encoding of TM , we use the alphabet {0,1} although the TM may have a
much larger alphabet .
For encoding , we start by assigning positive integers to each state , each tape symbol and
each of three directions S,L and R in the TM we want to encode. We assume two fixed infinite
sets Q = { q1,q2,…………} and S = { a1, a2, ………} so that for any TM
T1 = (Q1 , Σ, Γ, δ , q 0 , B, F ) , we have Q1 ⊆ Q and Γ ⊆ S .
Hence once we have a subscript attached to every possible state and tape symbols, we can
represent a state or a symbol by a string of 0’s of the appropriate length. 1’s are used as
separators.
The Encoding Function e
First, associate to each tape symbol, to each state and to each of the three directions , a string of
0’s. Let
s(B) = 0
s(ai) = 0i+1 for each ai ∈ S
i+2
s(qi) = 0 for each qi ∈ S
s(S) = 0
s(L) = 00
s(R) = 000
Then each move of TM , described by formula
δ ( q, a ) = ( p, b, D ) is encoded as
e(m) =s(q)1s(a)1s(p)1s(b)1s(D)1
and for any TM T, with initial state q, T is encoded as:
e(T ) = s (q )1e(m1 )1e(m2 )1...................1e(mk )1

1 -HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory Universal Turing Machine
Where m1 , m2 ,.........mk are the distinct moves of T arranged in some arbitrary order.
Finally, any string w = w1 w2 w3 ............wk , for each wk ∈ S is encoded as:
e( w) = 1s ( w1 )1s ( w2 )1...................1s ( wk )1
♦ -The 1 at beginning of e(w) included so that a composite string of the form e(T)e(w),
there is no doubt for the stoppage of e(T) since separated by three 1’s. Since no valid
code for TM contains three 1’s in a row, we can be sure that the first occurrence of 111
separates the code for TM T1and input w.
♦ Also encoding of s(a) of a symbol a ∈ S is different from the encoding e(a) of the one
character string a.
♦ There may be any possible codes for a TM T1. The codes for the TM for n transitions
may be listed in any of n! orders.

An Example: Let TM T is given as:

T = ({q1 , q 2 , q 3 }, {a, b}, {a, b, B}, δ , q1 , B, F )
where δ is defined by the following moves.
m1 = δ (q1 , b) = (q3 , a, R)
m2 = δ (q3 , a) = (q1 , b, R)
m3 = δ ( q 3 , b ) = ( q 2 , a , R )
m 4 = δ ( q 3 , B ) = ( q 3 , b, L )

Encoding :
s(q1 ) = 000

s(q 2 ) = 0000
s (q3 ) = 00000
s(a1 ) = 00 considering a1 = a and a2 = b
s(a 2 ) = 000
s( B) = 0
s(S ) = 0
s ( L) = 00
s ( R ) = 000

Now e(m1 ) = s (q1 )1s (b)1s (q3 )1s (a)1s ( R)1 = 000100010000010010001

e(m2 ) = s (q3 )1s (a)1s (q1 )1s (b)1s ( R)1 = 000001001000100010001

e(m3 ) = s (q3 )1s (b)1s (q 2 )1s (a )1s ( R)1 = 0000010001000010010001

2 -HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory Universal Turing Machine
e(m4 ) = s (q3 )1s ( B)1s (q3 )1s (b)1s ( L)1 = 000001010000010001001

Now The code for T will be:

e(T ) = s (q1 )1e(m1 )1e(m2 )1e(m3 )1e(m4 )1

=0001000100010000010010001100000100100010001000110000010001000010010001100
00010100000100010011
for this machine the input (T,w) where w= ab , the code will be,

e(w) = 1s(a)1s(b)1 = 10010001

Code for (T,W) is:

000100010001000001001000110000010010001000100011000001000100001001000110000
01010000010001001110010001
Universal Languages:
The universal language Lu is the set of binary strings that encode a pair (M,w)
where M is a TM with binary input alphabet, and w is a string in (0+1)*, such that w
is in L(M).
In other words, the languages that is accepted by universal TM is called universal
Languages.
A universal TM U can be described as a multi-tape Turing machine in which the
transitions of M are stored initially on the first tape along with string w. The second
tape holds the simulated tape of M in the format same as the code of M. Third tape of
U holds the state of M, with suitable encoding as in figure below.

Finite Control

M w

Tape of M 001000010010001………………….

State of M 000…..

Scratch

A Sketch of Universal TM

3 -HGC
For more notes visit https://collegenote.pythonanywhere.com
Automata Theory Universal Turing Machine

The Operation of Universal Turing Machine U can be described as:

1. Examine the input to make sure that the code for M is valid code for some TM. If
not, U halts without accepting. Any invalid codes represents TM with no moves.
2. Initialize the second tape to contain the input w in encoded form ( simulated tape
of M)
3. Place code of q1 (the start state of M) on the third tape and move the head of U’s
second tape to the first simulated cell.
4. To simulate a move of M , U searches on its first tape for a transition
0i10j10k10l10m1 such that 0i is the state on tape 3, 0j is the tape symbol of M that
begins at the position on tape 2 scanned by U. This transition is the one move of
M.
U should:
a. Change the contents of tape 3 to 0k, i.e. simulate the state change of M
b. Replace 0j on tape 2 by 0l i.e. change the tape symbol of M. If more or less
space is needed( j ≠ l) use scratch tape and shifting over technique as:
i) Copy onto a scratch tape the entire nonblank tape to the right of where
new value goes
ii) Write the new value using the correct amount of space for that value.
iii) Recopy the scratch tape onto tape 2 , immediately to the right of new
value.
c. Move head on tape 2 to the position of the next 1 to the left or right or
stationary. If m=1 (stationary), if m=2 (move left ) and if m=3(move right) .
Thus U simulates the one move of M.
5. If M has no transition that matches the simulated state and tape symbol, no
transition found . So M halts hence U halts likewise.
6. If M enters its accepting state, then U accepts.

The Halting Problem:

The halting problem for a TM M , H( M ) is defined as the set of input w such that M halts
given input w, regardless of whether or not M accepts w . so, the halting problem is the set of
pairs ( M, w) such that w is in H( M ).
The halting problem is related to the membership problem of RE languages . For a given TM
M and given string w, instead of asking M accepts w, it asks whether M halts on input w. We
abbreviate the problem Halts as :
Halts : Given a TM M and a string w, does M halt on input w ?
The domain of this problem is to be taken as the set of all Turing machines and all w; that is, we
are looking for a single Turing machine that , given the description of and arbitrary TM and w,
will predict whether or not the computation of TM applied to w halt. We can not find the answer
by simulating the action of TM on w, say by performing it on universal Turing machine, because
there is no limit on the length of computation. If TM enters an infinite loop, then no matter how
long we wait, we can never be sure that TM is in fact in a loop. It may be simple case of very
long computation .

4 -HGC