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?
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$.