Hacker News Reader

Comment by Filligree | Hacker News Reader

So… what if BB(748) is uncomputable? Or rather, didn’t you just prove that it is?

I suppose I did!

I was having a hard time reconciling this with the intuition that BB(n) is in principle "computable" (colloquially speaking) for any n - my thinking went that if I want to compute BB(n), I can enumerate turing machines and run them until they halt, since infinitely looping machines are excluded from BB(n). But of course I have now reduced this to the halting problem! How do you know when you're "done" for that n? You don't.

Thanks to you and sibling commenters.

Similarly, if you know BB(n), you can use it to solve the halting problem for Turing machines up to that size.

Isn't the easier proof that BB(n) isn't computable something like

- assume BB is computable

- there exist a TM called X that computes the function

- it has K states

- X(K+1) produces BB(K+1) but from the definition of BB our machine cannot produce a result higher than BB(K).

There's a difference between a TM/algorithm/etc. that computes a function, like BB(n) (for all Natural numbers n); versus computing a particular value, like BB(748).

For comparison, there is no TM which computes the halting function halts(p) (for all programs p); but it's easy to compute particular values like halts("exit") or halts("while(true){}")

Yes. My reasoning applies to a function n=> BB(n)

Isn't that what "the function is not computable" is about?

Or is the thesis that the value of BB(748) can't be computed?

BB(n) for any particular n is always computable, no exceptions. There simply is no single computable function that can compute BB(n) for every n, but for any particular n there absolutely is a TM that computes it.

Indeed, the value of BB(n) for each n is just a number; and it's easy to construct a TM which outputs some particular number. However, we don't know what those TMs are, for the same reason we don't know what those BB(n) numbers are.

The same applies to more limited settings too, e.g. boolean questions like whether the Collatz conjecture holds: I know that one of the following programs calculates the right answer, but I don't know which:

- PRINT "true"; HALT

- PRINT "false"; HALT

(Perhaps we should also allow `PRINT "independent of the given axioms"; HALT` as well!)

Reply on news.ycombinator.com