News for hackers. Stuff that matters.

A comment on Computation as a Universal and Fundamental Concept. Parent comment

Re:Computation as a Universal and Fundamental Concept by masfuerte on Saturday July 11, 2026 @07:56AM (#48871249)
> For any particular Java program, there's obviously an algorithm that says whether it halts or not. The algorithm is a single statement, which says either "yes" or "no".

This isn't true.

In general, if a program hasn't halted yet you don't know if it will.

In particular, consider the Collatz conjecture. You can't even tell if your Java implementation of it will halt for a particular input, until it does.

https://en.wikipedia.org/wiki/Collatz_conjecture

[ Parent | on HN ]
Re:Computation as a Universal and Fundamental Concept by Twey on Saturday July 11, 2026 @09:39AM (#48871969)
And yet there is a correct algorithm — it's either the const yes algorithm or the const no algorithm.

We don't _know_ which algorithm it is, but that's not relevant to the definition of undecidability, which only requires that the algorithm exist.

[ Parent | on HN ]
Re:Computation as a Universal and Fundamental Concept by masfuerte on Saturday July 11, 2026 @09:45AM (#48872016)
Cheers, I had missed the nuance.
[ Parent | on HN ]
Re:Computation as a Universal and Fundamental Concept by Twey on Monday July 13, 2026 @04:55AM (#48889718)
In constructive mathematics I think you'd be right: to call a problem decidable would require you to produce the algorithm that decides it, so you couldn't call the Collatz conjecture decidable (nor could you call it undecidable!). But the usual definition of decidability is classical.

This is slightly bizarre now I think about it: the definition of decidability allows the algorithm selection to be undecidable!

[ Parent | on HN ]