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 1 week 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.

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 .

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

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

* 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

Create and complete a function M-file that will receive an input, ? , and output the...

Create and complete a function M-file that will receive an input, ? , and output the corresponding conversion to radians within the range of a complete circle. For each 30? increment, the output should be displayed as a string, (i.e. pi/2 , pi/4 ,etc.), and any other degree to be displayed numerically. I'm using Matlab, explanations are appreciated.

Show that the following problem is NP-hard. Input: A boolean function in CNF such that every...

Show that the following problem is NP-hard. Input: A boolean function in CNF such that every clause has at most three literals and every variable appears in at most three clauses. Output: An assignment that evaluates the given function TRUE.

Subjects