ISRO2014-59

Question

Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?

• A. it may halt and accept the input
• B. it may halt by changing the input
• C. it may halt and reject the input
• D. it may never halt

Answer 1

Intuitively option B might be correct.

If the input belongs to a recursive language, either it may halt and accept the input or it may halt and reject the input.

If the input belongs to a recursively enumerable language, then either it may halt and accept the input or it may never halt.

I don't think it can halt by changing the input, because TM just transits from one state to another state on a given input. It only does the transitions that it is supposed to do on the given input as per it's definition.

TM is like a slave and input is like the command given by a master, so possibly it can not alter commands given to it. However I am not very sure about it.

Comments

"101" on input tape can change to "01111" rt? I don't understand the "b" option..

---

Yes sir, I interpreted option B as it can change input from "101" to "01111". This statement seems incorrect because although a TM can mark on input with its read write head but it can not change the input.

---

There are three possible out come of Turing machine.

it may halt and accept the input
it may halt and reject the input
it may never halt

Answer is ' B '

---

ya,  turing mc can have only 3 possibility till now . and major problem  is to solve halting problem which is undecidable.