  At first glance, one-state Turing machines are very weak: the halting problem
for them is decidable, and, without memory, they cannot even accept a simple
one element language such as $L = \{ 1 \}$ . Nevertheless it has been showed
that a one-state Turing machine can accept non regular languages. We extend
such result and prove that they can also recognize non context-free languages,
so for some tasks they are more powerful than pushdown automata.

Formal Languages and Automata Theory