Hacker News Reader

Comment by cvoss | Hacker News Reader

But BB is an uncomputable function. You've not escaped undecidability at all. You cannot write a program that will compute BB(n) given n as an input.

Also, the enormous size of BB(n) for any particular n is no argument for why it's so hard to determine what BB(n) is. It's actually the other way around. Undecidability sheds light on the enormous sizes of BB(n). Suppose you had a computable function which was known to be an upper bound for BB. Well, then you can play some tricks and leverage it to solve the halting problem by simulating machines for only so many steps before realizing whether you're looking at a halting one or a non-halting one. Therefore, no such upper bound function exists. Therefore, you can write down the fastest growing computable function you can think of, and BB will outpace it.

View on HN

Scott Aaronson addresses this. Uncomputable does not mean unsolvable by humans. It just means there’s no axiomatic system powerful enough to enumerate all the busy beaver numbers. Rather we’ll need axiomatic system A for the first few, then B, then C, etc each more complicated than the last.

Ex: we already know BB(745) is independent of ZFC, any more powerful system should have its own independence limit, etc.

source: page 6 here https://www.scottaaronson.com/papers/bb.pdf

Since BB computing code is halting problem solving code, it goes back to my point about “one finite program to solve halting for countably infinitely many TMs and inputs” seeming intractable compression-wise. On the contrary, maybe countably many BB computing programs for each countably many BB number would be doable.

> Uncomputable does not mean unsolvable by humans.

It absolutely means that, unless you don't believe the Church-Turing thesis and claim that humans have the ability to carry out computations that machines physically cannot.

I think you are misunderstanding the difference between having an algorithm to determine BB(n) for all n, and figuring out what BB(n) is for certain special n.

f(n) = name of top pop song in the year n defined for n>=1950

This doesn’t seem computable, yet we can definitely figure out its values.

Anyways, I believe my point above is in alignment with Scott Aaronson, so if you’ve read that I’m curious what you think the differences are.

Scott says in the paper:

    Even if we supposed that, for every n, there was some reasonable
    extension of ZF set theory that was powerful enough to settle the
    value of BB(n) — even so, there could be no systematic way to find
    those extensions.

It's essentially true that we (humans) cannot rely on varying our axioms indefinitely because we'd have to perform the incalculable search. I think what you're saying though is something like, the theory is already pretty interesting for low N, maybe we can eke it out.

It's definitely an interesting way to frame things. But imo the halting-problem insights still seem more naturally applicable to typical related issues in computer science and engineering. How do you prefer BB(n), when does it ever come up? Honestly curious. Appreciated the link.

> It's essentially true that we (humans) cannot rely on varying our axioms indefinitely because we'd have to perform the incalculable search. I think what you're saying though is something like, the theory is already pretty interesting for low N, maybe we can eke it out.

No, the idea of incalculable simply means that it can’t be enumerated using one program. As humans we can write different programs and it’s fine.

Imagine code which exhaustively checks all math proofs. That code will have an axiomatic system built into it such as ZFC. This says that that code still can’t calculate busy beaver numbers at a point, because at a certain point ZFC is no longer enough. But if we had similar code with some ordinal stuff thrown in, maybe we could get a little farther. Etc.

Practically, undecidability and busy beaver numbers are both very, very untenable. I always had a philosophical objection to undecidability, it felt wrong that knowledge was limited in theory because of “this sentence is false” logical tricks. Practically, who cares if we can’t prove “this sentence is false”. (Turings undecidability argument is a halt program encoding of this sentence is false.)

I wanted a different more satisfying answer, and busy beaver numbers are that answer: math is unfathomably complicated, and we don’t have powerful enough axiomatic systems to understand even small computer programs yet.

> No, the idea of incalculable simply means that it can’t be enumerated using one program. As humans we can write different programs and it’s fine.

I'm getting frustrated reading your comments. LLMs show that human beings are likely to themselves admit simulations by computer programs. So computability limits apply to human beings as much as to computers. I've never seen anyone misunderstand these topics in quite the way you have.

> I wanted a different more satisfying answer, and busy beaver numbers are that answer

Listen, you're wrong. This entire thread you've started is wrong. The Busy Beaver function is uncomputable precisely because the Halting problem is unsolvable -- that's how you prove it. It provides no additional insight into "undecidability" except for a bunch of misunderstandings you have that other people have been trying to point out to you.

You might appreciate the additional lens of Chaitin's constant omega then. The probability that a particular universal machine will halt when fed a random program is uncomputable but also algorithmically random -- meaning the (finite) binary expansions of omega always form a maximally complex sequence, in the Kolmogorov sense. Why? We can't calculate omega... I mean, that figures. But on top of that the mysterious number, which could be 1/2 or 1/e for all we might expect at first, is instead just a completely uncorrelated sequence of bits.

At a certain point it just becomes a mess. No process can keep up. In general most logical systems (all of them become relevant as n grows) are completely random, with no characteristic structure.

Yeah I have read that too. You may be mixing up with chaitins incompleteness though partly. As far as I can tell it has the same quality as busy beaver numbers: for a given axiomatic system there is a limit. Therefore no system can compute the entire series (aka digits in omega)… yet again what people don’t ever seem to recognize (and I don’t know why not) is that with more powerful formal systems we could in theory calculate arbitrarily many digits of omega.

That's an irrelevant example because your f(n) does not have a self-contained mathematical definition.

Nice paper! The number is BB(748), by the way.

Thinking in terms of concrete machines is great. The work on Abstraction Logic has made me a Platonist in a Goedel way as well. I insist that the mathematical universe is real: there are mathematical objects, and they have their own independent, real existence. If you admit that 1 and 2 and 3 are real, then it is difficult to argue that Turing Machines are not real, and of course the models of consistent theories are real as well.

In fact, I would go as far as saying, if you are not a Platonist, then good luck making any kind of argument for correct reasoning.

there's been reduction to 745 in more recent work https://scottaaronson.blog/?p=7388

Yes, you are right, just saw this yesterday, too.

Please note that mostly all of such considerations are related to FOL models. While it may be acurate because we value FOL, such statements does not have general or absolute meaning

Such as?

> But BB is an uncomputable function. You've not escaped undecidability at all. You cannot write a program that will compute BB(n) given n as an input.

I think you're going down the wrong path re "uncomputable". BB(n) is easily computable, just write a little program that enumerates (generates) and runs all n-state BB machines. BB(n) is the largest lifetime of any those n-state machines. BB(n) is known and easily computable for small n.

The problem is that the number of machines increases very quickly with n, and the time taken to evaluate each machine often increases quickly with n. So for even moderate n, it is completely impractical to brute-force compute BB(n). But impractical is not uncomputable.

Just because you don't wait to wait past the heat-death of the universe, doesn't mean that you wouldn't have got an answer eventually. And eventually = computable.

BB(n) isn't computable, even given unlimited computational resources.

Running all n-state machines won't work, because you may have some machines that continue indefinitely, but without repeating. (Remember that while the number of states is finite, the tape is infinite.) No matter how long you run them for, you can't be sure whether they are going to terminate at some point in the future, or if they'll continue forever without halting.

This is why computing BB(n) for arbitrary n is equivalent to solving the halting problem.

You're right about the tape. Duh.

This is false. You’d never get the answer with that strategy, since some of the machines will never halt, but you wouldn’t know if the ones you have left are going to halt or not.

Te winning strategy is to A) prove all the machines that don’t halt and B) find the largest runtime of machines that do halt.

That’s why BB(745) is important because we can’t use ZFC to prove A for BB(745), even if we could run all the halting machines to find BB(745).

How do you know when the last n-state machine has finished, given that some will not halt?

Reply on news.ycombinator.com