An $\omega$-Turing machine is just a usual Turing machine $T=(Q,\Sigma,\Gamma,\delta,q_0,F)$ where $Q$ is the finite set of states, $\Sigma$ is the input alphabet, $\Gamma\supset\Sigma$ is the tape alphabet, $\delta$ is is the transition relation, $q_0$ is the initial state and $F\subset Q$ is the set of accepting states. We will consider a special acceptance condition on $\omega$-words (elements of $\Sigma^\omega$): The language $L(T)\subset\Sigma^\omega$ recognised by $T$ is the set of all $\omega$-words such that—when the initial configuration is given by this word–there exists a run of $T$ such that every input token is reald only finitely many times and only states in $F$ get visited. An $\omega$-Turing machine is called deterministic iff $\delta$ is a function. The condition that an accepting must not visit any tape position infinitely often is non-essential in the non-deterministic case because we can transform every non-deterministic $\omega$-Turing machine into an equivalent one where every run is non-oscillating.

In 1978 Cohen and Gold have proved that non-deterministic $\omega$-Turing machines are strictly more powerful than deterministic ones. The argument goes as follows: They consider a larger class of deterministic $\omega$-Turing machines with more general acceptance conditions which can all be translated into equivalent non-deterministic $\omega$-Turing machines as defined above, but the languages recognisable by these machines are closed under complementation. However, using a diagonalisation argument (using a simulation of non-deterministic $\omega$-Turing machines) they prove that the general class of languages recognisable by $\omega$-Turing machines is not closed under complementation.

Now for me it is not clear why the standard simulation of non-deterministic Turing machines by deterministic ones does not work, let me sketch my approach, which must be wrong: We could try to simulate the non-deterministic machine step-by-step by computing all possible next configurations (where the states are still in $F$). The possible configurations can get bigger and bigger, but their number always remains finite. If this deterministic machine has an accepting run then by König’s lemma (which should be applicable because of the simple acceptance condition, for Büchi acceptance it would not work because there can be arbitrary large gaps between to occurences of an accepting state) in the simulated non-deterministic one there should be an accepting run, too. I think I am missing some subtle point, maybe related to the non-oscillation condition (?), but it might also be an obvious detail in the definition. Could anybody clarify that?


1 Answer 1


You say we can remove the condition that a run read every input only finitely many times, but I don't think that's so. As you noted, König's lemma shows that acceptance is a $\Pi^0_1$ property if we remove that condition. That means that the language of such a machine is a $\Pi^0_1$-class.

On the other hand, if we retain that condition, we can build a machine that accepts Fin, the set of all infinite binary strings with only finitely many 1s. Simply make a machine that scans right through the input until it sees a 1, then it turns that 1 into a 0, runs back to the beginning of the input and repeats. Since Fin is a properly $\Sigma^0_2$-class, this shows that we can achieve strictly more by retaining the condition.

I looked at the paper you linked. Your definition of accepting is what the authors call 1'-accepting, while their Theorem 8.6, which I believe you were referring to when you said we could remove the condition, is about 3-accepting. Now, the authors do show that every 3-accepting non-deterministic machine can be simulated by a 1'-accepting non-deterministic machine, but the 1'-machine they build is explicitly oscillating.

So you claim that any non-oscillating 1'-accepting non-deterministic machine can be simulated by a non-oscillating 1'-accepting deterministic machine. I'm fairly certain your argument is correct. There is no contradiction, because the proof that non-determinism is stronger than determinism was for 3-accepting machines; 1'-accepting non-oscillating machines are less general.

Note also: the authors' proof that non-determinism is strictly stronger than determinism is for the special case of non-oscillating deterministic machines. If you allowed oscillating deterministic machines, I think you could simulate non-deterministic machines by deterministic machines without too much work.

  • $\begingroup$ Thank you very much, I think that resolved my confusion. I did not realise how the possibility to reject words by oscillation makes the computation more powerful (and had different stuff in mind). $\endgroup$
    – The User
    Jul 17, 2013 at 19:20

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.