5 ms·
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 b
by 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 agof(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 agoThat's an irrelevant example because your f(n) does not have a self-contained mathematical definition.
- woopsn 3y agoScott 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 agoYou 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.
- deleted 3y ago[deleted]
- kakaz 3y agoPlease 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 agoSuch as?
- practal 3y agoNice 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.