Question

In: Computer Science

Show that the following problem i undecidable: Input: A Turing machine M. Output: Yes if M...

Show that the following problem i undecidable:

Input: A Turing machine M. Output: Yes if M eventually halts when started on a blank tape, no otherwise

Input: A Turing machine M and a tape symbol a. Output: Yes if M eventually writes a when started on an blank tape, no otherwise.

Input: A Turing machine M. Output: Yes if M ever writes a nonblank symbol when started on a blank tape, No otherwise.

Input: A Turing machine M and a string w over the input alphabet of M. Output: Yes if M ever moves to the left when started on w.

Solutions

Expert Solution

PLEASE LIKE IT RAISE YOUR THUMBS UP
IF YOU ARE HAVING ANY DOUBT FEEL FREE TO ASK IN COMMENT SECTION

venereology answered 6 months ago
Next > < Previous

Related Solutions

Show that the language F={M| M is a Turing machine , and L(M) contains infinite elements}...
Show that the language F={M| M is a Turing machine , and L(M) contains infinite elements} is not Turing recognizable.
Which of the following problems about Turing machines are solvable, and which are undecidable? Explain your...
Which of the following problems about Turing machines are solvable, and which are undecidable? Explain your answers carefully. (a) To determine, given a Turing machine M, a state q, and a string w, whether M ever reaches state q when started with input w from its initial state. (b) To determine, given a Turing machine M and a symbol a, whether M ever writes the symbol a when started with the empty tape.
Find the output for the following Turing machine when run on the tape b1001b, assuming that...
Find the output for the following Turing machine when run on the tape b1001b, assuming that the machine begins in state 1 and on the left side of the tape. (1, 1, 1, 2, R) (1, 0, 0, 2, R) (1, b, 1, 2, R) (2, 0, 0, 2, R) (2, 1, 0, 1, R)
Prove that a single-tape Turing Machine that is not allowed to write on the input portion...
Prove that a single-tape Turing Machine that is not allowed to write on the input portion of the tape can only recognize regular languages.
Prove that the language L={(M, N): M is a Turing machine and N is a DFA...
Prove that the language L={(M, N): M is a Turing machine and N is a DFA with L(M) =L(N)} is undecidable. You need to derive a reduction from Atm={(M, w)|Turing machine M accepts w} to L. (In layman's terms please, no other theorems involved)
Give turing Machine for L= a*i b*2j a*i b*2j where i,j>=0. Also provide the logic, show...
Give turing Machine for L= a*i b*2j a*i b*2j where i,j>=0. Also provide the logic, show 1 or 2 strings for accept, reject .
Show that Turing-decidable languages are closed under the following operations: union concatenation star Show that Turing-recognizable...
Show that Turing-decidable languages are closed under the following operations: union concatenation star Show that Turing-recognizable languages are closed under the following operations: union concatenation star Each answer needs only be a short informal description of a Turing Machine (but it must still be sufficiently precise so someone could reconstruct a formal machine if needed).
(10) Show that the Post Correspondence Problem is undecidable over the binary alphabet S = {0,...
(10) Show that the Post Correspondence Problem is undecidable over the binary alphabet S = {0, 1}.
What is the possible transition diagram of Turing Machine for the given expression? M (x, y)...
What is the possible transition diagram of Turing Machine for the given expression? M (x, y) = x + y where x and y are integers expressed in unary notation to calculate f (2,3), then the input will be 110111
* Show the output of the following BASH code: i=7 i=$((i-5)) if [ $i -eq 4...
* Show the output of the following BASH code: i=7 i=$((i-5)) if [ $i -eq 4 ] # -eq is == then         echo "Four" elif [ $i -eq 2 ] then         echo "Two" else         echo $i fi
ADVERTISEMENT
Subjects
ADVERTISEMENT
Latest Questions
ADVERTISEMENT