Adding extensions to automata has always been a fruitful domain. But usually, one wants to add weak capabilities, as undecidability comes quickly into the picture.

Take FSM with added stacks. It is easily seen that two stacks can simulate a Turing machine's tape, and the state control of the TM is taken care of by the FSM. Thus, such machines recognize Turing-recognizable languages.

The implicit assumption made here is that the FSM is not only non-deterministic but has $\varepsilon$-transitions, which are used to "wait" for the TM to halt.

My question is thus: what (minimal) capabilities should one add to $\varepsilon$-transition-free automata in order to make them recognize undecidable (or non-context-sensitive) languages. I'm searching for something else than an oracle for a specific language, of course!

Nota: Requiring no-$\varepsilon$-transition means that a word of length $n$ is read taking $n$ transitions. This may mean that the added power ought to be undecidable / of large space complexity by nature.

  • $\begingroup$ I agree to the last paragraph (the added power must be undecidable in nature). $\endgroup$ Commented May 3, 2011 at 18:39
  • $\begingroup$ One-way deterministic finite automata with two counters are Turing equivalent. "One-way" means the input head can stay on the square or can move one square to the right in each step. If the number of the stationary steps on a tape square is bounded by a fixed number, then we obtain a realtime (instead of one-way) model. (If no stationary movement is allowed, then it is called strictly realtime.) Is the basic model in your question realtime deterministic finite automaton? $\endgroup$ Commented Apr 16, 2013 at 8:02

2 Answers 2


I do not think it is possible at all. Either such automata cannot be recursively defined, or have to make local non-recursive decisions at nodes. The first case is obviously uninteresting, and the latter is equivalent to having undecidable oracles at nodes.


If time(n) for a class of automata is bounded by a total function, the languages accepted are recursive. Why? Just simulate and reject after time(n) steps. This is a fundamental fact of recursion and complexity theory. So if there are no e-input moves, time(n) <= n, which is certainly computable, and the languages accepted are recursive.

But just adding e-moves to a model does not guarantee that non-recursive languages will be accepted. For example, a finite state automaton model (no or uniformly-bounded auxiliary storage and inability to use unbounded amounts of input tape) with e-moves still accepts only regular languages.

To add power to a model that makes some languages it defines non-recursive, the added power would have to interfere with the time function to make it partial, that is, undefined for some inputs. For example, if a machine purports to solve the halting problem by simulating the universal turing machine, then it would have to compute indefinitely long without consuming any input when simulating a non-halting computation, so its time() would be a partial function, undefined for some inputs.

There is probably a theorem to the effect that any "local" modification (suitably defined) to a model with a total time() function does not guarantee non-recursive behavior, that is, any modification which simply changes what automata in the model can do on a specific move, like make certain kinds of alterations in the auxiliary store. You'd have to look at whether the modification globally increases time and/or space without bound. For example, allowing a machine to tack on extra input tape whenever it wants, like an unrestricted one-tape turing machine, obviously increases auxiliary space without bound, and does, in fact, lead to defining non-recursive languages.

So I don't think the notion of e-transitions will, by itself, lead to a model that accepts non-recursive languages.


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.