3 ms·

>This first idea that math have some intrinsic limitations - eg: you can’t compute all the Busy Beaver Numbers But this is not a limitation of mathematics at l

>This first idea that math have some intrinsic limitations - eg: you can’t compute all the Busy Beaver Numbers But this is not a limitation of mathematics at least not any more so than there being no largest prime number is a limitation of mathematics. It is a limitation on abstract systems, such as Turing machines. The halting problem is not that you can not deduce whether any given Turing machine halts, but that there is no Turing machine that deducing this. Gödel's (ö and o are different letters, by the way) theorems are far more wide reaching, as they appy to large classes of axiomatic systems, but they are only making claims about the systems in relation to themselves.

bigbillheck 3y ago
> no smallest prime number Behold: 2.
- olddustytrail 3y ago
  -2 is smaller... (I'll let someone better educated expand on prime ideals)
kbrkbr 3y ago
As the smallest prime number is 2 you probably meant "there being no largest prime number".
- constantcrying 3y ago
  Indeed...
tux3 3y ago
The Busy Beaver numbers express a limitation of classes of axiomatic systems, not merely of Turing Machines. It's not merely that computers aren't guaranteed to be able to calculate these. BB(n) for some n <= 745 is independent of the ZFC axioms of set theory. Furthermore, Gödel's theorem and Turing's problem are related. It is undecidable whether a Turing machine halts, it's not just that you can't write a Turing machine that decides whether another Turing machine halts. Without Gödel's theorem, you could try to enumerate all possible proofs in your complete and consistent axiomatic system until you find one that proves whether an arbitrary Turing machine of your choosing halts, and you'd have conceptually solved the halting problem. (Then, you could encode that whole algorithm in a Turing machine (TM), and have that new TM be your decider that solves the halting problem, if you wanted). Because of Gödel you can't do this, whether on paper, with a TM, or even in principle. Your axiomatic system is not complete, so there are things it simply cannot prove. Like the halting problem, or in the case of ZF the value of BB(745).

bigbillheck 3y ago

> no smallest prime number Behold: 2.

olddustytrail 3y ago
-2 is smaller... (I'll let someone better educated expand on prime ideals)

kbrkbr 3y ago

As the smallest prime number is 2 you probably meant "there being no largest prime number".

constantcrying 3y ago
Indeed...

tux3 3y ago

The Busy Beaver numbers express a limitation of classes of axiomatic systems, not merely of Turing Machines. It's not merely that computers aren't guaranteed to be able to calculate these. BB(n) for some n <= 745 is independent of the ZFC axioms of set theory. Furthermore, Gödel's theorem and Turing's problem are related. It is undecidable whether a Turing machine halts, it's not just that you can't write a Turing machine that decides whether another Turing machine halts. Without Gödel's theorem, you could try to enumerate all possible proofs in your complete and consistent axiomatic system until you find one that proves whether an arbitrary Turing machine of your choosing halts, and you'd have conceptually solved the halting problem. (Then, you could encode that whole algorithm in a Turing machine (TM), and have that new TM be your decider that solves the halting problem, if you wanted). Because of Gödel you can't do this, whether on paper, with a TM, or even in principle. Your axiomatic system is not complete, so there are things it simply cannot prove. Like the halting problem, or in the case of ZF the value of BB(745).