4 ms·

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

by cvoss 3y ago

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.

srcreigh 3y ago
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 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.
- cvoss 3y ago
  > 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.
  - srcreigh 3y ago
    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.
    - ogogmad 3y ago
      That's an irrelevant example because your f(n) does not have a self-contained mathematical definition.
    - woopsn 3y ago
      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.
      - srcreigh 3y ago
        > 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.
- deleted 3y ago
  [deleted]
- kakaz 3y ago
  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
  - srcreigh 3y ago
    Such as?
- practal 3y ago
  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.
  - srcreigh 3y ago
    there's been reduction to 745 in more recent work https://scottaaronson.blog/?p=7388 https://scottaaronson.blog/?p=7388
    - practal 3y ago
      Yes, you are right, just saw this yesterday, too.
drpixie 3y ago
> 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.
- a_cardboard_box 3y ago
  How do you know when the last n-state machine has finished, given that some will not halt?
- torinmr 3y ago
  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.
  - drpixie 3y ago
    You're right about the tape. Duh.
- srcreigh 3y ago
  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).

by cvoss 3y ago

srcreigh 3y ago

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 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.

cvoss 3y ago
> 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.
- srcreigh 3y ago
  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.
  - ogogmad 3y ago
    That's an irrelevant example because your f(n) does not have a self-contained mathematical definition.
  - woopsn 3y ago
    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.
    - srcreigh 3y ago
      > 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.
deleted 3y ago
[deleted]
kakaz 3y ago
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
- srcreigh 3y ago
  Such as?
practal 3y ago
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.
- srcreigh 3y ago
  there's been reduction to 745 in more recent work https://scottaaronson.blog/?p=7388 https://scottaaronson.blog/?p=7388
  - practal 3y ago
    Yes, you are right, just saw this yesterday, too.

drpixie 3y ago

> 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.

a_cardboard_box 3y ago
How do you know when the last n-state machine has finished, given that some will not halt?
torinmr 3y ago
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.
- drpixie 3y ago
  You're right about the tape. Duh.
srcreigh 3y ago
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).