News for hackers. Stuff that matters.

A comment on Did Turing prove the undecidability of the halting problem?. Parent comment

Re:Did Turing prove the undecidability of the halting problem? by nextaccountic on Tuesday July 02, 2024 @05:11PM (#40860466)
But do we need general ways to show that any program halts? We don't write general programs

In particular, our programs have a limited size and use a limited amount of memory (or else the OS will make sure they will halt..). And for this specific class of programs, the halting problem is actually decidable!

[ Parent | on HN ]
Re:Did Turing prove the undecidability of the halting problem? by Tainnor on Wednesday July 03, 2024 @06:45AM (#40864693)
Theoretical impossibility results like this one are often interesting because they tell you there is no "smart" way even in practice beyond just brute forcing it.

While it's true that the class of programs that terminate in time at most T is decidable for trivial reasons (just run the program for at most time T), that trivial decider is of course not gonna run in time T (but at least T+1). So if you set T=time until the heat death of the universe, you haven't gained any practical ability to solve the halting problem either.

[ Parent | on HN ]