Tm M Never Enters Its Initial State Again When Running on W Is Undecidable

Turing Car was invented by Alan Turing in 1936 and information technology is used to accept Recursive Enumerable Languages (generated past Type-0 Grammar).

A turing machine consists of a tape of infinite length on which read and writes operation can be performed. The tape consists of infinite cells on which each cell either contains input symbol or a special symbol called blank. Information technology also consists of a head arrow which points to prison cell currently being read and information technology tin move in both directions.

Figure: Turing Car

A TM is expressed equally a 7-tuple (Q, T, B, ∑, δ, q0, F) where:

• Q is a finite set of states
• T is the tape alphabet (symbols which can exist written on Tape)
• B is blank symbol (every prison cell is filled with B except input alphabet initially)
• ∑ is the input alphabet (symbols which are part of input alphabet)
• δ is a transition part which maps Q × T → Q × T × {L,R}. Depending on its present state and present tape alphabet (pointed by head pointer), it will move to new state, modify the tape symbol (may or may non) and motion head arrow to either left or right.
• q0 is the initial state
• F is the gear up of final states. If any state of F is reached, input cord is accepted.

Permit us construct a turing machine for 50={0^n1^n|due north>=ane}

• Q = {q0,q1,q2,q3} where q0 is initial land.
• T = {0,ane,X,Y,B} where B represents blank.
• ∑ = {0,1}
• F = {q3}

Transition function δ is given in Tabular array 1 every bit:

Illustration

Let us see how this turing auto works for 0011. Initially head points to 0 which is underlined and state is q0 every bit:

The motility will be δ(q0, 0) = (q1, X, R). It means, it will become to state q1, replace 0 by X and head will move to right as:

The motility will be δ(q1, 0) = (q1, 0, R) which means it will remain in aforementioned land and without changing any symbol, information technology will movement to right equally:

The move will be δ(q1, ane) = (q2, Y, 50) which means it will move to q2 state and irresolute 1 to Y, it will move to left as:

Working on it in the same fashion, the machine will reach state q3 and head volition point to B as shown:

Using move δ(q3, B) = halt, it will end and accepted.

Note:

• In non-deterministic turing auto, there tin can be more than than one possible motility for a given state and tape symbol, but non-deterministic TM does not add whatever power.
• Every non-deterministic TM tin be converted into deterministic TM.
• In multi-tape turing machine, there can exist more than one tape and corresponding head pointers, but information technology does non add any power to turing machine.
• Every multi-record TM can exist converted into unmarried tape TM.

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

The tabular array is interpreted as illustrated below. The entry (q1, 1, R) in row q0 and column i signifies that if M is in country q0 and reads ane on the current tape square, and then information technology writes 1 on the aforementioned tape foursquare, moves its tape caput one position to the right and transitions to land q1. Which of the post-obit statements is true about M?

1. M does not halt on any string in (0 + ane)+
2. G does non halt on any string in (00 + 1)*
3. M halts on all cord catastrophe in a 0
4. K halts on all string catastrophe in a i

Solution:  Permit us see whether car halts on cord '1'. Initially state will be q0, head will point to one as:

Using δ(q0, 1) = (q1, i, R), it will motility to country q1 and head will motility to right as:

Using δ(q1, B) = (q0, B, Fifty), information technology volition move to state q0 and caput volition move to left as:

It volition run in the same fashion again and once more and not halt.

Option D says Thousand halts on all string catastrophe with ane, but it is not halting for 1. And then, option D is wrong.

Let us see whether motorcar halts on string '0'. Initially land will be q0, head volition betoken to ane as:

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

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

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

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

Pick B says that TM does not halt for any string (00 + 1)*. Just NULL string is a part of (00 + i)* and TM will halt for Zip string. For Aught string, tape volition be,

Using δ(q0, B) = halt, TM volition halt. As TM is halting for Nada, this choice is also incorrect.
So, option (A) is right.

This article is contributed past Sonal Tuteja. Delight write comments if you find anything incorrect, or yous want to share more data about the topic discussed above

owenstross1953.blogspot.com

Source: https://www.geeksforgeeks.org/turing-machine-in-toc/

Share this post