z
VIGNAN Institute of Technology and Science
Department of Computer Science and Engineering
Formal Languages and Automata Theory
B.Tech III year I Sem
UNIT - V
Learning Objectives
1
2
3
4
5
6
Recursive
languages
& their Properties
Types of Turing Machine
& Halting
Undecidable
Problems about Turing Machines
UNIT - V
Decidabilty & Undecidabilty
PCP
Modified PCP
Counter
Machines
1
Types of
Turing Machine
Types of Turing Machine
Many other TM variations are equivalent to the original TM. This includes the following −
Types of Turing Machine
Multiple track Turing Machine
Types of Turing Machine
Two-way infinite Tape Turing Machine
Types of Turing Machine
Multi-tape Turing Machine
Types of Turing Machine
Multi-head Turing Machine
Types of Turing Machine
Multi-dimensional Turing Machine
Types of Turing Machine
Non-deterministic Turing Machine
Universal Turing Machine
The Turing machine has a tape of infinite length where we can perform read and write operations. The infinite cells of the Turing machine can contain input symbols and blanks. It has a head pointer that can move in any direction, it points to the cell where the input is being read.
Turing Machine
Universal Turing Machine
It simulates a Turing Machine.
Universal Turing Machine is like a single Turing Machine that has a solution to all problems that is computable.
It contains a Turing Machine description as input along with an input string, runs the Turing Machine on the input and returns a result.
Universal Turing Machine
Universal Turing Machine
Given the description of a TM (ATM) and some input (x), Can we determine whether the machine accepts it?
The Language
ATM = {<M,w> | M is a Turing Machine and M accepts w} is Turing Recognizable.
Simulate & Run the TM on the input (x)
M accepts x: Our algorithm halt and accept
M rejects x: Our algorithm halt and reject
M loops on x: Our algorithm will not halt
Universal Turing Machine
Action: Simulate M
Behave just like M would accept or reject or loop
Input: M = The description of some Turing Machine
w = An input string for M
The Universal Turing Machine is a recognizer (not a decider for ATM = {<M,w> | M is a Turing Machine and M accepts w}
Simply, Universal Turing machine is a Turing machine for running other Turing machines.
Halting Problem of Turing Machine
Input:
A Turing machine and an input string w.
Problem:
Does the Turing machine finish computing of the string w in a finite number of steps? The answer must be either yes or no.
The halting problem is a concept in computer science that refers to the challenge of determining, from a description of an arbitrary computer program and an input, whether the program will finish running, or continue to run forever.
Halting Problem of Turing Machine
Proof :
At first, we will assume that such a Turing machine exists to solve this problem and then we will show it is contradicting itself.
We will call this Turing machine as a Halting machine that produces a ‘yes’ or ‘no’ in a finite amount of time. If the halting machine finishes in a finite amount of time, the output comes as ‘yes’, otherwise as ‘no’.
Block Diagram of the Inverted Halting Machine
Now we will design an inverted halting machine (HM)| as
If H returns YES, then loop forever.
If H returns NO, then halt.
Block Diagram of the Halting Machine
Halting Problem of Turing Machine
Halting Problem of Turing Machine
Further, a machine (HM)| which input itself is constructed as follows −
If (HM)| halts on input, loop forever.
Else, halt.
Here, we have got a contradiction. Hence, the halting problem is undecidable.
2
Decidability & Undecidability
Decidability and Undecdability
A Language ‘L’ is said to be recursively enumerable if there exists a Turing machine which will accept (and therefore halt) for all the strings in ‘L’, but may or may not halt for all input strings which are not in ‘L’.
Recursive Language
Recursively Enumerable Language
A Language ‘L’ is said to be recursive if there exists a Turing machine which will accept all the strings in ‘L’ and reject all the strings not in ‘L’.
The Turing machine will halt every time and give an answer (accepted or rejected) for each and every string input.
Decidability and Undecdability
Decidable Language
A Language ‘L’ is decidable if it is a recursive language.
All decidable languages are recursive languages and vice-versa.
Partially Decidable Language
A Language ‘L’ is partially decidable if it is a recursively enumerable language.
Undecidable Language
A Language ‘L’ is undecidable if it is not decidable.
An undecidable language may sometimes be partially decidable but not decidable.
If a language is not even partially decidable, then there exists no Turing machine for that language.
Decidability and Undecdability
Recursive Language | TM will always Halt |
Recursively Enumerable Language | TM will halt sometimes & may not halt sometimes |
Decidable Language | Recursive Language |
Partially Decidable Language | Recursively Enumerable Language |
Undecidable Language | No TM for this language |
3
Undecidable Problems
Undecidable Problems
Regularity of CFL, CSL, and REC
Ambiguity of context-free languages
Everything or completeness of CFG
Equivalence of two context-free languages
Whether the language accepted by Turing Machine is regular or CFL?
Membership problem of a Turing Machine?
Emptiness of a Turing Machine?
Finiteness of a Turing Machine?
Undecidable Problems
Two popular undecidable problems are halting problem of TM and PCP
(Post Correspondence Problem).
4
Recursive Languages and its Properties
Closure Properties of Recursive Languages
RE languages are not closed under complementon which means complement of RE language need not be RE.
5
PCP
&
Modified PCP
Post Correspondence Problem
The PCP problem over an alphabet ∑ is stated as follows
Given the following two lists, M and N of non-empty strings over ∑ −
M = (x1, x2, x3,........., xn)
N = (y1, y2, y3,........., yn)
We can say that there is a Post Correspondence Solution, if for some i1,i2,............ ik, where 1 ≤ ij ≤ n,
the condition xi1 .......xik = yi1 .......yik satisfies.
The Post Correspondence Problem (PCP),
introduced by Emil Post in 1946,
is an undecidable decision problem.
Post Correspondence Problem
Find whether the lists M = (ab, bab, bbaaa) and N = (a, ba, bab) have a Post Correspondence Solution?
Find whether the lists M = (abb, aa, aaa) and N = (bba, aaa, aa) have a Post Correspondence Solution?
Post Correspondence Problem
From this we have to find some sequence in both M and N that could match
We can see that
x2x1x3 = y2y1y3 (i = 2, j = 1, and k = 3)
🡺 ‘aaabbaaa’ = ‘aaabbaaa’
Hence, we say that there is a Post Correspondance solution.
Find whether the lists M = (abb, aa, aaa) and N = (bba, aaa, aa) have a Post Correspondence Solution?
| X1 | X2 | X3 |
M | abb | aa | aaa |
N | bba | aaa | aa |
Post Correspondence Problem
Find whether the lists M = (ab, bab, bbaaa) and N = (a, ba, bab) have a Post Correspondence Solution?
The key difference between Post Correspondence Problem (PCP) and Modified Post Correspondence Problem (MPCP) is that in MPCP, the solution must start with the first string on each list.
Modified Post Correspondence Problem
The MPCP problem over an alphabet ∑ is stated as follows
Given the following two lists, M and N of non-empty strings over ∑ − M = (x1, x2, x3,........., xn) & N = (y1, y2, y3,........., yn)
We can say that there is a Post Correspondence Solution, if for some i1,i2,............ ik & j1,j2,............ jk , where 2 ≤ i,j ≤ n,
the condition x1xi1 .......xik = y1yi1 .......yik satisfies, where x1 and y1 are the first strings of each list
6
Counter
Machines
Counter Machines
Counter machine has the same structure as the multi-stack machine but in place of each stack is a counter. Counters hold any non-negative integer, but we can only distinguish between zero and nonzero counters.
Counter Machines
A counter machine is a simple kind of computer model used to understand how computation works. It’s similar to a Turing machine but uses counters instead of tapes. These counters can hold any non-negative number (like 0, 1, 2, 3...), and we can perform basic operations on them, like:
Counter Machines
A Counter Machine M = (K, Σ, ∆, s, F)
K is a set of states
Σ is the input alphabet
s ∈ K is the start state
F ⊂ K are Final states
∆ ⊆ ((K × (Σ ∪ e) × {zero,¬zero}) × (K × {−1, 0, +1}))
Accept if you reach the end of the string, end in an
accept state, and have an empty counter.
Thank You