# Countable State Automata

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?

• 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$ – eepperly16 Jun 1 '16 at 22:59
• Such an automaton would be able to recognize the language $\{0^n1^n:n\in\mathbb N\}$, I suppose.. – Math1000 Jun 1 '16 at 23:03
• cstheory.stackexchange.com/q/20688/16998 – 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$.