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.