News for hackers. Stuff that matters.

A comment on Rice’s Theorem: An interactive tutorial. Parent comment

Re:Rice’s Theorem: An interactive tutorial by kaba0 on Friday November 25, 2022 @01:29PM (#33745339)
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”.
[ Parent | on HN ]
Re:Rice’s Theorem: An interactive tutorial by wizeman on Friday November 25, 2022 @01:52PM (#33745569)
> 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 :)

[ Parent | on HN ]
Re:Rice’s Theorem: An interactive tutorial by kaba0 on Friday November 25, 2022 @02:56PM (#33746148)
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).

[ Parent | on HN ]