While you are right that our hardware with a finite amount of RAM is not a Turing-machine, you should not forget that it is usually not just a CPU and a RAM module with no side effects. Does writing to HDD extend your tape? Sending a post request on the internet and storing data on another computer, hell, controlling some physical machine pouring concrete into a hole? These all extend the same tape, effectively turning the whole universe into one. And while you might even go as far to claim that the universe itself is not infinite, and you would be right again! There are a finite amount of atoms, but I’m not really sure it is a good rebuke of the Halting problem that “we can brute force our way out of it”.
I think that’s what makes computability theory interesting, especially if you add that our very Mathematics “break down” at a “trivially” small scale and that Turing machines will happily go on and on, literally being mathematically reasoned about, because we hit the edges of it sooner!
Not the whole universe, exactly. Just the parts that are possible to access :)
> I’m not really sure it is a good rebuke of the Halting problem that “we can brute force our way out of it”.
Why do you think the only way to solve the Halting problem on a model of a machine with finite memory is to brute-force our way out of it?
Another person mentioned the same thing, that it would take an exponential number of steps (in the number of bits in the state space) to simulate running a program.
But why are you both assuming we can only solve the problem by simulating running the program and not by analyzing the program description?
Now you are just back at the Halting theorem, and thus Rice’s theorem. The only question here is whether a computer is a Turing-machine, and frankly it is a weird hill to die on. With arbitrary side effects, you are back to “can the heat death of the universe be considered O(1)”, which is, well an interesting thought, but that just demonstrates infinity’s “size”.
> Now you are just back at the Halting theorem, and thus Rice’s theorem.
How so?
We know the Halting theorem and Rice's theorem to be decidable for finite-state machines, so how does that prove anything about the time complexity of analyzing whether the program halts?
> The only question here is whether a computer is a Turing-machine
For me that's an absurd question, as it's impossible to build a machine as powerful as a Turing machine.
> With arbitrary side effects, you are back to “can the heat death of the universe be considered O(1)”, which is, well an interesting thought, but that just demonstrates infinity’s “size”.
As mentioned by others, a Turing machine doesn’t/can’t use infinite amount of memory, even if all it does is to step right and write a 1, it will use n bits of memory in n steps, so I don’t see how would our “finite” universe be a limiting factor here that would force our computers to be FSAs.
My point regarding the heat death of the universe is that ad absurdum you can only use that amount of energy for your calculations, if every “Turing machine”-step takes a fixed amount of energy, which will indeed be a final number, and thus the O notation applies to that, making everything O(1), QED. But.. I don’t see why would the Turing machine model break down as an analogy to existing computers, programs, hell, real life (as it is one way to represent everything computable).
I think that’s what makes computability theory interesting, especially if you add that our very Mathematics “break down” at a “trivially” small scale and that Turing machines will happily go on and on, literally being mathematically reasoned about, because we hit the edges of it sooner!