Infinite state machine

An infinite state machine is a state machine which has a countably infinite amount of states which can be transitioned to. Infinite state machines are a kind of transfinite program.

The power of infinite state machines lies entirely in how their transitions can be defined. If they can be defined in any possible way imaginable, then infinite state machines are uncomputable.

We can imagine an infinite state machine taking in input in a given alphabet $\Sigma$. The machine may take arbitrarily long sequences of symbols. These sequences are Turing machine descriptions, with a final ending symbol. The transitions are constructed such that each symbol taken goes to a distinct state, meaning there are $|\Sigma |^{n}$ states for the nth consumed symbol. When finally taking in the end symbol, the corresponding state emits either ACCEPT or REJECT such that descriptions which halt ACCEPT and those which don't REJECT. Since we have infinite constant storage and a radically unrestricted definition scheme, this uncomputable halting problem solving machine can be created.

Restricting how infinite state machines can be defined reduces their power. Infinite state machines which can be emulated by a Turing machine with a finite preset tape are necessarily computable. Turing equivalent machines of this form may have their infinite state register operated much like a Turing machine's tape, although perhaps with an encoding similar to how universal L-systems can encode a Turing machine.

Restricting them to finite states reduces their power to that of finite state automata.