[Aeium]

Isn't saying BB(6) is computable the same as assuming that it is an integer?

I thought this was not necessarily true.

For example, one beaver might halt after some integer number of steps. This would be the potentially very large integer the author is referring to. Another might go into an infinite loop, and clearly never halt.

My understanding of the where incomputability entered the discussion is the third possibility, that a beaver might have complex behavior that neither ever halts or ever loops.

The author touches on answering this, drawing the distinction that a specific answer might not be provable. But I'm not sure I understand.

How would the answer for a specific integer be computable if it's impossible to determine what the value for the function of is for that integer?

[umanwizard]

No, the definition of the busy beaver problem excludes any program that never halts, regardless of how complex its behavior is.

> How would the answer for a specific integer be computable if it's impossible to determine what the value for the function of is for that integer?

Can you say precisely what you mean by “computable”? I suspect you’re using an intuitive definition that’s different from the author’s formal definition.

[Aeium]

So, one thing that we know from Godel is that there are true statements that cannot be proven.

What if a similar proof is made for a Beaver? That a specific beaver is constructed such that

1: It probably never halts 2: Proving that it never halts is a paradox

Something like that. If assignment of BB number for BB of that size depends on that proof, then the BB value doesn't exist.

And what else would it depend on? How could a smaller number be selected when larger potential numbers cannot be ruled out?

[umanwizard]

> What if a similar proof is made for a Beaver?

Then we will never be able to find the Nth beaver number for the corresponding N.

That doesn’t mean it is undefined or uncomputable. It actually has nothing to do with it. There is a computer program that prints out the number of hairs on my head. Doesn’t matter that you will never know how to write that program.

Again, uncomputable is being used in a technical sense here which is why I asked you what definition of “computable” you’re using.

[Aeium]

> Then we will never be able to find the Nth beaver number for the corresponding N.

This is pretty clearly what people are asking about when asking if BB(6) is "uncomputable" then.

I understand (now) the point about the specific meaning of the term of art "uncomputable". If you want to speak precisely on the topic, it's not the right question to ask.

But it still seems like the question, "will we ever be able to find out the Nth beaver number", is the more interesting question.

So, we can define ZFC axioms that classify the beavers we can know together with the beavers we cannot know. So what? Then that is just skipping the interesting question. Maybe that just means for this specific problem that is not the best construction to decide to use to classify them?

I would be more interested in a classification that would assign one label to beavers we could possibly hope to calculate, and another for beavers where the calculation is impossible.

[elijaht]

“Probably doesn’t halt” is ill defined, it either halts or it doesn’t. In either case, computability of that number is completely separate from whether we can prove that number is BB(N) or decide whether a given beaver halts. Additionally, the way the busy beaver function is defined ensures it has a defined integer output. Computability is just our ability to construct a machine which would print out that number. We can clearly do that for any integer

[jcranmer]

To be frank, this is an issue where there's an abuse of terminology going on, although the people asking the question probably don't realize there's an abuse of terminology.

"Is X computable?" is asking if there is a program that is capable of printing X out. For any integer, the answer to this question is trivially yes.

But when people are asking "Is BB(6) computable?", that's not really what they're intending to ask. What they're trying to ask is "is it possible for us to figure out what the value of BB(6) is?" In a more precise sense, the question is "Can we prove {BB(6) = x} is a true statement for some value of x?"

To some degree, I think Scott is being somewhat specious here. The question may be somewhat malformed as written, but it's also pretty clear to an expert what the question meant to ask, and--especially when you're targeting a more lay audience--insisting on giving the trivial answer to the clearly unintended question isn't likely to help the situation much.

[immibis]

Every Turing machine execution either halts, or does not halt. There are no intermediate possibilities. Some non-halting is easier to prove than others, but it's all still non-halting.

[Aeium]

Yes, this is clearly true. Pardon the hasty first reading and deleted comment please.

It doesn't address what I am claiming though.

The busy beaver is not defined entirely by halting vs not-halting.

Looping beavers are excluded as well.

The middle ground I am claiming is that there is a middle ground between non-halting and provably non-halting.

I'm claiming there could be a non-halting Beaver that is impossible to prove, which would mean there is no answer for the BB function.

[rdlw]

> The busy beaver is not defined entirely by halting vs not-halting.

> Looping beavers are excluded as well.

Looping beavers do not halt.

> there is a middle ground between non-halting and provably non-halting

Yes, there are turing machines that encode mathematical theorems which are independent of ZFC, meaning they cannot be proven to halt or not to halt. The state-of-the-art is BB(748), which is known to be independent [0].

There are also much smaller known turing machines which encode classically difficult math problems, like the Goldbach conjecture [1]. This means that the value of BB(27) cannot be proven until the Goldbach conjecture is proven or disproven, as until that is done, we will always have something like "BB(27) is N unless the Goldbach conjecture is false".

However, our inability to prove these things does not change the fact that they have specific values. To stick with the BB(27) example, say that it seems we've narrowed it down to some huge number A, or a number dependent on the first number for which Goldbach does not hold. Call that second number B. We may be unable to find the value of B (doing so would disprove Goldbach), but it is still a specific number. There still exists a concrete value for BB(27)--it's A if Goldbach is true, and it's B is Goldbach is false.

[0] https://www.ingo-blechschmidt.eu/assets/bachelor-thesis-unde...

[1] https://gist.github.com/anonymous/a64213f391339236c2fe31f874... This 27-state machine halts when it finds a counterexample to the Goldbach conjecture.

[immibis]

Busy beavers are the machines in some size class which run the longest, then halt. They may be alternatively defined as the ones which produce the most output, then halt. Machines which obviously loop are excluded, and so are machines that non-obviously loop - for example ones that loop until they prove the Riemann hypothesis are excluded if the Riemann hypothesis is false and the proof system is consistent.

[elijaht]

For the purpose of the busy beaver problem, your second and third cases are equivalent- it’s a beaver that does not halt. Therefore neither of them are BB(6). BB(6) is tautologically an integer