Turing machines with activations of transitions

Abstract

We consider Turing machines which perform infinite sequences of runs, where the (finite) number of computation steps is in each run is defined by the transitions activated in the preceding run when using a transition activated for this computation step in this preceding run. Acceptance is defined by the non-oscillating sequences of runs, i.e., for every tape cell n there exists a run r(n) such that in all runs after run r(n) the contents of tape cell n is not changed any more. In that way, with deterministic Turing machines we can characterize ∏03 , whereas with non-deterministic Turing machines we obtain ∑11 .