A one-state Turing machine is a very weak device: it has no internal memory and it cannot even recognize the trivial language $L = \{1\}$. Its transition function is a simple map $\delta : \Sigma \to \Sigma \times \{L,R\}$, i.e. given the symbol under its head it can rewrite it with another one and move left or right, but the state remains the same. Nevertheless it can use its ability to write on the tape to “gain” some memory; in particular in each cell $C_i$ of the tape it can store:
- the number $n$ of times the head visited $C_i$ modulo a fixed constant $k$;
- if it has entered $C_i$ from the left or from the right.
This information is enough to build $k$-ary counters and also a sort of comparator between numbers written in different bases. So, some one-state Turing machines can “recognize” languages that are not Context-Free (the quotes are due to a different accept/reject conditions that are necessary because we cannot distinguish between accepting and non accepting states).