UNIT V-TOC

 Unit-V

Turing Machine (TM) TM Definition, Model Of Computation, Turing Machine as Language Acceptor, TM that Compute Partial Function, Church Turing Thesis, Combining TM, Variations Of TM, Non Deterministic TM, Universal TM, Recursively and Enumerable Languages, Context sensitive languages and Chomsky hierarchy.

5.1)Turing Machine (TM) TM Definition

A Turing Machine is an accepting device which accepts the languages (recursively enumerable set) generated by type 0 grammars. It was invented in 1936 by Alan Turing.

Definition

A Turing Machine (TM) is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape.

A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected.

A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q₀, B, F) where −

• Q is a finite set of states
• X is the tape alphabet
• ∑ is the input alphabet
• δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.
• q₀ is the initial state
• B is the blank symbol
• F is the set of final states

Comparison with the previous automaton

The following table shows a comparison of how a Turing machine differs from Finite Automaton and Pushdown Automaton.

Machine	Stack Data Structure	Deterministic?
Finite Automaton	N.A	Yes
Pushdown Automaton	Last In First Out(LIFO)	No
Turing Machine	Infinite tape	Yes

Example of Turing machine

Turing machine M = (Q, X, ∑, δ, q₀, B, F) with

• Q = {q₀, q₁, q₂, q_f}
• X = {a, b}
• ∑ = {1}
• q₀ = {q₀}
• B = blank symbol
• F = {q_f }

δ is given by −

Tape alphabet symbol	Present State q0	Present State q1	Present State q2
a	1Rq1	1Lq0	1Lqf
b	1Lq2	1Rq1	1Rqf

Here the transition 1Rq₁ implies that the write symbol is 1, the tape moves right, and the next state is q₁. Similarly, the transition 1Lq₂ implies that the write symbol is 1, the tape moves left, and the next state is q₂.

Time and Space Complexity of a Turing Machine

For a Turing machine, the time complexity refers to the measure of the number of times the tape moves when the machine is initialized for some input symbols and the space complexity is the number of cells of the tape written.

Time complexity all reasonable functions −

T(n) = O(n log n)

TM's space complexity −

S(n) = O(n)

The Turing Machine is the basic fundamental model of a modern computer. It is an abstract model of computation. It was proposed by Alan Turing in 1936. At that time, there were no computers. The Turing machine can carry out any computational process that a modern computer can perform. It is the machine format of unrestricted language.

Basics of Turing Machine

A Turing machine (TM) is defined by 7 tuples: (Q, Σ, Γ, δ, q0, B, F)

• Q − Finite set of states
• Σ − Finite set of input alphabets
• Γ − Finite set of allowable tape symbols
• δ − Transitional function
• q0 − Initial state
• B − A symbol of Γ called blank
• F − Final state

Mechanical Diagram of Turing Machine

A Turing machine consists of three main parts: an input tape, a read-write head, finite control.

The input tape contains the input alphabets. It has an infinite number of blanks at the left and right side of the input symbols. The read-write head reads an input symbol from the input tape and sends it to the finite control. The machine must be in some state. In the finite control, the transitional functions are written. Based on the present state and the present input, a suitable transitional function is executed.

Operations of Turing Machine

When a transitional function is executed, the Turing machine performs these operations −

• The machine goes into some state.
• The machine writes a symbol in the cell of the input tape from where the input symbol was scanned.
• The machine moves the reading head to the left or right or halts.

Instantaneous Description (ID) of Turing Machine

The Instantaneous Description (ID) of a Turing machine remembers the following at a given instance of time −

• The contents of all the cells of the tape, starting from the rightmost cell up to at least the last cell, containing a non-blank symbol and containing all cells up to the cell being scanned.
• The cell currently being scanned by the read-write head.
• The state of the machine.

 

 

Transition function δ is given in Table 1 as: 

Question: A single tape Turing Machine M has two states q0 and q1, of which q0 is the starting state. The tape alphabet of M is {0, 1, B} and its input alphabet is {0, 1}. The symbol B is the blank symbol used to indicate end of an input string. The transition function of M is described in the following table. 

The table is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column 1 signifies that if M is in state q0 and reads 1 on the current tape square, then it writes 1 on the same tape square, moves its tape head one position to the right and transitions to state q1. Which of the following statements is true about M? 
 

1.    M does not halt on any string in (0 + 1)+

2.    M does not halt on any string in (00 + 1)*

3.    M halts on all string ending in a 0

4.    M halts on all string ending in a 1

Solution:  Let us see whether machine halts on string ‘1’. Initially state will be q0, head will point to 1 as: 

 

Using δ(q0, 1) = (q1, 1, R), it will move to state q1 and head will move to right as: 

Using δ(q1, B) = (q0, B, L), it will move to state q0 and head will move to left as: 

                

It will run in the same way again and again and not halt. 

Option D says M halts on all string ending with 1, but it is not halting for 1. So, option D is incorrect. 

Let us see whether machine halts on string ‘0’. Initially state will be q0, head will point to 1 as: 

Using δ(q0, 0) = (q1, 1, R), it will move to state q1 and head will move to right as: 

Using δ(q1,B)=(q0,B,L), it will move to state q0 and head will move to left as: 

 

It will run in the same way again and again and not halt. 

Option C says M halts on all string ending with 0, but it is not halting for 0. So, option C is incorrect. 

Option B says that TM does not halt for any string (00 + 1)*. But NULL string is a part of (00 + 1)* and TM will halt for NULL string. For NULL string, tape will be, 

Using δ(q0, B) = halt, TM will halt. As TM is halting for NULL, this option is also incorrect. 
So, option (A) is correct.

5.2)Basic model of computation:

5.3)Language accepted by Turing machine  

UNIT V - Turing Machines & Undecidability Study Material - Studocu

 

Language accepted by Turing machine

The turing machine accepts all the language even though they are recursively enumerable. Recursive means repeating the same set of rules for any number of times and enumerable means a list of elements. The TM also accepts the computable functions, such as addition, multiplication, subtraction, division, power function, and many more.

Example:

Construct a turing machine which accepts the language of aba over ∑ = {a, b}.

Solution:

We will assume that on input tape the string 'aba' is plac

The tape head will read out the sequence up to the Δ characters. If the tape head is readout 'aba' string then TM will halt after reading Δ.

Now, we will see how this turing machine will work for aba. Initially, state is q0 and head points to a as:

                       

The move will be δ(q0, a) = δ(q1, A, R) which means it will go to state q1, replaced a by A and head will move to right as:

                  

The move will be δ(q1, b) = δ(q2, B, R) which means it will go to state q2, replaced b by B and head will move to right as:

                  

The move will be δ(q2, a) = δ(q3, A, R) which means it will go to state q3, replaced a by A and head will move to right as:

The move δ(q3, Δ) = (q4, Δ, S) which means it will go to state q4 which is the HALT state and HALT state is always an accept state for any TM.

The same TM can be represented by Transition Table:

States	a	b	Δ
q0	(q1, A, R)	-	-
q1	-	(q2, B, R)	-
q2	(q3, A, R)	-	-
q3	-	-	(q4, Δ, S)
q4	-	-	-

 

The same TM can be represented by Transition Diagram:

 

5.4)TM That Compute Partial Computation

https://www.youtube.com/watch?v=LtBDRRuxTyg

 

5.5)Church Turing Thesis

In 1936, A method named as lambda-calculus was created by Alonzo Church in which the Church numerals are well defined, i.e. the encoding of natural numbers. Also in 1936, Turing machines (earlier called theoretical model for machines) was created by Alan Turing, that is used for manipulating the symbols of string with the help of tape.

Church Turing Thesis :

Turing machine is defined as an abstract representation of a computing device such as hardware in computers. Alan Turing proposed Logical Computing Machines (LCMs), i.e. Turing’s expressions for Turing Machines. This was done to define algorithms properly. So, Church made a mechanical method named as ‘M’ for manipulation of strings by using logic and mathematics. This method M must pass the following statements:

• Number of instructions in M must be finite.

• Output should be produced after performing finite number of steps.

• It should not be imaginary, i.e. can be made in real life.

• It should not require any complex understanding.

Using these statements Church proposed a hypothesis called

Church’s Turing thesis

that can be stated as: “The assumption that the intuitive notion of computable functions can be identified with partial recursive functions.”

Or in simple words we can say that “Every computation that can be carried out in the real world can be effectively performed by a Turing Machine.”

In 1930, this statement was first formulated by Alonzo Church and is usually referred to as Church’s thesis, or the Church-Turing thesis. However, this hypothesis cannot be proved. The recursive functions can be computable after taking following assumptions:

1.    Each and every function must be computable.

2.    Let ‘F’ be the computable function and after performing some elementary operations to ‘F’, it will transform a new function ‘G’ then this function ‘G’ automatically becomes the computable function.

3.    If any functions that follow above two assumptions must be states as computable function.

5.6)Combining TM:

https://www.youtube.com/watch?v=jCS9fNVBZ6w

 

5.7)Variation of Turing Machine

1. Multiple track Turing Machine: 

• A k-track Turing machine(for some k>0) has k-tracks and one R/W head that reads and writes all of them one by one.

• A k-track Turing Machine can be simulated by a single track Turing machine

 

2. Two-way infinite Tape Turing Machine: 

• Infinite tape of two-way infinite tape Turing machine is unbounded in both directions left and right.

• Two-way infinite tape Turing machine can be simulated by one-way infinite Turing machine(standard Turing machine).

3. Multi-tape Turing Machine: 

• It has multiple tapes and is controlled by a single head.

• The Multi-tape Turing machine is different from k-track Turing machine but expressive power is the same.

• Multi-tape Turing machine can be simulated by single-tape Turing machine.

4. Multi-tape Multi-head Turing Machine: 

• The multi-tape multi-head Turing machine has multiple tapes and multiple heads

• Each tape is controlled by a separate head

• Multi-Tape Multi-head Turing machine can be simulated by a standard Turing machine.

5. Multi-dimensional Tape Turing Machine: 

• It has multi-dimensional tape where the head can move in any direction that is left, right, up or down.

• Multi dimensional tape Turing machine can be simulated by one-dimensional Turing machine

6. Multi-head Turing Machine: 

• A multi-head Turing machine contains two or more heads to read the symbols on the same tape.

• In one step all the heads sense the scanned symbols and move or write independently.

• Multi-head Turing machine can be simulated by a single head Turing machine.

7. Non-deterministic Turing Machine: 

• A non-deterministic Turing machine has a single, one-way infinite tape.

• For a given state and input symbol has at least one choice to move (finite number of choices for the next move), each choice has several choices of the path that it might follow for a given input string.

• A non-deterministic Turing machine is equivalent to the deterministic Turing machine.

5.7)Non-Deterministic Turing Machine

In a Non-Deterministic Turing Machine, for every state and symbol, there are a group of actions the TM can have. So, here the transitions are not deterministic. The computation of a non-deterministic Turing Machine is a tree of configurations that can be reached from the start configuration.

An input is accepted if there is at least one node of the tree which is an accept configuration, otherwise it is not accepted. If all branches of the computational tree halt on all inputs, the non-deterministic Turing Machine is called a Decider and if for some input, all branches are rejected, the input is also rejected.

A non-deterministic Turing machine can be formally defined as a 6-tuple

 (Q, X, ∑, δ, q₀, B, F) where −

• Q is a finite set of states
• X is the tape alphabet
• ∑ is the input alphabet
• δ is a transition function;

δ : Q × X → P(Q × X × {Left_shift, Right_shift}).

• q₀ is the initial state
• B is the blank symbol
• F is the set of final states

 

 

Explain about Non-Deterministic turing machine:

Non-determinism like in PDA (partially NFA) for one input configuration has several possible outputs.

The non-deterministic TM is like TM but with a finite number of choices of moves; may have more than 1 move with the same input “current state & current symbol”.

The non-deterministic TM accepts the input w if there is at least one computation that halts normally for the input w.

Non-determinism is more powerful than determinism for pushdown automata. But it makes no difference for finite automata.

Quite surprisingly, the deterministic and non-deterministic Turing machines are the same in power.

Note:

If a nondeterministic Turing machine accepts a language L, then there is a deterministic Turing machine that also accepts L.

There are many other similar machines, which might look more or less powerful, but which can be seen to be equivalent in power to the simple Turing machine (recognise the same recursive enumerable languages generated by the unrestricted grammars) − adding more tapes, more control units, . . .

 

 

 

5.8)Universal Turing machine

The Turing Machine (TM) is the machine level equivalent to a digital computer.

It was suggested by the mathematician Turing in the year 1930 and has become the most widely used model of computation in computability and complexity theory.

The model consists of an input and output. The input is given in binary format form on to the machine’s tape and the output consists of the contents of the tape when the machine halts

The problem with the Turing machine is that a different machine must be constructed for every new computation to be performed for every input output relation.

This is the reason the Universal Turing machine was introduced which along with input on the tape takes the description of a machine M.

The Universal Turing machine can go on then to simulate M on the rest of the content of the input tape.

A Universal Turing machine can thus simulate any other machine.

The idea of connecting multiple Turing machine gave an idea to Turing −

• Can a Universal machine be created that can ‘simulate’ other machines?
• This machine is called as Universal Turing Machine

This machine would have three bits of information for the machine it is simulating

• A basic description of the machine.
• The contents of machine tape.
• The internal state of the machine.

The Universal machine would simulate the machine by looking at the input on the tape and the state of the machine.

It would control the machine by changing its state based on the input. This leads to the idea of a “computer running another computer”.

It would control the machine by changing its state based on the input. This leads to the idea of a “computer running another computer”.

The schematic diagram of the Universal Turing Machine is as follows −

 

5.9)Recursive and Enumerable Languages

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.

Example

When a Turing machine reaches a final state, it halts. We can also say that a Turing machine M halts when M reaches a state q and a current symbol ‘a’ to be scanned so that δ(q, a) is undefined.

There are TMs that never halt on some inputs in any one of these ways, So we make a distinction between the languages accepted by a TM that halts on all input strings and a TM that never halts on some input strings.

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 −

If w ∈ L then a TM halts in a final state,

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.

Recursive Languages are also recursive enumerable

Proof − If L is a recursive then there is TM which decides a member in language then −

• M accepts x if x is in language L.
• M rejects on x if x is not in language L.

According to the definition, M can recognize the strings in language that are accepted on those strings.

 

5.10)Context sensitive language Chomsky hierarchy

Context-Sensitive Grammar –
A Context-sensitive grammar is an Unrestricted grammar in which all the productions are of form –

Where α and β are strings of non-terminals and terminals.

Context-sensitive grammars are more powerful than context-free grammars because there are some languages that can be described by CSG but not by context-free grammars and CSL are less powerful than Unrestricted grammar. That’s why context-sensitive grammars are positioned between context-free and unrestricted grammars in the Chomsky hierarchy.

Context-sensitive grammar has 4-tuples. G = {N, Σ, P, S}, Where
N = Set of non-terminal symbols
Σ = Set of terminal symbols
S = Start symbol of the production
P = Finite set of productions
All rules in P are of the form α₁ A α₂ –> α₁ β α₂

Context-sensitive Language: 

The language that can be defined by context-sensitive grammar is called CSL. Properties of CSL are :

• Union, intersection and concatenation of two context-sensitive languages is context-sensitive.
• Complement of a context-sensitive language is context-sensitive.

Example –

Consider the following CSG.
S → abc/aAbc
Ab → bA
Ac → Bbcc
bB → Bb
aB → aa/aaA

What is the language generated by this grammar?

Solution:
S → aAbc
→ abAc
→ abBbcc
→ aBbbcc
→ aaAbbcc
→ aabAbcc
→ aabbAcc
→ aabbBbccc
→ aabBbbccc
→ aaBbbbccc
→ aaabbbccc
The language generated by this grammar is {aⁿbⁿcⁿ | n≥1}.

Context sensitive language:

A context-sensitive grammar whose productions are of the form

αAβ → αγβ

Where α, β ∈ (N ∪ T)*, A ∈ N; γ ∈ (N ∪ T)+ and a rule of the form S → λ is allowed if the start symbol S do not appear on the right hand side of any rule.

The language generated by such a grammar is called a context-sensitive language.

• Every context-free grammar is also context-sensitive =⇒ the context-free languages are a subset of the context-sensitive languages (see Chomsky Normal Form).
• But, not every context-sensitive language is context-free.

Example

The language {anbncn, n > 1} is context-sensitive but not context free.

A grammar for this language is given by:

S → aSBC | aBC,

CB → HB,

HB → HC,

HC → BC,

aB → ab,

bB → bb,

bC → bc,

cC → cc

A derivation e.g. aabbcc, using this grammar is:

S ⇒ aSBC

   ⇒ aaBCBC (using S → aBC)

   ⇒ aabCBC (using aB → ab)

   ⇒ aabHBC (using CB → HB)

   ⇒ aabHCC (using HB → HC)

   ⇒ aabBCC (using HC → BC)

   ⇒ aabbCC (using bB → bb)

   ⇒ aabbcC (using bC → bc)

   ⇒ aabbcc (using cC → cc)

The context-sensitive languages can also be generated by a monotonic grammar, any production is allowed, as long as there are no rules for making strings shorter (except one S → ∧)!

5.11)Chomsky Hierarchy

Chomsky Hierarchy represents the class of languages that are accepted by the different machine. The category of language in Chomsky's Hierarchy is as given below:

1.    Type 0 known as Unrestricted Grammar.

2.    Type 1 known as Context Sensitive Grammar.

3.    Type 2 known as Context Free Grammar.

4.    Type 3 Regular Grammar.

This is a hierarchy. Therefore every language of type 3 is also of type 2, 1 and 0. Similarly, every language of type 2 is also of type 1 and type 0, etc.

Type 0 Grammar:

Type 0 grammar is known as Unrestricted grammar. There is no restriction on the grammar rules of these types of languages. These languages can be efficiently modeled by Turing machines.

For example:

Advertisement

1.    bAa → aa  

2.    S → s  

Type 1 Grammar:

Type 1 grammar is known as Context Sensitive Grammar. The context sensitive grammar is used to represent context sensitive language. The context sensitive grammar follows the following rules:

• The context sensitive grammar may have more than one symbol on the left hand side of their production rules.

• The number of symbols on the left-hand side must not exceed the number of symbols on the right-hand side.

• The rule of the form A → ε is not allowed unless A is a start symbol. It does not occur on the right-hand side of any rule.

• The Type 1 grammar should be Type 0. In type 1, Production is in the form of V → T

Where the count of symbol in V is less than or equal to T.

For example:

1.    S → AT  

2.    T → xy  

3.    A → a  

Type 2 Grammar:

Type 2 Grammar is known as Context Free Grammar. Context free languages are the languages which can be represented by the context free grammar (CFG). Type 2 should be type 1. The production rule is of the form

1.    A → α  

Where A is any single non-terminal and is any combination of terminals and non-terminals.

For example:

1.    A → aBb  

2.    A → b  

3.    B → a  

Type 3 Grammar:

Type 3 Grammar is known as Regular Grammar. Regular languages are those languages which can be described using regular expressions. These languages can be modeled by NFA or DFA.

Type 3 is most restricted form of grammar. The Type 3 grammar should be Type 2 and Type 1. Type 3 should be in the form of

1.    V → T*V / T*  

For example:

1. A → xy