I think there is a fundamental gap between the OP's concept of "Point" versus the responders. They're essentially asking if decidability has practical[1] uses to which the answer is generally "No". When a general CS practitioner imagines doing something via computation, they are already thinking of things in the realm of the possible. It may be helpful to know that exact answers are intractable and you'll have to settle for an approximation, but that information seems to correlate more with complexity than with decidability.
[1]: Where practical is in the sense of an engineer (or in their terms, a CS practitioner), not a theoretician. Most of the responders seem to interpret practical in the sense of a mathematician.
> they are already thinking of things in the realm of the possible.
very astute observation. Now I'm left wondering how this comes to be?
what is it about the way in which a general CS practitioner's approach to problem solving that grounds the potential ideas (of how to solve problem) into the computationally decidable?
They're essentially asking if decidability has practical[1] uses to which the answer is generally "No".
I don’t think I agree! For example, I strongly suspect that Malware detection researchers would be following many fruitless paths in the vein of “Let’s just figure out what the program is doing” if not guided by the fact that this is strictly harder than “Let’s just figure out if the program halts.”
Decidability has very practical applications. There have been a number of security exploits that have depended on the attacker being able to run a weird machine inside a decoder of some kind, like NSO's iPhone hack:
"JBIG2 doesn't have scripting capabilities, but when combined with a vulnerability, it does have the ability to emulate circuits of arbitrary logic gates operating on arbitrary memory. So why not just use that to build your own computer architecture and script that!? That's exactly what this exploit does. Using over 70,000 segment commands defining logical bit operations, they define a small computer architecture with features such as registers and a full 64-bit adder and comparator which they use to search memory and perform arithmetic operations. It's not as fast as Javascript, but it's fundamentally computationally equivalent.
The bootstrapping operations for the sandbox escape exploit are written to run on this logic circuit and the whole thing runs in this weird, emulated environment created out of a single decompression pass through a JBIG2 stream. It's pretty incredible, and at the same time, pretty terrifying."
Startup founder to VC: We're going to build an AI that can do X!
1 billion dollars later: We discovered we can't do X because there's this thing called "undecidability."
Undecidability puts fundamental limits on what we can do with computers. You can't even do simple things like write a program which can { determine if two programs are equal, determine if two programs would have equal outputs given any input, if any program will return a "1", if any program would halt, ... }
This feels kinda important considering what people might try to build using AI.
For practical purposes it doesn't really matter because most real world computation is an approximation anyway. AI researchers don't care much about impossibility results because their goal is human level artificial intelligence and they consider people to be existence proofs that such computation is possible to engineer artificially. Basically, AI researchers believe that people are just walking computers/robots so they're not at all concerned about theoretical obstructions to constructing generally intelligent software systems.
Something else to consider is that if it is possible to truly engineer human level intelligence for operating autonomous machines then ethical concerns would require treating such systems with full human rights. Some are already claiming the ethical thresholds for human rights for AI have already been passed in internal research projects at Google.[1]
You can certainly write a program which can determine if a program would halt. It just won't be able to output a yes or no for _every_ program. In some cases it would have to output 'undecidable'. Most of the practical programs you might want to feed into this program will have an answer.
If I may nitpick, it shouldn't ever output "undecidable" but rather something like "undecided" or "I give up". A program that can be trivially seen to halt if we let it run for a quadrillion years is only "undecidable" in the sense that we might get impatient and die.
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.
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.
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.
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.
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.
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.
> 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.
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
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.
> 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.
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).
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.
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.
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.
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.
> 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).
I don't understand this point at all. Busy beaver lets you solve halting and vice-versa. If there are some special cases in which you can solve busy beaver then you can use them to solve halting.
Each individual busy beaver number can't be solved in theory for the same reason that the halting problem can't - if you try to check all n-state Turing machines to compute BB(n) some of them won't halt, and some of those you won't be able to prove that they don't halt.
> Each individual busy beaver number can't be solved in theory for the same reason that the halting problem can't - if you try to check all n-state Turing machines to compute BB(n) some of them won't halt, and some of those you won't be able to prove that they don't halt.
Source? AFAIK we aren’t aware of any TMs which are impossible to prove loops forever. Turing’s proof only applies to finite halting code that works for arbitrary TMs and inputs. There will never be a solution for every busy beaver number for that reason. However I suspect for ex the program to compute BB(6) to be much larger than 6 states, (even just to print the number) so turings diagonalozation argument doesn’t fit.
> Source? AFAIK we aren’t aware of any TMs which are impossible to prove loops forever
There are explicitly known Turing machines which it is impossible to prove their whether or not they halt within ZFC. You could argue that you can construct a stronger logical system within which it is possible to prove one of these machines halts, the problem is that you can never be sure your stronger system is consistent. If you manage to come up with a proof within some stronger system that the machine halts, it may also be possible to come up with a proof that it does not halt (if the system is inconsistent).
Thanks, fun discussion. I think we understand each other.
I’m not so worried about consistency. Even ZFC has the issue you describe. I found this paragraph from Wikipedia about Gödels 2nd incompleteness theorem very interesting.
> The corollary also indicates the epistemological relevance of the second incompleteness theorem. It would actually provide no interesting information if a system F proved its consistency. This is because inconsistent theories prove everything, including their consistency. Thus a consistency proof of F in F would give us no clue as to whether F really is consistent; no doubts about the consistency of F would be resolved by such a consistency proof. The interest in consistency proofs lies in the possibility of proving the consistency of a system F in some system F' that is in some sense less doubtful than F itself, for example weaker than F. For many naturally occurring theories F and F', such as F = Zermelo–Fraenkel set theory and F' = primitive recursive arithmetic, the consistency of F' is provable in F, and thus F' cannot prove the consistency of F by the above corollary of the second incompleteness theorem.
> 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).
It's possible to prove the values of certain busy beaver numbers, of course, but that's equivalent to noting that you can prove whether certain TMs halt. For example, it is possible to run every n-state TM long enough that, for each TM, you've either observed it halt or you've proved that it's in an infinite loop. The problem is that, for any TM that you haven't observed halt and you haven't been able to prove it's in an infinite loop, you just gotta keep waiting until one or the other happens. And, critically, you can't know if you'll ever come up with a proof that it's in an infinite loop.
Yeah. In the most egregious case it could come down to simply listing the numbers that we have proofs for.
Another interesting thought is whether we can prove the limit of say ZFC in busy beaver numbers with just ZFC. We have BB(745) limit for ZFC. It would be fascinating if “BB(20) is independent of ZFC” turns out to be independent of ZFC as well.
> 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.
It's not that there is necessarily any particular TM that you can't prove halts or doesn't halt. It's that you can't develop a TM that can prove, for each and every TMs, whether they halt.
Busy beaver series is uncomputable as a whole, but not for its individual values. So in theory we can solve arbitrarily many busy beaver numbers, just can’t write a program to list them endlessly.
Ex: no reason yet in theory why we can’t solve and list the first 100k busy beaver numbers or 200k, covering many practical uses for halting problem. But there’s always a limit, we can’t compress the infinite list of values into some code to generate them.
(In theory.. we may never solve BB(6), but that’s not because of undecidability at all.)
Sorry, you are wrong here. We may never solve BB(6) exactly because of undecidability. We don't have an algorithm for computing BB(6). If we had one, BB(6) would be computable (= decidable). Of course, as soon as we know BB(6) = n, for some numeric literal n, it is trivially clear that BB(6) is computable/decidable:
function BB(k) {
if (k === 6) return n;
}
Granted, we don't know if BB(6) is decidable or not, because we don't know if there are proofs in reasonable axiomatic theories which show for each of the 6-state TMs which don't halt that they don't halt. That there are only finitely many such TMs does not really matter here. For something like BB(3) there are only 21 TMs, so we can try our luck to prove that those TMs which don't seem to halt actually don't halt, and hey, we got lucky, we can! Nobody knows if we have the same kind of luck for BB(6).
Indeed, for BB(745) we know that at least for ZFC, we don't have this kind of luck. Of course, if we knew BB(745) = n, for some numeric literal n, then in ZFC + {BB(745) = n} we have that BB(745) is decidable, but if you don't like logical tricks, then you won't like that result too much, either.
The fact that BB(745) is undecidable in ZFC doesn't mean that it will stay unknown forever. But we will have to come up with some other mathematical explanation than ZFC to know BB(745), and nobody knows if such an explanation exists. It could also be that you come up with such an explanation, but many others don't agree with it. Now, on which grounds would you defend your explanation?
But I am a Platonist, so I do agree with you that there is some sort of mathematical explanation for BB(745) = n for some n formulated in a suitable mathematical theory. Because obviously, such an n must exist. Because TMs are real, and they either halt or they don't (Platonist leap of faith I). And then there must be a way to explain why that is (Platonist leap of faith II). But it may be that we never find such an explanation, and/or that humans are too limited to understand the explanation. Certainly, there is no known general algorithm to find human-understandable answers to all human-understandable mathematical questions, and that's why undecidability is the reason we may never know BB(6).
I believe we are in agreement about everything. I just would not say that undecidability is the reason why we can't solve BB(6), it would be some reason such as you mention (unable to prove 6-state machines halt).
In jest. If I am lacking a source of heat, the reason for my being unable to cook food isn't my lack of Superman heat vision eye laser beams. Similarly, the fact that we can never skip all of math with one finite algorithm isn't the reason why we can't discover BB(6).
In any case, at a Platonic level there is no such algorithm, so us lacking it can't be the reason why we can't solve BB(6). In a way it's even less realistic than Superman heat vision eye laser beams.
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?
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.
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?
> 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.
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.
One response brings up the (un)decidability of determining if a physical system's ground state is separated from the rest of its spectrum:
> And there are still cases going on today where undecidability results are of broad interest to those outside of logic. For example, the "spectral gap problem" in physics asked whether, given a description of a physical system, whether that system requires a minimum amount of energy to nudge it out of its ground state, or whether arbitrarily small amounts of energy can nudge it out of its ground state. This was proven to be undecidable in 2015, basically telling physicists that a theoretical problem of theirs, motivated entirely by physical considerations, is hopeless in full generality.
Well that sucks.[1] But I think it's cool that theoretical physics and theoretical computer science seem to meet together in these low places. Information has thermodynamic consequences and vice versa.
64 comments
[ 1.8 ms ] story [ 156 ms ] thread[1]: Where practical is in the sense of an engineer (or in their terms, a CS practitioner), not a theoretician. Most of the responders seem to interpret practical in the sense of a mathematician.
very astute observation. Now I'm left wondering how this comes to be?
what is it about the way in which a general CS practitioner's approach to problem solving that grounds the potential ideas (of how to solve problem) into the computationally decidable?
Configuration processing. E.g. I'd like my yamls to be decidable, though I'll settle for guaranteed to halt[1].
[1] https://dhall-lang.org/
I don’t think I agree! For example, I strongly suspect that Malware detection researchers would be following many fruitless paths in the vein of “Let’s just figure out what the program is doing” if not guided by the fact that this is strictly harder than “Let’s just figure out if the program halts.”
https://googleprojectzero.blogspot.com/2021/12/a-deep-dive-i...
"JBIG2 doesn't have scripting capabilities, but when combined with a vulnerability, it does have the ability to emulate circuits of arbitrary logic gates operating on arbitrary memory. So why not just use that to build your own computer architecture and script that!? That's exactly what this exploit does. Using over 70,000 segment commands defining logical bit operations, they define a small computer architecture with features such as registers and a full 64-bit adder and comparator which they use to search memory and perform arithmetic operations. It's not as fast as Javascript, but it's fundamentally computationally equivalent.
The bootstrapping operations for the sandbox escape exploit are written to run on this logic circuit and the whole thing runs in this weird, emulated environment created out of a single decompression pass through a JBIG2 stream. It's pretty incredible, and at the same time, pretty terrifying."
1 billion dollars later: We discovered we can't do X because there's this thing called "undecidability."
Undecidability puts fundamental limits on what we can do with computers. You can't even do simple things like write a program which can { determine if two programs are equal, determine if two programs would have equal outputs given any input, if any program will return a "1", if any program would halt, ... }
This feels kinda important considering what people might try to build using AI.
1: https://www.bbc.com/news/technology-62275326
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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).
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.
Every proof for undecidability use hypothetical TM constructions with a logical property and a trick. Busy beaver numbers are concrete.
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.
I don't understand this point at all. Busy beaver lets you solve halting and vice-versa. If there are some special cases in which you can solve busy beaver then you can use them to solve halting.
Each individual busy beaver number can't be solved in theory for the same reason that the halting problem can't - if you try to check all n-state Turing machines to compute BB(n) some of them won't halt, and some of those you won't be able to prove that they don't halt.
Source? AFAIK we aren’t aware of any TMs which are impossible to prove loops forever. Turing’s proof only applies to finite halting code that works for arbitrary TMs and inputs. There will never be a solution for every busy beaver number for that reason. However I suspect for ex the program to compute BB(6) to be much larger than 6 states, (even just to print the number) so turings diagonalozation argument doesn’t fit.
There are explicitly known Turing machines which it is impossible to prove their whether or not they halt within ZFC. You could argue that you can construct a stronger logical system within which it is possible to prove one of these machines halts, the problem is that you can never be sure your stronger system is consistent. If you manage to come up with a proof within some stronger system that the machine halts, it may also be possible to come up with a proof that it does not halt (if the system is inconsistent).
I’m not so worried about consistency. Even ZFC has the issue you describe. I found this paragraph from Wikipedia about Gödels 2nd incompleteness theorem very interesting.
> The corollary also indicates the epistemological relevance of the second incompleteness theorem. It would actually provide no interesting information if a system F proved its consistency. This is because inconsistent theories prove everything, including their consistency. Thus a consistency proof of F in F would give us no clue as to whether F really is consistent; no doubts about the consistency of F would be resolved by such a consistency proof. The interest in consistency proofs lies in the possibility of proving the consistency of a system F in some system F' that is in some sense less doubtful than F itself, for example weaker than F. For many naturally occurring theories F and F', such as F = Zermelo–Fraenkel set theory and F' = primitive recursive arithmetic, the consistency of F' is provable in F, and thus F' cannot prove the consistency of F by the above corollary of the second incompleteness theorem.
It's possible to prove the values of certain busy beaver numbers, of course, but that's equivalent to noting that you can prove whether certain TMs halt. For example, it is possible to run every n-state TM long enough that, for each TM, you've either observed it halt or you've proved that it's in an infinite loop. The problem is that, for any TM that you haven't observed halt and you haven't been able to prove it's in an infinite loop, you just gotta keep waiting until one or the other happens. And, critically, you can't know if you'll ever come up with a proof that it's in an infinite loop.
Another interesting thought is whether we can prove the limit of say ZFC in busy beaver numbers with just ZFC. We have BB(745) limit for ZFC. It would be fascinating if “BB(20) is independent of ZFC” turns out to be independent of ZFC as well.
It's not that there is necessarily any particular TM that you can't prove halts or doesn't halt. It's that you can't develop a TM that can prove, for each and every TMs, whether they halt.
Ex: no reason yet in theory why we can’t solve and list the first 100k busy beaver numbers or 200k, covering many practical uses for halting problem. But there’s always a limit, we can’t compress the infinite list of values into some code to generate them.
(In theory.. we may never solve BB(6), but that’s not because of undecidability at all.)
The fact that BB(745) is undecidable in ZFC doesn't mean that it will stay unknown forever. But we will have to come up with some other mathematical explanation than ZFC to know BB(745), and nobody knows if such an explanation exists. It could also be that you come up with such an explanation, but many others don't agree with it. Now, on which grounds would you defend your explanation?
But I am a Platonist, so I do agree with you that there is some sort of mathematical explanation for BB(745) = n for some n formulated in a suitable mathematical theory. Because obviously, such an n must exist. Because TMs are real, and they either halt or they don't (Platonist leap of faith I). And then there must be a way to explain why that is (Platonist leap of faith II). But it may be that we never find such an explanation, and/or that humans are too limited to understand the explanation. Certainly, there is no known general algorithm to find human-understandable answers to all human-understandable mathematical questions, and that's why undecidability is the reason we may never know BB(6).
In jest. If I am lacking a source of heat, the reason for my being unable to cook food isn't my lack of Superman heat vision eye laser beams. Similarly, the fact that we can never skip all of math with one finite algorithm isn't the reason why we can't discover BB(6).
In any case, at a Platonic level there is no such algorithm, so us lacking it can't be the reason why we can't solve BB(6). In a way it's even less realistic than Superman heat vision eye laser beams.
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?
Whereas the halting problem is known to be unsolvable.
I just prefer things that are solvable in theory to things that aren’t.
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?
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.
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.
https://www.digitalonus.com/the-origins-of-functional-progra...
> And there are still cases going on today where undecidability results are of broad interest to those outside of logic. For example, the "spectral gap problem" in physics asked whether, given a description of a physical system, whether that system requires a minimum amount of energy to nudge it out of its ground state, or whether arbitrarily small amounts of energy can nudge it out of its ground state. This was proven to be undecidable in 2015, basically telling physicists that a theoretical problem of theirs, motivated entirely by physical considerations, is hopeless in full generality.
Well that sucks.[1] But I think it's cool that theoretical physics and theoretical computer science seem to meet together in these low places. Information has thermodynamic consequences and vice versa.
[1] https://arxiv.org/abs/1502.04135
https://en.wikipedia.org/wiki/Logical_consequence