1
$\begingroup$

The only thing I found online about this is the following blog: http://blog.computationalcomplexity.org/2005/03/tape-reduction.html

where they write:

Roughly the simulation guesses every step of the transition function on one tape and uses the other tape to verify the transition function on each tape of the original machine one tape at a time.

How exactly do you guess the transition function? And if you guess it, then why do you need to verify it? Isn't the guess in non deterministic turing machines always correct?

$\endgroup$

1 Answer 1

1
$\begingroup$

I think the idea is that we can run with just the first tape of the original machine while pretend other $k-1$ tapes exist. We pretend knowing states of other tapes by guessing every possible ones.

After the first tape executed, for those machines stopped in accept state, run with the second tape to see whether the guesses with respect to that tape were correct. Reject all wrong guesses. Repeat until all $k$ tapes are executed.

Isn't the guess in non deterministic turing machines always correct?

For NDTMs, "correct guess" is that guess which will lead the machine into accept state. We need to reject all incorrect guesses by verifying them to make only the correct guesses (for our problem) correct (for NDTM).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.