> Then again, no real computer is Turing complete because they all have finite memory so they're strictly speaking only big finite state machines (though we do typically consider them Turing complete anyway).
Memory is only finite if it uses absolute addresses like RAM, e.g. "load 0x12345" refers to the same piece of memory, regardless of where in memory that instruction appears (ignoring complications from paging, etc.). Computers can also have external storage that's addressed relatively, e.g. a tape which can move forwards or backwards.
I like to think of Turing machines has having a "tape factory" at both ends of the tape, which appends new cells whenever the read/write head gets close. We can do the same thing with a real computer, by pausing the computer and splicing on new sections on to the tape as needed; or by extending the rails and racks of a tape robot.
Of course, our factories are ultimately limited by raw materials, even once production expands into space. The key is that relatively-addressed memory is infinitely expandable, whilst absolutely-addressed memory has a predefined upper-limit.
That is an interesting point. But the halting problem is one of those things that is only problem on a literally unbounded memory. If you have a known number of bits of state available, just run the machine for 2^bits steps. Either the machine will have halted by then or it will run forever. Now 2^bits may be astronomically huge, but there's still a big gap between that and undecidable!
> That is an interesting point. But the halting problem is one of those things that is only problem on a literally unbounded memory.
What do you mean "but"?
If you say "trust me, there's a tape factory that will kick in once you run low on space in a zillion years and it will add on another terabyte", then you do have "literally unbounded memory".
Memory is only finite if it uses absolute addresses like RAM, e.g. "load 0x12345" refers to the same piece of memory, regardless of where in memory that instruction appears (ignoring complications from paging, etc.). Computers can also have external storage that's addressed relatively, e.g. a tape which can move forwards or backwards.
I like to think of Turing machines has having a "tape factory" at both ends of the tape, which appends new cells whenever the read/write head gets close. We can do the same thing with a real computer, by pausing the computer and splicing on new sections on to the tape as needed; or by extending the rails and racks of a tape robot.
Of course, our factories are ultimately limited by raw materials, even once production expands into space. The key is that relatively-addressed memory is infinitely expandable, whilst absolutely-addressed memory has a predefined upper-limit.