•Chapter-5 (Turing Machines and Recursive Function

Turing Machines, variations, halting problem, PCP,

Chomsky Hierarchy, Recursive and Recursively
enumerable language, Rice Theorem.
 Turing Machine
• The Church-Turing thesis states that any algorithmicprocedurethatcan be carried out by human
beings/computer can be carried out by a Turing machine.

• It has been universally accepted by computer scientists that the Turing machine provides an ideal theoretical
model of a computer.
• Turing machines are useful in several ways: As an automaton, the Turing machine is the
• most general model. It accepts type-0 languages. It can also be used for computing
• functions. Turing machines are also used for determining the undecidability of certain
• languages
and measuring the space and time complexity of problems.
•
 Components of Turing Machine
Infinite Tape
•An input infinite tape can be, used as an input buffer and also as a member element. •It is
random accessible. It is of infinite length divided into cells and each cell is capable of
holding only one tape symbol. It is
• also called 2-way infinite tape.
 Components of Turing Machine
Read-Write Buffer
•Read the data from the tape and can also write the data over the tape. After reading the
symbol from the tape, the read/write header moves to exactly one cell either in left or
right direction.
 Components of Turing Machine
Finite Control Unit
•As per the control unit, the transitions will take place, and will finally lead to some output.
 FORMAL DEFINITION
A Turing machine M is a 7-tuple, namely (Q, ∑, Γ, δ, q0, b, F), where
• Q is a finite nonempty set of states.

• Γ is a finite nonempty set of tape symbols,

• b ∈ Γis the blank.

• ∑ is a nonempty set of input symbols and is a subset of Γ and b ∉∑.

• δ is the transition function mapping d: Q ×ℾ -> Q× ℾ × (L/R). It says that, on providing a tape symbol, from a
particular state there will be a transition to another state, with a different or same tape symbol with defining

• q Q is the initial state, and

• 0 ∈Q is the set of final states.

F⊆
Q Design a Turing machine for L = {an bn | n >= 1}?
 REPRESENTATION OF TURING MACHINES

Three representations:
•Instantaneous descriptions using move-relations.

• Transition table, and

•Transition diagram (transition graph).
 LANGUAGE ACCEPTABILITY BY TURING MACHINES

• A string w in ∑* is said to be accepted by a TM(M) if after parsing the string w Turing machine
must halts on final state.
• q0w ⊢* α1pα2 for some p ∊ F and α1, α2 ∊ Γ
*.
• M does not accept w if the machine M either halts in a non-accepting state or does not halt

and goes into a loop.

Q Design a Turing machine for L = {an bn cn| n >=
0}?
Q Design a Turing machine for L = {w c w | w {0, 1}* }?

∊
Q Design a Turing machine for addition of two number in unary?
Q Design a Turing machine for converting unary number into binary
number?
Versions of Turing Machine
•On the basis of determinism of the next transition to a state on a particular
input, Turing Machine are divided in two types-
•Determinism Turing Machine. •Non-
Deterministic Turing Machine.

•In non-deterministic Turing machine, there can be more than one possible move
for a given state and tape symbol, but non-deterministic TM does not add any
power.
•Every non-deterministic TM can be converted into deterministic TM.
 Versions of Turing Machine
• There are multiple versions of Turing Machine which are as follows-
• Multi-tape Turing Machine.
•In multi-tape Turing machine, there can be more than one tape and corresponding head
pointers, but it does not add any power to Turing machine.
•Every multi-tape TM can be converted into single tape TM.
•Every language accepted by a multi-tape TM is acceptable by some single-tape TM (that is,
the standard TM).
• Multi Read/Write head points.
• Multi-dimensional Turing Machine.
• TM with stay option d: Q ×ℾ -> Q× ℾ × (L/R/S).
• TM with one way infinite tape (Semi infinite tape)
• Offline TM, this TM have a restriction that input can not be changed Jumping TM, where
• it is allowed to take more that one moves in one transaction d: Q × ℾ -> Q×
ℾ × (L/R) ×{n}.
• Always writing TM, (after reading a symbol from tape it must be replaced with other symbol)
• Multidimensional TM d: Q ×

• Multi-head TM ℾ -> Q× ℾ × (L/R/U/D)

• FA with a Queue

• TM with only 3 states

• Multi-tape Turing Machine with stay option and at most 2 states.

• Non-Deterministic TM d: Q × -> 2 Q×
• ℾ × (L/R)

• A NPDA with two independent stacks d: Q ×(S U Î) × × -> 2 Q× * ×

ℾ
ℾ ℾ
ℾ ℾ*
Q Consider the Turing machine M defined below 0 (Q0, 0, 1 (Q2, 1, B (Qf, -,
Choose the false statement a) The machine loops ® 0
Q R) L) -)
on 01 Q1 (Q2, 1, L) (Q1, 1, (Qf, -, -
Q2 (Q2, 1, L) R) )
b) The machine does not accept 0000
*Q --- (Q2, 0, L) (Qf, -, -
c) The machine accepts strings ending with a 1 ---
)
f
---
d) The machine accepts strings ending with 10
 Halt
•The state of Turing machine, where no transition isdefined or required is known as Halt. There
are two types of Halt-
•Final Halt- Machine has been halted on final state, then it is known as Final halt and hence
it depicts that machine is accepted.
•Non-Final Halt-Machine has been halted on non- final state, then it is known as non- final
halt and hence the string is rejected.

•After taking an input string, there are three possibilities for Turing Machine
•It may go to Final halt.
•It may go to Non- Final halt.
•It may go into Infinite loop.

•Final Halt and Non- Final Halt have been described above. After taking an input string, if the
machine goes to infinite loop, then we can’t say whether the string is Accepted/Rejected.
• So, broadly Recursively Enumerable Languages are categorized as-
•Recursive Set- The Language L, which is accepted by Turing Machine, is said to be recursive
set, where for all, ‘w’ that belongs to L, machine will go to final halt, and for all ‘w’ that
does not belongs to L, machine will go to non-final halt. Hence, membership property is
defined here.
•Recursively Enumerable Set- The language L, which is accepted by Turing Machine is said to
be REL, where for all, ‘w’ that belongs to L, machine will go to final halt, and for all ‘w’ that
does not belongs to L, machine will either go to non-final halt or infinite loop. Hence,
membership property is not defined here.

• If a set and its complement both are recognizable, then the set is decidable.
• There are some sets which are not recognizable (even members can’t be identified) because
there are more languages than programs.
Universal Turing Machine
 Universal Turing Machine

•Incomputer science, auniversal Turing machine(UTM) is aTuring machinethat

simulates an arbitrary Turing machine on arbitrary input.

•The universal machine essentially achieves this by reading both the description
of the machine to be simulated as well as the input to that machine from its own
tape.
•Every Turing machine computes a certain fixedpartialcomputable functionfrom the input
strings over itsalphabet. In that sense it behaves like a computer with a fixed program.

•However, we can encode the action table of any Turing machine in a string. Thus we can
construct a Turing machine that expects on its tape a string describing an action table followed
by a string describing the input tape, and computes the tape that the encoded Turing machine
would have computed. Turing described such a construction in complete detail in his 1936
paper:

•"It is possible to invent a single machine which can be used to compute any computable
sequence. If this machineUis supplied with a tape on the beginning of which is written the S.D
["standard description" of an action table] of some computing machineM, thenUwill compute
the same sequence asM.
Linear Bounded Automata
A Linear Bounded Automaton (LBA) is similar toTuring Machinewith
property stated below:
•Turing Machine witha bounded finite length of the tape.
 Turing-Church Thesis
• Concept Origin: Independently developed by Alan Turing and Alonzo Church in
the 1930s, establishing a fundamental principle in computer science about
computable functions.
[Link] Machines: Turing proposed the concept of a 'Turing machine', a
theoretical computing machine that can simulate any algorithm's logic.

[Link]'s Lambda Calculus: Church introduced lambda calculus, a

formal system for expressing computation based on function abstraction
and application.

[Link] Models: The thesis states that what can be computed on a

Turing machine can also be computed in Church's lambda calculus,
implying both models are equivalent in their computational power.
 The Post Correspondence Problem (PCP)
• is a significant problemin the field oftheoretical computerscience. It wasintroduced by Emil
Post in 1946 and is known for its undecidability. Here are the main points:
•Basic Concept: The problem involves two lists of words (strings of symbols) over a
common alphabet. The challenge is to find a sequence of indices where the concatenation
of the words in the first list, in that sequence, is equal to the concatenation of the words in
the second list in the same sequence.

• A = {1, 110, 0111}

• B = {111, 001, 11}
• Undecidability: The Post Correspondence Problem is known to be undecidable,
meaning there is no algorithm that can determine for every instance of the
problem whether or not a solution exists. This undecidability is a crucial aspect in
the theory of computation, particularly in understanding the limits of algorithmic
solvability.

• A = {b, babbb, ba}

• B = {bbb, ba, a}
 Decision properties
• Following properties are decidable in case a RS.
• Membership

• All properties are undecidable in case of a REL.

 RL DCFL CFL CSL RS RES
Emptiness Y Y Y X N N
Non-
Emptiness Y Y Y X N N

Finiteness Y Y Y X N N
Infiniteness Y Y Y X N N
Membershi
p Y Y Y X Y N

Equality Y N N X N N
Ambiguity
Y N N X N N
∑* Y N N X N N
Halting
Y Y Y X Y N
 Closure Properties of Recursive Set
• Recursive languages are closed underfollowingoperations
• Union
• Concatenation
• Intersection
• Reverse
• Complement •Inverse
homomorphism
• Intersection with regular set
• Set Difference

• Recursive languages are not closed under following operations

• Kleen closure
• Homomorphism
• Substitution
 Closure Properties of Recursive Enumerable Set
• Recursive Enumerableareclosedunderfollowingoperations
• Union
• Concatenation
• Kleen Closure
• Intersection
• Substitution
• Homomorphism •Inverse
Homomorphism
• Intersection with regular set
• Reverse operation

• Recursive Enumerable are not closed under following operations

• Compliment
• Set Difference
 RL DCFL CFL CSL RS RES
Y N Y Y Y Y
Union

Intersection Y N N Y Y Y

Complement Y Y N Y Y N

Set Difference Y N N Y Y N

Kleene Closure Y N Y Y Y Y

Positive Closure Y N Y Y Y Y

Concatenation Y N Y Y Y Y

Intersection with
Y Y Y Y Y Y
regular set

Reverse Y Y Y Y Y

Subset N N
 RL DCFL CFL CSL RS RES
Y N Y N N Y
Homomorphism

Free Homomorphism Y N Y Y Y Y

Inverse Homomorphism Y Y Y Y Y Y

Substitution Y N Y N N Y

Free Substitution Y N Y Y Y Y

∈
Quotient with regularset Y Y