# Automata model with undecidable (or non-context-sensitive) languages and no $\varepsilon$-transitions.

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.

• I agree to the last paragraph (the added power must be undecidable in nature). – Tsuyoshi Ito May 3 '11 at 18:39
• 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? – Abuzer Yakaryilmaz Apr 16 '13 at 8:02