Hacker News Reader

Comment by skybrian | Hacker News Reader

That doesn’t sound right to me. What about the machines that don’t halt? You can’t compute whether or not to skip them directly.

> A busy beaver hunter who goes by Racheline has shown that the question of whether Antihydra halts is closely related to a famous unsolved problem in mathematics called the Collatz conjecture. Since then, the team has discovered many other six-rule machines with similar characteristics. Slaying the Antihydra and its brethren will require conceptual breakthroughs in pure mathematics.

https://www.quantamagazine.org/busy-beaver-hunters-reach-num...

View on HN

What specifically doesn't sound right?

The claim is that every bb(n) is computable but I don’t think you can compute bb(6) without knowing which machines won’t halt. That doesn’t seem like a finite calculation?

But given the answer, I suppose you could write a program that just returns it. This seems to hinge on the definition of “computable.” It’s an integer, so that fits the definition of a computable number.

My mistake.

Yes. A valid question for a specific n would be whether you can prove the value of BB(n). If you don't care about provability, you can indeed just produce a number that happens to be the right one.

So as you noticed, it only makes sense to talk about whether a function is computable, we can't meaningfully talk of computable numbers.

Yes exactly, imagine a function HH(n) that returns 0 if the Turing machine represented by the integer n halts, and 1 if it doesn't.

Then HH the function itself is not computable, but the numbers 0 and 1, which are the only two outputs of HH are computable.

Integers themselves are always computable, even if they are the output of functions that are themselves uncomputable.

The main thing to make it clear is that BB(n) for a specific n isn't a function - it's a number. Just like Mult(10,4) isn't a function, it's a number (40).

So a specific BB(n) is just a number and is computable.

Reply on news.ycombinator.com