40.6k views
0 votes
Consider the problem of determining whether a two-tape Turing machine ever writes a nonblank symbol on its second tape during the course of its computation on any input string. Forμlate this problem as a language and show that it is undecidable.

a) True
b) False
c) Undecidable
d) Non-deterministic

User Daniel Ado
by
8.1k points

1 Answer

3 votes

Final answer:

The problem of determining if a two-tape Turing machine writes a nonblank symbol on the second tape is undecidable. It can be formulated as a language L and shown to be undecidable by relating it to the undecidable halting problem. The assumption of a decider leads to a contradiction, proving L's undecidability.

Step-by-step explanation:

The question asks about the decidability of a problem related to a two-tape Turing machine. Specifically, the problem is to determine whether such a machine ever writes a nonblank symbol on its second tape during its computation on any input string. We can formulate this as a language L where each string in L represents the encoding of a two-tape Turing machine M that does write a nonblank symbol on its second tape for some input. The decidability of this problem can be related to the halting problem, which is a well-known undecidable problem.

To show that our language L is undecidable, we can assume that there exists a Turing machine H that decides L. If H exists, then we could use H to decide the halting problem by constructing a modified machine M' which uses its second tape to simulate the computation of another machine on a given input and writes a nonblank symbol if and only if the simulated machine halts. However, since the halting problem is undecidable, such a machine H cannot exist, hence our original problem is also undecidable.

The correct answer to the question is therefore (c) Undecidable.

User Anton Barycheuski
by
8.2k points