Instantaneous Description:
• Calculate the Instantaneous Description for the string “aaaabb” by the
given Turing Machine
a b X Y B
q0 q1, X, R q4, Y, R
q1 q2, X, R
q2 q2, a, R q3, Y, L q2, Y, R
q3 q3, a, L q0, X, R q3, Y, L
q4 q4, Y, R q5, B, R
*q5
• q0 aaaabb |- X q1 aaabb |- XX q2 aabb |- XXa q2 abb |- XXaa q2 bb |- XXa q3 aYb |- XX q3 aaYb
|- X q3 XaaYb |- XX q0 aaYb |- XXX q1 aYb |- XXXX q2 Yb |- XXXXY q2 b |- XXXX q3 YY |-
XXX q3 XYY |- XXXX q0 YY |- XXXXY q4 Y |- XXXXYY q4 B |- XXXXYYB q5 B
Calculate the Instantaneous Description for the string “abbaab” and
“baaab” by the given Turing Machine
q0 baaab |- Y q3 aaab |- q4 YXaab |- Y q0 Xaab |- YX q0 aab |- YXX q1 ab |- YXXa q1 b |- YXX q2
aY |- YX q2 XaY |- YXX q0 aY |- YXXX q1 Y |- YXXXY q1 B
Language Acceptance by a Turing Machine
Turing Machine can do the following things
• Halt and Accept by entering into the final state
• Halt and Reject. This is possible if the transition is not defined i.e. δ(q,b) is not
defined.
• TM will never halt and enters into an infinite loop.
Decidable and undecidable problem
Decidable Problems
• A problem is decidable if we can construct a Turing machine which will halt in
finite amount of time for every input and give answer as ‘yes’ or ‘no’. A decidable
problem has an algorithm to determine the answer for a given input
Undecidable Problems
• The problems for which we can’t construct an algorithm that can answer the
problem correctly in finite times are termed as undecidable problem.
Recursive and Recursively Enumerable language
Recursive Language
• A language L is recursive (decidable) if L is the set of strings accepted by some Turing
Machine (TM) that halts on every input. Recursive languages are also called as Turing
decidable languages
Recursive Enumerable Language
• A language L is recursively enumerable if L is the set of strings accepted by some TM.
• If L is a recursive enumerable language then − REL
• If w ∈ L then a TM halts in a final state,
RL
• If w ∉ L then a TM halts in a non-final state or loops forever.
• If L is a recursive language then −
• If w ∈ L then a TM halts in a final state,
• If w ∉ L then TM halts in a non-final state.
Unrestricted Grammar
• Type-0 grammars generate recursively enumerable languages.
• It is also known as Phrase Structure Grammar.
• It is called unrestricted because no other restriction is made on this except each of
their left hand sides being non-empty.
• The left hand sides of the rules can contain terminal and non-terminal, but the
condition is at least of them must be non-terminal.
The unrestricted grammar is 4 tuple - G = (V,T,P,S)
V - A finite set of non-terminal symbols or variables,
T - It is a set of terminal or input symbols
P - It is a finite set of "productions" or "rules",
S - It is a start variable or non-terminal symbols.
If, α and β are two strings over the alphabet V ∪ T. Then, the rules or productions
are of the form α → β. The start variable S appears on the left side of the rule.
Halting Problem
• The Halting problem – Given a program/algorithm will ever halt or not?
• Halting means that the program on certain input will accept it and halt or reject it
and halt and it would never go into an infinite loop.
• Basically halting means terminating. So can we have an algorithm that will tell
that the given program will halt or not.
• In terms of Turing machine, will it terminate when run on some machine with
some particular given input string.
• The answer is no we cannot design a generalized algorithm which can
appropriately say that given a program will ever halt or not?
• The only way is to run the program and check whether it halts or not.
• This is an undecidable problem because we cannot have an algorithm which will
tell us whether a given program will halt or not in a generalized way i.e by having
specific program/algorithm
Extension to the basic Turing Machine:
Programming Techniques for Turing Machines:
• Multi track/Multiple tracks Turing Machine:
A single tape is assumed to be divided into several tracks, now the tape
alphabet is required to consist of k tuples of tape symbol, k being the
number of tracks.
Hence the only difference between the standard TM and TM with
multiple tracks in the set of tape symbols. In the case of the standard
TM, tape symbols are elements of , but in the case of TM with
multiple track it is . The moves are defined in a similar way.
Head reads 4 symbols at a time.