Let S={0,1}n be the state space of our finite/physical computer, where n is the number of bits of state the computer has. This can include RAM, non-volatile storage, CPU registers, cache, GPU RAM, etc… just add up all the bits.
The stateless parts of the computer can be modeled as a state transition function f:S→S, which is applied at every time step to produce the next state. (And let’s suppose that there is some special halting state h∈S.)
This is clearly a FSM with 2n states, and not TC. The halting problem can be trivially solved for it: it is guaranteed to either halt or loop after 2n steps.
(Proof: It can be seen that if we ever get back to a state where we have already been, we will loop. So let’s suppose that after 2n time we have had a different state at each time step, and haven’t halted. This is impossible, since there are only |S|−1=2n−1 non-halting states, so there cannot exist 2n distinct ones.)
Notably, this is why we focus on the arbitrarily large memory and time case, where we can assume that the machine has arbitrarily large memory and time to work with.
The key question here is whether a finite physical computer can always be extended with more memory and time without requiring us to recode the machine into a different program/computer, and most modern computers can do this (modulo physical issues of how you integrate more memory and time).
In essence, the key property of modern computers is that the code/systems descriptor doesn’t change if we add more memory and time, and this is the thing that leads to Turing-completeness if we allow unbounded memory and time.
Let S={0,1}n be the state space of our finite/physical computer, where n is the number of bits of state the computer has. This can include RAM, non-volatile storage, CPU registers, cache, GPU RAM, etc… just add up all the bits.
The stateless parts of the computer can be modeled as a state transition function f:S→S, which is applied at every time step to produce the next state. (And let’s suppose that there is some special halting state h∈S.)
This is clearly a FSM with 2n states, and not TC. The halting problem can be trivially solved for it: it is guaranteed to either halt or loop after 2n steps.
(Proof: It can be seen that if we ever get back to a state where we have already been, we will loop. So let’s suppose that after 2n time we have had a different state at each time step, and haven’t halted. This is impossible, since there are only |S|−1=2n−1 non-halting states, so there cannot exist 2n distinct ones.)
Notably, this is why we focus on the arbitrarily large memory and time case, where we can assume that the machine has arbitrarily large memory and time to work with.
The key question here is whether a finite physical computer can always be extended with more memory and time without requiring us to recode the machine into a different program/computer, and most modern computers can do this (modulo physical issues of how you integrate more memory and time).
In essence, the key property of modern computers is that the code/systems descriptor doesn’t change if we add more memory and time, and this is the thing that leads to Turing-completeness if we allow unbounded memory and time.