Summary:
Computability of finite automata with one head, and computational equivalence.
Complexity classes of those finite automata, complete problems, open problems,
reductions, relations with turing machine complexity. Search for a reduction,
to find a complete problem in classes with constant input. Counterexamples.
Keywords:
Computability, Complexity, Automata, Non-deterministic automaton
