Hacker News Reader

Comment by Kranar | Hacker News Reader

A computable real number is a real number for which a Turing Machine exists that can compute it to any arbitrary precision.

So yes sqrt(2) is computable.

Every BB(n) is computable since every every natutal number can be computed. It's the BB function itself that is not computable in general, not the specific output of that function for a given input.

View on HN

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

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.

Interesting point about BB(n)... Is it known that BB(n) is finite for every n?

I believe it is by definition? The machines that don’t halt are filtered out. The trouble is how to do the filtering.

Yes BB(n) is always a natural number which is by definition finite.

Reply on news.ycombinator.com