# Where does the deterministic simulation of non-deterministic ω-Turing machines fail?

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?

-

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.