Hacker News Reader

HNHacker News

Top New Best Ask Show Jobs

Comment by Someone | Hacker News Reader

Parent Full thread

Someone·

> Given a constanct C, you can construct a constant sequence f(n) = C.

> Since f(n) is trivially computable

That only is true if C is computable.

View on HN

Integers are what's relevant to BB, and all integers are computable.

So what if we set C = BB(10)?

The integer C is computable. However, we do not know what integer C is without first computing BB(10); and doing that might be not be possible.

But BB(10) is also just an integer. So it should be computable?

BB(10) is computable. That doesn’t mean anyone can actually figure out what it is. It doesn’t even mean it’s theoretically possible to do so. Computable just means that there exists a turing machine that will output the digits.

There is some notational subtletly here. Strictly speaking, BB(n) represents the output of the BB function for the input n. In that sense BB(n) is computable.

However, the BB function itself is not computable. It makes sense to ask "for what inputs is the BB function computable?". When people talk about BB(n) not being computable, they are really talking about the computability of the BB function at n, not the computability of the integer that happens to be BB(n).

It's hard or maybe impossible to figure out what BB(10) is. But abstractly, it is some finite integer. That finite integer is trivially computable: make a turing machine that hardcodes all the digits and outputs them one by one. You can't know that this machine actually produces BB(10) if you don't know what BB(10) is, but that's separate from the question of whether the number itself is computable.

Reply on news.ycombinator.com