The Power of One-State Turing Machines
classification
💻 cs.FL
keywords
one-statetheyturingacceptlanguagesmachinesautomatabeen
pith:WIDSVHDO Add to your LaTeX paper
What is a Pith Number?\usepackage{pith}
\pithnumber{WIDSVHDO}
Prints a linked pith:WIDSVHDO badge after your title and writes the identifier into PDF metadata. Compiles on arXiv with no extra files. Learn more
read the original abstract
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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.