The Power of One-State Turing Machines
source link: http://www.nearly42.org/cstheory/the-power-of-one-state-turing-machines/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
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).
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK