Consider an automaton with a countably infinite number of states. This machine could, given it's current state and a symbol from the input alphabet, move to another arbitrary state in a finite amount of time.

What would the computational power of such an (obviously not physically realizable) device?

In particular, could it compute any function computable by a Turing Machine? Could it even solve the halting problem for a Turing Machine?

  • $\begingroup$ By a countable state automata, I mean a machine precisely the same as a finite state automata (en.wikipedia.org/wiki/Finite-state_machine#Mathematical_model) but with the set of states, $S$, a countably infinite set rather than a finite set. The transition function could be any function $\delta : S \times \Sigma \rightarrow S$ $\endgroup$ – eepperly16 Jun 1 '16 at 22:59
  • $\begingroup$ Such an automaton would be able to recognize the language $\{0^n1^n:n\in\mathbb N\}$, I suppose.. $\endgroup$ – Math1000 Jun 1 '16 at 23:03
  • 2
    $\begingroup$ cstheory.stackexchange.com/q/20688/16998 $\endgroup$ – mvw Jun 1 '16 at 23:17

Let $A$ be a finite alphabet and let $L$ be any language of $A^*$. Then $L$ is accepted by the countable automaton $\mathcal{A} = (A^*, A, \cdot, 1, L)$, where the set of states is $A^*$, the initial state is the empty word $1$, the set of final states is $L$ and the transition function is given by $u \cdot a = ua$, for any $u \in A^*$ and $a \in A$.

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.