My Turing machine starts with an empty tape. It writes a random word of the set $0^n1^n$ to the tape. Hopefully i made no mistakes.

My question is about the productions coming out of state $q_0$:

$δ(q_0, blank)=(0,R)$ and $δ(q_0,blank)=(blank,L)$. (see image below).

Their purpose is to generate a random amount of $0$ before going to state $q_1$. They are nondeterministic. Is there a workaround to make them deterministic?

I heard that every Turing machine can be made deterministic. But this case is a little bit strange, because instead of testing if a word on the tape is element of a set, it writes a random word of the set to the tape.

Turing machine generating 0^n1^n


1 Answer 1


If a language is decided by some nondeterministic Turing machine, then it is decided by some deterministic Turing machine. However, not every behavior of a nondeterministic Turing machine can be replicated deterministically, as your example demonstrates.


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.