Turing Machine with modification

1. Two Stack PDA

2. TM with stay option
3. TM with semi-infinite tape
4. Offline TM
5. Multidimensional TM
6. Jumping TM
7. Multi-Tape T.M.
8. Non Deterministic T.M
9. Universal TM
10. TM without writing capacity/Read only TM/(2-way FA)
11. TM with input size Tape (LBA)
12. TM with tape used as stack (PDA)
13. TM with finite Tape (FA)
1. Two Stack PDA: A 2-stack PDA machine is similar to PDA but It has
two stacks instead of one. PDA recognizes languages known as CFG but 2-
stack PDA recognizes the recursively enumerable languages that are
recognised by Turing Machine. That’s why it is the variant of T.M. The
reason behind it is that on adding the second stack to the PDA, PDA
becomes much more powerful similar to T.M. It can compute anything that
a T.M. can compute and we know that T.M. Can be built to compute
anything that is computable.
2-stack PDA is 6-tuple PDA (Q, Σ, Γ, δ, q0, F) where

δ: Q × (∑ ∪ {ε}) × τ × τ = Q × τ*x τ*

2. TM with stay option:

δ: Q × τ = Q × τ x (L,R,S)
3. TM with semi-infinite tape:
B a a b b B B . .
δ: Q × τ = Q × τ x (L,R)

4. Offline TM B X a Y b B B . .

δ: Q × τ = Q × τ x (L,R) FC

B a a b b B B . .

5. Multi-dimensional TM B B B B B B B . .
B a a b b B B . .
δ: Q × × τ = Q × τ x (L,R,U,D)
B B B B B B B . .

6. Jumping TM : δ: Q × τ = Q × τ x {L,R},{N}
Jump with n cells
 7. Non-deterministic Turing Machines
•The T.M. has more than one transition for one symbol from the
current state.
A Non –determnistic TM Tape TM is a seven-tuple:
M = (Q, Σ, Γ, δ, q0, B, F)
Q A finite set of states
Σ A finite input alphabet, which is a subset of Γ– {B}
Γ A finite tape alphabet, which is a strict superset of Σ
B A distinguished blank symbol, which is in Γ
q0 The initial/starting state, q0 is in Q
F A set of final/accepting states, which is a subset of Q
δ A next-move function, which is a mapping (i.e., may
be undefined) from δ : Q x Γ –> 2Q x (Γ x {L,R})
 Time 0

 a b c  Time 1
Choice 1
q1
q2  b b c 
a  b, L
q2
q1
Choice 2

 c b c 
a  c, R q3
q3  is blank

Fall 2006 Costas Busch - RPI 5

 8. Multi-tape Turing Machines
•The T.M. having more than one tape called multiple T.M.
•A K-tape T.M. has K-read/write head that can move independently in
right, left or stationery.
•A multiple tape can read multiple symbols and update these symbols
and can decide the direction of each of head independently.
A Multi Tape TM is a seven-tuple:
M = (Q, Σ, Γ, δ, q0, B, F)
Q A finite set of states
Σ A finite input alphabet, which is a subset of Γ– {B}
Γ A finite tape alphabet, which is a strict superset of Σ
B A distinguished blank symbol, which is in Γ
q0 The initial/starting state, q0 is in Q
F A set of final/accepting states, which is a subset of Q
δ A next-move function, which is a mapping (i.e., may be
undefined) from
δ : Q x Γᴷ –> Q x (Γ x {L,R,S})ᴷ
Tape 1 Input string
Input string appears on Tape 1  is blank
Tape 2

 a b c   e f g 
FC
Tape 1 Time 1 Tape 2

 a b c   e f g 
q1 Time 2 q1
 a g c   e d g 
q2 q2
(b, f )  ( g , d ), L, R
q1 q2
δ(q1,b,f) = (q2,g,d,L,R)
7
A universal Turing machine is just a Turing machine whose
programming simulates other Turing machines. That is, the input
to the UTM is a description of a Turing machine TM and an input w
for TM, and the UTM simulates TM on that input w.

It behaves like a general purpose computer. TM is treated as

program whereas UTM is treated as General purpose computer.

Let M = (Q, Σ, Γ, δ, q0, B, F) and Q={q1,q2,q3} and w={a1a2a3..)

And let δ(q1, a1)=(q2,X,L)
Let encoding state are q1=1,q2=11,q3=111, a1=1,a2=11,a3=111, L=1,R=11,
separator=0 and B=1010 ,X=1,Y=11 then 1010110101
UTM simulates TM on a input w using three tapes.
There are three possibilities for a given string:
1. UTM accepts ( reaching final state & halt)
2. UTM rejects ( reaching non-final state & halt)
3. Infinite loop

Operation:
1. The first tape observed carefully to check whether the code for
M is valid or not, If the code is not valid then UTM halts with
out accepting.
2. Initialize the second tape for placing the tape values of M in
encoding form.
3. Third tape store states of machine M. The head of the third
tape will now positioned to state and the head for tape 2 will
positioned at the first simulated cell of second
It's universal in the sense that, for any problem that can be solved
by Turing machines, you could either use a Turing machine that
directly solves that problem, or you could use a UTM and give it
the description of a TM that directly solves the problem.

A UTM is an interpreter for (all) Turing machines.

The UTM is a Turing recognizable but no decidable for

ATM ={ (M,w| M is description of TM and w is input)}

https://www.youtube.com/watch?v=9Kxumc0ooiw
 Linear Bounded Automata
CSG generated CSL and CSL is accepted by LBA

Context Sensitive Grammar is the form of α -> β where

CSG must follow the following rules:
1. The number of symbols on LHS must not exceed the number of
symbols on RHS.
i.e. | α| ≤ |β| and α ϵ (NUT)*N (NUT)* , β ϵ (NUT)+
Where N is non-terminals and T is terminal

2. The production of the form A->ε is not allowed unless A is Start

symbol.

e.g. 1. AB → AbBc, A → bcA , B → b

2. S->aSBc, S->abc, cB->Bc, bB->bb
3. S->aSb, S-> ε
Linear Bound Automata is non-deterministic Turing Machine with
only one tape of exactly the same length of the input linearly bounded
with two right-end and left-end markers.

LBA is 8-tuple M = (Q, Σ, Γ, δ, q0, [ , ] ,F) where [ , ] are left-end and

right-end markers respectively and

δ : Q x Γ -> 2 Q x Γ x {L,R}

LBA accepts the strings in the similar manner as that of Turing

Machine.
[ a a b b c c ]

FC
Some Context Sensitive languages are:

L= {anbncn|n>=1}

L= {an|n>=0}

L= {an|n=m2,m>=1}

L= {an|n is prime}

L= {an|n is not prime}

L={ww| wϵ(a,b)+}
 RECURSIVE FUNCTION THEORY

Initial Functions For Natural Numbers

Let N = {0, 1, 2. ...) be a set of natural numbers. We have three initial

functions over N defined below:

1. Zero Function is denoted by Z and defined as follows

Z(n) = 0 for For all n ∈ N

Clearly the zero function returns zero regardless of its argument.

e.g. Z(0) = 0 where n=0, , Z(2)=0 where n=2

2. Successor Function(s) is denoted by S and defined as follows:

S(n) = n +1 for all n ∈ N.

Clearly successor function takes one argument and returns the succeeding
number.

For example: S(2) = 2 + 1 = 3 where 2, 3 ∈ N

3. Projection Function is is denoted by Pi n and defined as follows:

Pi n (a1 a2,...,an) = ai where ai ∈ N for i = 1, 2...... n and i<=n.

It means projection function takes n arguments and returns its ith argument.

e.g. P23(7,6,8)=6 .

Here total no. of arguments are 3 and i=2. So ith value is 6.

Initial Functions for Symbols:

We know that set of alphabet is represented by Σ . Two initial functions

are defined over Σ :

1. Null Function is defined as follows: NULL (n) = ε for all n∈ Σ *

For example: If Σ = {a,b} ,NULL (a) = ε NULL (b) = ε

2. Concatenation Function is defined as follows:

CONCATE W(W1) = WW1 for W.W, ∈ Σ * and |W1|>0

For example:
CONCATE N(TC) = NTC
CONCATE a(CONCATE b(NULL (abc) )
= CONCATE a(CONCATE b(ε)) = CONCATE a(b) = ab
Composition of Functions:

•We can define a new function by the combination of two or more functions.
Such defined functions are called composition function.

For example: i) S(Z(a)) = S(0) = 1 and ii) S(S(Z(n))) = S(S(0)) = S(1) = 2

•Let f1,f2,f3 ........,fk are k functions with n arguments, g is a function with k

arguments then g(f1,f2,f3 ........,fk) is called composition of f and g.

Example: If f1(x,y)=x+y, f2(x,y)=2x f3(x,y)=xy and g(x,y,z)=x+y+z then find

g(f1, f2, f3)

Solution:
g(f1, f2, f3)=g(f1(x,y), f2(x,y), f3(x,y)) = g(x+y,2x,xy) = 3x+xy+y

Note: g(x,y,z)=x+y+z
Recursive Function:

A function which calls itself directly or indirectly and terminates after

finite number of steps is known as recursive function.
In recursive functions, terminating point is also known as base point. A
recursive function will be good if it has terminating point and it call to
itself should be nearer to its terminating point.

e.g. n! = n(n-1)(n-2).........1 where 0!=1

Example: Define m ! recursively,

Solution. Let g(m)=m!=m*(m-1)*(m-2)....*1.

We know that 0!=1!=1. So g(0)=1 (it is a terminating point)

And g(n+1) = (n+ 1)g(n) ( as per definition g(m)=m!=m*(m-1)!
Total Recursive Function:

A function is called total function if it is defined for all its arguments.

Let f(a1, a2, a3, ..., an.) be a function and defined on function g(b1, b2, b3, ...,
bm.) then f is total function if every element of f is assigned to some unique
element of function g. i.e.
f(m,n)=m+n for m,n>=0
e.g. y=2x i.e. for each value of x, there will be a unique value of y.

Partial Recursive Function

A function is called partial recursive if it is defined for some of its
arguments.

Let f(a1, a2, a3, ..., an.) be a function and defined on function g(b1, b2, a3,
..., bm.) then f is partial function if some element of f is assigned to almost
one element of function g. i.e f(x,y) = x-y | if x>y otherwise 0
A partial function is recursive if
•It is an initial function over N, or
•It is obtained by applying recursion or composition or minimization on
initial function over N.
Primitive Recursive Function

A function is primitive if it follows the condition:

•It is any one of three initial function, or
•It is obtained from recursion or composition of initial functions.

Most popular total functions are primitive recursive functions, however

some total functions are not. For example, the ackerrman function is total
function but not primitive recursive.

Note: 1. Primitive recursive means there exists an algorithm with

bounded loop(i.e. for loop)
2. Total Recursive means algorithm will always halt.
3. Partial recursive means there is a Turing Machine which halts
when accepts and may or may not halt when rejects.
 Example: Find the value of f (7,2). Where f is primitive recursive
function.:
By definition, primitive recursive function is any one of three initial
functions
Z(x),S(x) and Pi n.

Here x=7 and y+1=2 or y=1 f(7,0)=x+y = 7+0 =7

f(7,2)= S(f(7,1))
f(7,2)= S(S(f(7,0)))
= S(S( 7))
= S(8)
=9
F(x,y)=xy
f(3,2)= S(f(3,1))
=f(3,1)+3
=S(f(3,0))+3
= (f(3,0)+3)+3
= f(3,0)+6
=0+6
=6
 Ackremann’s Function

In Computability theory, It is named after the W. Ackremann.

It is a recursive function of two parameters, each of which
can be assigned any non-negative integer, that grows very
fast and defined by A(m , n)
• if m=0, n!=0 then A(0 , n) = n+1
•if m!=0, n=0 then A(m , 0) =A(m-1,1)
• if m!=0, n!=0 then A(m , n) =A(m-1,A(m,n-1)) is computable
but not primitive recursive.

•Note: All primitive recursive functions are total and

computable but Ackermann illustrates that not all total
computable functions are primitive recursive.
Ex: Calculate A(1 , 1) and A(1,2) using Ackermann function

Solution:
A(1,1)= A(0,A(1,0)) by A(m-1,A(m,n-1)
A(1,0)= A(0,1) by A(m,n) = A(m-1,1)
A(0,1) = 2 by A(m,n) = n+1 | m=0
A(1,0)= 2
A(1,1)= A(0,2)
= 2+1 = 3

A(1,2) = A(0,A(1,1))
= A(0,3)
=4
A(2,1)= ?
Example: Show that function f(x,y) is primitive recursive where
•f(x,y)=x+y ii) f(x,y)= xy iii) f(x,y) = xy

Solution: By definition, primitive recursive function is any one of three

initial functions Z(x),S(x) and Pi n.

•f(x,y)=x+y

Step 1: Put y as 0,
f( x,0)) = x+0 = x

Step 2: Put y as y+1

f( x,y+1)) = x+y+1
= f(x,y)+1 Since f(x,y)=x+y is given
Step 3: Take a function h with three parameters as x,y and f(x,y) which is
equivalent to f(x,y)+1
h( x, y, f(x,y)) = f(x,y)+1

(note: By definition of Successor function, this is successor function of f(x,y))

Assume f(x,y) as z then
h(x,y,z)= S(P33(x,y,z))

(Note: 1. explanation of (P33(x,y,z): Here there are 3 arguments x,y,z and z is

f(x,y) which 3rd element. It means n=3 and i=3 for projection function and 2.
explanation of S(P33(x,y,z)) because z is f(x,y) and f(x,y)+1 is successor of z
)
Hence f(x,y)=x+y is primitive recursive function.
•f(x,y)=xy

Step 1: Put y as 0,
f( x,0) = x*0 = 0
= Z(0) (Note: Zero function)

Step 2: Put y as y+1,

f( x,y+1) = x(y+1)
= xy+x
= f(x,y)+x Since f(x,y)=xy is given

Step 3: Take a function h with three parameters as x,y and f(x,y) which
is equivalent to f(x,y)+x
h( x, y, f(x,y)) = f(x,y)+x
= P33(x,y,f(x,y))+P13(x,y,f(x,y))
(Note: 1) Explanation of P33(x,y,f(x,y)) is the projection function of f(x,y)
(i.e. 3rd argument) and 2) Explanation of P13(x,y,f(x,y)) is the projection
function of x (i.e 1st argument)
Since addition is already primitive recursive function.
Hence f(x,y)=xy is primitive recursive function.
Iii ) f(x,y)=xy for practice.

Step 1: Put y as 0,
f( x,0) = x0 = 1
= S(Z(0)) (Note: Successor function)

Step 2: Put y as y+1,

f( x,y+1) = x(y+1)
= xy.x
= f(x,y)*x Since f(x,y)=xy is given

Step 3: Take a function h with three parameters as x,y and f(x,y) which is
equivalent to f(x,y).x
h( x, y, f(x,y)) = f(x,y)*x
= P33(x,y,f(x,y))*P13(x,y,f(x,y))
(Note: 1) Explanation of P33(x,y,f(x,y)) is the projection function of f(x,y) (i.e.
3rd argument) and 2) Explanation of P13(x,y,f(x,y)) is the projection function
of x (i.e 1st argument)
Since multiplication is already primitive recursive function.
Hence f(x,y)=xy is primitive recursive function.
 Programming Techniques for Turing machine Construction
1. Storage in a state:
Finite control can be used not only to represent the position in the program
of TM but to hold a finite amount of data as it shown here.

B B B B B B . .
.

q
A B C
This makes the state to remember and to have a memory for the symbol
scanned in the input.
Ex: Design a TM to accept string 01*+10*
L={ 01,10,011,01111,100,10000,........}
S1: At initial state [q0, B], if it finds 0 or 1 , it stores in its state without replacing
and moves right and enters the state q1.
S2: At state [q1,0], if it finds1 then it skips all 1 and moves right and remains in
the same state.
S3: At state [q1,1], if it finds 0 then it skips all 0 and moves right and remains in
the same state.
S4: At state [q1,0], it finds B, then it reaches the accepting state [q1,B]
S5: At state [q1,1], it finds B, then it reaches the accepting state [q1,B]
 q0 q1
B 01 B [q0,B]
01111B 10000

1,1,R
0,0,R
[q0,B] [q1,0]
B,B,R

1,1,R
[q1,B]
B,B,R
[q1,1]

0,0,R

state 0 1 B
[q0,B] ([q1,0],0,R) ([q1,1],1,R) -
[q1,0] - ([q1,0],1,R) ([q1,B],B,R)
[q1,1] ([q1,1],0,R) ([q1,1],B,R)
 2. Multiple Track Tape
A specific type of T.M. contains multiple track but just one
tape head reads and writes on all tracks. A single tape head
reads n symbols from n track at one step.
A useful trick to perform more complicated simulations.
One Tape

  a b a b  track 1

  b a c d  track 2  is blank
One r/w head One symbol ( a, b)
Finite State
control unit δ(q0,a,b) = (q1,x,y,R)
Here symbol ab replaces with xy and head moves to right
B a b
b a
30
A Multi Track TM is a seven-tuple:
M = (Q, Σ, Γ, δ, q0, B, F)
Q A finite set of states
Σ A finite input alphabet, which is a subset of Γ– {B}
Γ A finite tape alphabet, which is a strict superset of Σ
B A distinguished blank symbol, which is in Γ
q0 The initial/starting state, q0 is in Q
F A set of final/accepting states, which is a subset of Q
δ A next-move function, which is a mapping (i.e., may
be undefined) from
k k
δ : Q x Γ –> Q x Γ x {L,R} K is no of tracks on tape
The power of Multi track TM is equivalent to Single track TM.
To understand the similarity of multi track and single track TM, click the link below
4. Subroutines:
In some problems, some tasks needed to be performed repeatedly
and it can be done by subroutines called a function. And
Subroutine is a set of instructions designed to perform a
frequently used operations within a program. e.g. f(a,b)= a*b
where a and b are unary numbers. 2 * 3=6

B B B B B B B 0 1 1 1 1 1 1
1,1,R 1,1,L
1,1,R 0,0,R 0,0,L
1,B,R 1,Y,R
q0 q1 0,0,R q2 q3 B,1,L q4

0,B,R
0,0,L Y,Y,R
B,B,R X,X,R
q6
q5 Y,1,L
0,0,L
1,B,R 0,B,R qf
1,1,L
 3. Checking off symbol:

This trick/method is used by Turing Machine for the language that contains the
repeated string and to compare the length of the two substring.
e.g. L={wcw|wϵ∑*}, L={ww|wϵ∑*}, L={wwr|wϵ∑*}, L={a^nb^n| n>=1} etc.

B X Y X X c X Y X X B

b,b,R X,X,R X,X,L b,b,L

a,a,R Y,Y,R a,a,L X,X,R
Y,Y,L
a,X,R a,X,L
q1
q0 q2 q3 q4 b,b,R
c,c,R c,c,L Y,Y,R
c,c,R X,X,R b,b,L
b,Y,R a,a,L
q5 q6 q7 q8
q9 a,a,R c,c,R b,Y,L c,c,L
b,b,R X,X,R
X,X,R
Y,Y,R
X,X,R Y,Y,R
Y,Y,R
B,B,R qf Y,Y,R