4 ms·

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

by 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.
- woopsn 3y ago
  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.
  - srcreigh 3y ago
    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.
- ogogmad 3y ago
  > 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.

by woopsn 3y ago

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.

woopsn 3y ago
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.
- srcreigh 3y ago
  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.
ogogmad 3y ago
> 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.