10 ms·

I prefer busy beaver numbers to undecidability. The halting problem has a flaw in that it asks for finite code to predict halting for any arbitrary program, whi

I prefer busy beaver numbers to undecidability. The halting problem has a flaw in that it asks for finite code to predict halting for any arbitrary program, which to me seems intractable despite the logical paradoxes involved. Busy beaver numbers step around this by looking at TMs of one size at a time. Now, the busy beaver numbers are enormous and we will likely never solve even BB(6). But that’s not for reasons of logical paradoxes like “this sentence is false” or “the smallest positive integer not definable in under sixty letters”. The reasons we can’t solve small busy beaver numbers: - There’s an enourmous number of 6-state TMs let alone 100 state TMs. - BB(6) has been proven to be at least 10^10^10^…^10 (15 times total). So what could BB(20) be. - some small busy beaver numbers are conjectured to be independent of ZFC, meaning we’d need new math foundations. Conjectured to be BB(20), proven at least as high as BB(745) is independent of ZFC. - various unsolved math problems are equivalent to TMs of particular sizes: Goldbach’s conjecture, Riemann hypothesis, etc At least with busy beaver numbers there isn’t some stupid paradox, we just can’t practically solve them.

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.
- 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).
kevinventullo 3y ago
I also prefer BB’s, I think because the rapid increase in scale gives me an almost supernatural or divine feeling. As you said, “smallish” BB’s already transcend ZFC, which is something like humanity’s best attempt at “universal” logical foundations. So, when thinking about BB’s, I can’t help but feel that I’m running up against the limits of what is even possible for humans to comprehend.
tshaddox 3y ago
If you're trying to teach or learn about undecidability, I've always thought of busy beaver problems as unnecessary added complexity over the halting problem. I can't think of a good way to explain the undecidability of busy beaver without invoking the halting problem. It's not because there is an enormous number of 6-state TMs or because BB(6) is at least 10^10^10^…^10. It's simply because you can't decide, for each TM with n states, whether that TM will halt. Busy beaver problems are interesting in their own right, particularly for 1) demonstrating the huge amount of complexity that can arise from very simple rules and 2) for the epiphany that a busy beaver function grows asymptotically faster than any computable. But I don't find them to be great as an introduction to undecidability.
- srcreigh 3y ago
  That’s the thing, I don’t think busy beaver numbers are undecidable. Every TM with n states will or won’t halt, and there isn’t any reason to think we can’t prove whether it halts or not. Every proof for undecidability use hypothetical TM constructions with a logical property and a trick. Busy beaver numbers are concrete.
  - ogogmad 3y ago
    Oh dear God. The BB function is uncomputable precisely because of the halting problem, which you think is a "logical trick".
  - eigenket 3y ago
    If you can solve the halting problem there is an algorithm to easily solve the busy-beaver problem and vice-versa. They are exactly equivalent.
    - srcreigh 3y ago
      Yes but no. Algorithm for BB numbers and halting problem can implement each other, but both provably don’t exist in the first place, so that’s a bit like proving 2 is odd implies 3 is even and vice versa. Anyway, the point is that the halting procedure in its full generality cannot exist, while each individual busy beaver number can be solved in theory (even if there’s no algorithm that can list them all). In other words, busy beaver numbers admit countably many theoretically tractable sub problems. It’s in a way the most natural way to break the halting problem down into tractable pieces.
twiceaday 3y ago
> I prefer busy beaver numbers to undecidability. Can you clarify what you mean by this? You prefer one to the other in what circumstances? > Now, the busy beaver numbers are enormous and we will likely never solve even BB(6). But that’s not for reasons of logical paradoxes like “this sentence is false” or “the smallest positive integer not definable in under sixty letters”. Also please clarify this. BB is hard to compute because it is essentially defined in terms of solving the halting problem (that's known to be pretty hard). You alluded to a proof of that fact. What is your point? And what is your problem with those kinds of proofs? What do BBs have to do with undecidability besides being directly defined in terms of an undecidable operation?
- srcreigh 3y ago
  There’s no known reason why we can’t compute any specific busy beaver number. We just can’t write code to list them indefinitely. No known reason why we can’t solve the first 100k, for example. Whereas the halting problem is known to be unsolvable. I just prefer things that are solvable in theory to things that aren’t.
  - twiceaday 3y ago
    I am reading your original comment as "I prefer the color green to the number seven" coupled with an implication that it is common to compare green to seven, and that there are obvious situations where green can be used instead of seven. I don't see why anybody would compare green to seven, enough to state it and the conversation to gain traction. Your explanation here is akin to 'I like green because green can be seen but you can never truly see seven.' Okay, these words make sense in that order, but they don't explain the above implications. Are you simply saying that you prefer the aesthetic of one of these two vaguely related things? It sounds like you are implying that there is some way to do all the work with undecidability but using BB instead. Show your work. There is no known reason why we can't tell if any specific program halts. We just can't write code to tell if an arbitrary program halts. This result is exactly what you are using when talking about preferring BB(k) for some fixed k, each k requires solving a bunch of halting problems. The paradox proofs you seem to dislike are only needed for the general case, the general halting problem or, and this is to me the confusing part, the general BB(n). So you are comparing BB(k) for some fixed k to something infinitely more general in the general halting problem. So, again, why would you compare these two things? When is that a useful thing to do?
ogogmad 3y ago
> At least with busy beaver numbers there isn’t some stupid paradox, we just can’t practically solve them. No! In computability theory we work with Turing Machines that have unlimited memory. Since they have unlimited memory, the sizes of individual busy beaver numbers are not the problem. Individual busy beaver numbers are in fact all computable because every integer is computable. What is uncomputable is the busy beaver function. The busy beaver function is uncomputable because of the halting problem -- I suggest finding or reading a proof. Therefore the BB function provides zero additional insight into undecidability. I'm also amazed that there are people on this technology website - like you - who see all of this progress happening in AI with programs that are close to human intelligence, and still think that human beings can do things like determine arbitrarily large busy beaver numbers. We have concrete evidence that human beings are themselves limited by computability. People cannot just write arbitrarily good programs (to determine the first n busy beaver number, let's say) because people are programs.
eigenket 3y ago
Other people have mentioned this already, but halting for Turing machines is essentially exactly the same for undecidability as busy beaver numbers. Here is a quick sketch of a proof: Assume we have a machine (or algorithm) which we input a description of a Turing machine and it tells us whether or not it halts. Then to find the nth busy beaver you 1. Enumerate all n state Turing machines 2. In a "for loop" ask your machine whether each n-state Turing machine halts 3. For the ones that halt, run each of them until they halt and write down how many steps it took 4. The largest of these numbers is the busy beaver number BB(n) Similarly lets say you have a machine (or algorithm) which tells you BB(n), you can solve the Halting problem like this 1. Run the Turing machine until it has completed BB(n) steps 2. Remember that if an n-state Turing machine hasn't halted in BB(n) steps then it will never halt 3. If it hasn't halted after BB(n) steps then it won't ever halt so you've solved the halting problem Busy beaver and Halting are (from the point of view of decidability) exactly the same thing.
- deleted 3y ago
  [deleted]

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

kevinventullo 3y ago

I also prefer BB’s, I think because the rapid increase in scale gives me an almost supernatural or divine feeling. As you said, “smallish” BB’s already transcend ZFC, which is something like humanity’s best attempt at “universal” logical foundations. So, when thinking about BB’s, I can’t help but feel that I’m running up against the limits of what is even possible for humans to comprehend.

tshaddox 3y ago

If you're trying to teach or learn about undecidability, I've always thought of busy beaver problems as unnecessary added complexity over the halting problem. I can't think of a good way to explain the undecidability of busy beaver without invoking the halting problem. It's not because there is an enormous number of 6-state TMs or because BB(6) is at least 10^10^10^…^10. It's simply because you can't decide, for each TM with n states, whether that TM will halt. Busy beaver problems are interesting in their own right, particularly for 1) demonstrating the huge amount of complexity that can arise from very simple rules and 2) for the epiphany that a busy beaver function grows asymptotically faster than any computable. But I don't find them to be great as an introduction to undecidability.

srcreigh 3y ago
That’s the thing, I don’t think busy beaver numbers are undecidable. Every TM with n states will or won’t halt, and there isn’t any reason to think we can’t prove whether it halts or not. Every proof for undecidability use hypothetical TM constructions with a logical property and a trick. Busy beaver numbers are concrete.
- ogogmad 3y ago
  Oh dear God. The BB function is uncomputable precisely because of the halting problem, which you think is a "logical trick".
- eigenket 3y ago
  If you can solve the halting problem there is an algorithm to easily solve the busy-beaver problem and vice-versa. They are exactly equivalent.
  - srcreigh 3y ago
    Yes but no. Algorithm for BB numbers and halting problem can implement each other, but both provably don’t exist in the first place, so that’s a bit like proving 2 is odd implies 3 is even and vice versa. Anyway, the point is that the halting procedure in its full generality cannot exist, while each individual busy beaver number can be solved in theory (even if there’s no algorithm that can list them all). In other words, busy beaver numbers admit countably many theoretically tractable sub problems. It’s in a way the most natural way to break the halting problem down into tractable pieces.

twiceaday 3y ago

> I prefer busy beaver numbers to undecidability. Can you clarify what you mean by this? You prefer one to the other in what circumstances? > Now, the busy beaver numbers are enormous and we will likely never solve even BB(6). But that’s not for reasons of logical paradoxes like “this sentence is false” or “the smallest positive integer not definable in under sixty letters”. Also please clarify this. BB is hard to compute because it is essentially defined in terms of solving the halting problem (that's known to be pretty hard). You alluded to a proof of that fact. What is your point? And what is your problem with those kinds of proofs? What do BBs have to do with undecidability besides being directly defined in terms of an undecidable operation?

srcreigh 3y ago
There’s no known reason why we can’t compute any specific busy beaver number. We just can’t write code to list them indefinitely. No known reason why we can’t solve the first 100k, for example. Whereas the halting problem is known to be unsolvable. I just prefer things that are solvable in theory to things that aren’t.
- twiceaday 3y ago
  I am reading your original comment as "I prefer the color green to the number seven" coupled with an implication that it is common to compare green to seven, and that there are obvious situations where green can be used instead of seven. I don't see why anybody would compare green to seven, enough to state it and the conversation to gain traction. Your explanation here is akin to 'I like green because green can be seen but you can never truly see seven.' Okay, these words make sense in that order, but they don't explain the above implications. Are you simply saying that you prefer the aesthetic of one of these two vaguely related things? It sounds like you are implying that there is some way to do all the work with undecidability but using BB instead. Show your work. There is no known reason why we can't tell if any specific program halts. We just can't write code to tell if an arbitrary program halts. This result is exactly what you are using when talking about preferring BB(k) for some fixed k, each k requires solving a bunch of halting problems. The paradox proofs you seem to dislike are only needed for the general case, the general halting problem or, and this is to me the confusing part, the general BB(n). So you are comparing BB(k) for some fixed k to something infinitely more general in the general halting problem. So, again, why would you compare these two things? When is that a useful thing to do?

ogogmad 3y ago

> At least with busy beaver numbers there isn’t some stupid paradox, we just can’t practically solve them. No! In computability theory we work with Turing Machines that have unlimited memory. Since they have unlimited memory, the sizes of individual busy beaver numbers are not the problem. Individual busy beaver numbers are in fact all computable because every integer is computable. What is uncomputable is the busy beaver function. The busy beaver function is uncomputable because of the halting problem -- I suggest finding or reading a proof. Therefore the BB function provides zero additional insight into undecidability. I'm also amazed that there are people on this technology website - like you - who see all of this progress happening in AI with programs that are close to human intelligence, and still think that human beings can do things like determine arbitrarily large busy beaver numbers. We have concrete evidence that human beings are themselves limited by computability. People cannot just write arbitrarily good programs (to determine the first n busy beaver number, let's say) because people are programs.

eigenket 3y ago

Other people have mentioned this already, but halting for Turing machines is essentially exactly the same for undecidability as busy beaver numbers. Here is a quick sketch of a proof: Assume we have a machine (or algorithm) which we input a description of a Turing machine and it tells us whether or not it halts. Then to find the nth busy beaver you 1. Enumerate all n state Turing machines 2. In a "for loop" ask your machine whether each n-state Turing machine halts 3. For the ones that halt, run each of them until they halt and write down how many steps it took 4. The largest of these numbers is the busy beaver number BB(n) Similarly lets say you have a machine (or algorithm) which tells you BB(n), you can solve the Halting problem like this 1. Run the Turing machine until it has completed BB(n) steps 2. Remember that if an n-state Turing machine hasn't halted in BB(n) steps then it will never halt 3. If it hasn't halted after BB(n) steps then it won't ever halt so you've solved the halting problem Busy beaver and Halting are (from the point of view of decidability) exactly the same thing.

deleted 3y ago
[deleted]