The Boundary of Computation: Busy Beaver [video] | Hacker News Reader

The Boundary of Computation: Busy Beaver [video]

youtube.com

18 pointsmiohtama13 comments

Scott Aaronson's article "Who Can Name the Bigger Number?" is an excellent introduction as well and has been discussed many times on HN.

https://www.scottaaronson.com/writings/bignumbers.html

On the topic of "biggest number", there's an excellent Numberphile[1] on Rayo's Number (which does mention Busy Beavers on the way.)

[1] https://www.youtube.com/watch?v=X3l0fPHZja8

A functional (lambda calculus based) equivalent [1] of the traditional Busy Beaver function is more fine-grained as a function of number of bits rather than number of states, and appears to grow faster bit-for-bit as argued in [2].

[1] https://oeis.org/A333479

[2] https://googology.fandom.com/wiki/User_blog:JohnTromp/The_la...

Is there a smallest uncomputable number? Or maybe that's not a well-formed question? Simplest uncomputable number? Simplest algorithm which produces uncomputable numbers? Confused now.

I don’t think so, because you could divide any uncomputable number by an arbitrary computable constant and it would still be uncomputable. I think!

Yeah, I updated the comment based on that. I guess you'd have to formulate it very specifically to get an interesting answer.

I think this is the wrong question. Any number, if you define them as a representation of digits, is computable in that sense. What isn't necessary computable is the value of a function taken with a certain input or input range. BB numbers, as large as they can be, are themselves finite and therefore "computable" once you know them, but the mapping from natural numbers to BB numbers is not computable. So the real value of a particular function f evaluated at some number say 100 could be as small as 0, but maybe you just can't compute f(100) and know that it's 0.

> Any number, if you define them as a representation of digits, is computable in that sense.

You have to be a bit careful, here. What you're saying is true of integers (such as the values taken by the BB function), as well as rationals. But it's not true of real numbers, because the reals are uncountable, and therefore there are infinitely many real numbers that cannot be finitely "described" or written down (in whatever notation you happen to care about).

An example of an uncomputable real number: https://en.wikipedia.org/wiki/Chaitin%27s_constant

"Computability" is defined in terms of series and algorithms — it there's an algorithm to generate a series of numbers, the series is (by definition) computable.

The Busy Beaver series of numbers stand out because there's no possible algorithm to generate them, per the halting problem. Also due to the halting problem, they grow faster than any possible computable series. In other words, for any series S(n), at some point you're going to hit a k such that for all numbers m greater than or equal to k, BB(m) > S(m).

So in that sense a "smallest incomputable number" is not well-defined. However it is reasonable to call them the simplest possible description (not algorithm, just a description) of an incomputable series of numbers.

There are more complex descriptions of incomputable numbers, such as the Busy Beaver number defined with respect to a Turing machine that has a busy beaver oracle attached to it.

To get one's head around the concept of an uncomputable number, you must come at it from the realm of uncomputable functions. I sometimes think of big-O computational complexity as a (finite) analogy for uncomputability.

For example, the naive matrix multiplication algorithm for n-by-n matrices is O(n^3). That means there is a cubic function relating the size of the input (in terms of n) to the number of steps required to produce the output. But it's not meaningful to ask "what is the computation complexity of multiplying 100-by-100 matrices?"---the answer to this question is O(1), constant time. I.e., it takes ~1000000 steps, every time! In other words, n^3 is a cubic function, but 100^3 is not a cubic function in any meaningful sense; the function n^3 has a polynomial degree, not the output of the function on a particular input.

In the same way, it's not meaningful to ask about the computability of specific known numbers: if you know the number, then you have computed it. Instead, you must ask about numbers which are, themselves, functions. (Not a number that is the output of a function on some input, mind you. I mean a number that is encoded by the entirety of the function, across all possible inputs.)

Someone has elsewhere mentioned Chaitin's constant as an example of an uncomputable number. What is meant in this case by "uncomputable number" is that we can only describe the number indirectly, rather than put our hands on it directly: The (say) decimal expansion of the digits (aka a machine that spews them out in order from left to right) as encoded by a function mapping the natural numbers to digits, is an uncomputable function. It was also mentioned elsewhere that the possibility of a number being uncomputable in this sense is special to the real numbers, as opposed to, say, the integers. However, I disagree. An integer can indeed be uncomputable in the same sense. If you have honestly no idea how big the integer in question is, to represent it you need a machine that emits its digits right to left (rather than left to right for decimals as we were imagining above), which is again a function mapping the naturals to digits. Such a function may be uncomputable, which would mean you have no way of determining if and/or when it will begin spitting out only zeros after a certain point (which would provide an upper bound for your integer).

If any of this is interesting, you may enjoy the Berry paradox. [0]

[0] https://en.wikipedia.org/wiki/Berry_paradox

Turing machines, with their infinitely long tape, break human imagination.

Surely there is some Turing machine that only halts if the Collatz conjecture is false. That could be thrown into this incredibly uncomputable mix.

The Collatz conjecture is undecidable, so no Turing machine like you describe exists.

The Collatz conjecture isn't a decision problem. The natural corresponding decision problem (given an x, does the conjecture hold when starting at all positive integers k less than x) is decidable in constant time.

We don't know what specifically the deciding machine is, but it is either the one that always returns Yes or the one that returns whether or not x is below some finite value. Either case can be solved by only reading a bounded number of bits from the input.

With some work, one can eventually generalize Collatz to make an undecidable problem; this is more or less the basis for FRACTRAN. https://en.wikipedia.org/wiki/FRACTRAN

Reply on news.ycombinator.com