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.

Expert Solution

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

venereology answered 9 months ago

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.

Turing Machine and Closure Operations Show that Turing-recognizable languages are closed under the following operations: union...

Turing Machine and Closure Operations 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). Also, be careful with non-termination (when appropriate)!

Turing Machine and Closure Operations Show that Turing-decidable languages are closed under the following operations: union...

Turing Machine and Closure Operations Show that Turing-decidable languages are closed under the following operations: union concatenation star

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= ai b2j ai b2j 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 .

(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}.

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).

Question