Infinite state machine

An infinite state machine is a state machine with countably infinitely many states.

Turing completeness

A Turing machine has three stateful components; the infinite tape, the infinite tape pointer (head), and the finite state register.

Any arbitrary Turing machine can be converted into an infinite state machine by directly translating the states into the infinite state machine. With this, the lower part of the infinite state register represents the finite state register of the Turing machine.

The higher part of the infinite state register is split into two arbitrarily large sections, one for the infinite tape, and the other for the infinite pointer.

The infinite state machine's infinite state space is then filled with countably infinitely many copies of the finite states, such that there exists one copy for each combination of infinite tape state and infinite head state.

With this, all modifications to the head, and tape, are representable by state transitions alone. Reads are constant, for any given state a read will always return the same result, as it is simply a portion of its state number, which is unchanging. Writes are large-distance transitions. Local transitions correspond to transitions in the original FSM which have no write.

If some omnipotent being were to follow this guide (or a finite being approximating it), care must be taken to ensure that all loops are translated properly. Loops generally will not only transition between local states (as that will initiate an unending loop), but also to longer distance states which represent changes to the head and/or tape.

Handling input

Input can be handled by encoding all possible inputs that can be entered into the infinite state space. E.g. consider the user inputs a true bit. State ...72 receives this, then transitions to ...73 (in the copy/universe where the input is true) if it were false then it would transition to ...73 (in the universe where it is false). Input is the only type of conditional transition that cannot be baked into the states.

Turing equivalence

It can also be proven that arbitrary infinite state machines can be mapped onto Turing machines. Split up the infinite tape into countably infinitely many chunks of arbitrarily large size. Each of these chunks contains the state's transition rule. For an infinite state machine without input, only one arbitrarily large number is required to encode the transition rule. For an infinite state machine with input, two are used, one for if the input is true, and another for false.

If the Turing machine begins at the tape location denoting state 0, it can perform an arbitrary multiple of an arbitrary number of moves in order to reach any of the infinite states. This can be thought of as a limit of a compiled program, with the size of the chunks approaching infinity.