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

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

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

Turing machine A that does the following: • On its first and second tape, A receives...

Turing machine A that does the following: • On its first and second tape, A receives two strings w and v, w, v ∈ {0, 1}? , representing two integer numbers. When machine A is started, the tape heads are located on the left-most position, on the most significant bits of w and v. • If none of the inputs w and v is the empty word, the Turing machine A writes the binary representation of the sum of the...

Question