Uttrakhand Asst. Professor Exam-74

Question

A turing machine crashes

• A. If the machine reads all the input characters without traversing some state.
• B. If the machine traverses all its states till the input remains
• C. If the transitional function is not defined
• D. None of the above

Answer 1

The Turing machine uses its transition function to map the current state and current symbol to the following: the next state, the next symbol and the movement for the tape head. If the transition function is not defined for the current state and current symbol, then the Turing machine crashes.

Halt and crash condition of Turing machine

A turing machine is said to be in halt state  if it is not able to move further.The set of  string followed from initial state to halt state is the language accepted by a Turing machine. The halt state in a turing machine is almost similar to a final state in a finite automata or push down automata with the only difference that when a turing machine enters into a halt state it does not take any further move.

If the read/write head of a turing machine is over the left most cell  and the machine is asked to take a left move it is called crash condition. Similarly, if the read/write head of the turing machine is over the right most cell  and the machine is asked to take a right move then it is also called a crash condition.

 

Answer 2

A) No problem if it didn't traverse some state.

B)Till input remains it traverse state at end it stop at some state and we can decide accordingly, No, problem in that.

C)IF transition function is not defined how would machine traverse? i.e it crashes.

Ans- C