3 ms·
You're pointing out that a machine that can grow without bound is mathematically equivalent to an infinite one. There's a reason the word "finite" is part of "f
by russdill 3y ago
You're pointing out that a machine that can grow without bound is mathematically equivalent to an infinite one. There's a reason the word "finite" is part of "finite state machine". If you have a state machine that can grow without bound, it's not an FSM and is capable of computing things an FSM cannot compute.
And the halting problem is solvable for any finite machine. A finite machine has a finite number of states. You only need to run N steps where N is the number of possible states. If it hasn't halted at that point, it must run forever.
- yarg 3y ago> You only need to run N steps where N is the number of possible states. It's at most N steps - the machine can return to a prior state long before that happens, which would also prove that it's non-halting. Of course the memory requirements to do that make it purely theoretical - but so too is exhaustive execution (due to time requirements). https://en.wikipedia.org/wiki/Busy_beaver#Exact_values_and_lower_bounds https://en.wikipedia.org/wiki/Busy_beaver#Exact_values_and_l...
- deleted 3y ago[deleted]