3 ms·

> 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-sta

> 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”. Sorry, I don't understand this argument :)

kaba0 4y ago
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).