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
.