5 ms·

BB(748) - BB(745) is probably the largest value that anyone has ever described as "tiny" :-)

by arethuza 3y ago

danbruc 3y ago
I would assume tiny refers to three.
- TheRealNGenius 3y ago
  [dead]
sebzim4500 3y ago
It's actually really hard to come up with an interesting lower bound that value. IIRC no one has proven that BB(n) + 1 < BB(n + 1) for large 2
- kevinventullo 3y ago
  Hm, is there some way to “concatenate” Turing machines which would let you prove something like BB(n) + BB(m) <= BB(n+m+c) for some fixed c independent of n and m?
  - nyssos 3y ago
    It seems very unlikely: the full joint state space has n*m states, so you're throwing away almost everything for large n and m.
  - sebzim4500 3y ago
    You can, but BB(1) = 1 so that doesn't help with BB(n + 1) > BB(n) + 1
- deleted 3y ago
  [deleted]
- Someone 3y ago
  Take the machine for BB(n) with non-end states {1,2,3,…n} and end state E. In its program, change every transition that goes to state E to go to a new state n+1 instead. Add transitions “when in state n+1 and on a 1, move right” and “when in state n+1 and on a 0, write a 1 and stop”. Doesn’t that give you a Turing machine with n+1 states that stops after writing one more 1 than BB(n) writes, thus proving that BB(n+1) is at least one more than BB(n+1)?
  - sebzim4500 3y ago
    yeah, that shows BB(n+1) >= BB(n) + 1, but if you want to make the inequality strict you need to find a way to add another step.
    - Someone 3y ago
      Oops. Reversing your “BB(n) + 1 < BB(n + 1)” turned out to be too difficult for me today. Thanks for the reply.
im3w1l 3y ago
If BB(745) is independent of ZFC can it even be called a value? It seems like you could easily run into paradoxes if you treated it like just any other value.
- pas 3y ago
  just because it's not provably constructable from axioms it doesn't mean it's not just a finite number. that's the really mindbreaking part in this. it's really just like 5. except 5 is provably constructable, describable, nameable. (most numbers are not, just as - for example - angle trisection is impossible with just a straightedge and a compass ) https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers#Definition_as_von_Neumann_ordinals https://en.wikipedia.org/wiki/Set-theoretic_definition_of_na... http://uu.diva-portal.org/smash/get/diva2:1715729/FULLTEXT01.pdf http://uu.diva-portal.org/smash/get/diva2:1715729/FULLTEXT01...
- Kranar 3y ago
  There is no paradox and yes, BB(745) is a specific integer, so it's nothing more than a sequence of finite digits. The fact BB(745) can't be constructed using ZFC only means that there is at least one Turing machine among the set of all 745 state Turing machines that runs forever, but can't be proven to run forever using the axioms of ZFC. You'd need a more powerful axiomatic system to prove that this Turing machine actually runs forever. This does not imply any kind of paradox or any kind of issue whatsoever in fact. It just means that ZFC is not powerful enough to prove that certain 745 state Turing Machines run forever.
  - thaumasiotes 3y ago
    > The fact BB(745) can't be constructed using ZFC only means that [...] ...so what? The claim wasn't that BB(745) can't be constructed using ZFC, or that it's not computable. The claim was that its value is independent of ZFC, that the ZFC axioms do not make any logical implication about the value. This necessarily means that there are multiple possible values; if there were only one value, that value would be logically implied by ZFC regardless of whether it was provable in ZFC. I should also note that these two observations are not compatible with each other: > BB(745) is a specific integer, so it's nothing more than a sequence of finite digits > BB(745) can't be constructed using ZFC All finite digit sequences can be constructed.
explaininjs 3y ago
It's hard to comprehend just how big that number is. It may indeed be among the largest numbers ever conceived, and we'd have no clue. I wouldn't be surprised if it is larger the number of possible permutations of all particles in the observable universe, for instance. I'd be more surprised if it was less than that.
- MichaelDickens 3y ago
  Graham's number used to be the largest number ever used in a proof, but BB(745) is much larger—Graham's number has been proven to be smaller than BB(16)[1] (although I don't know how carefully the proof has been checked). [1] https://www.sligocki.com/2022/07/11/bb-16-graham.html https://www.sligocki.com/2022/07/11/bb-16-graham.html
  - tromp 3y ago
    A number much larger than Graham's can be represented in less than 64 bits [1], using a functional flavored Busy Beaver function [2]. [1] https://googology.fandom.com/wiki/User_blog:JohnTromp/The_largest_number_representable_in_64_bits https://googology.fandom.com/wiki/User_blog:JohnTromp/The_la... [2] https://oeis.org/A333479 https://oeis.org/A333479
- danbruc 3y ago
  A commonly quoted number for the number of particles in the observable universe is 10^80 give or take a few orders of magnitude an they have very roughly 10^10^10^2 permutations if you consider all particles distinguishable. The best known lower bound for BB(6, 2) seems to be 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 which is more like the number of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of the particles in the universe. Trying to comprehend or compare the size of BB(745) is just futile. Here [1] is a well known attempt to convey the size of 52!, the number of permutations of a deck of cards. [1] https://www.youtube.com/watch?v=ObiqJzfyACM&t=947s https://www.youtube.com/watch?v=ObiqJzfyACM&t=947s

BB(748) - BB(745) is probably the largest value that anyone has ever described as "tiny" :-)

danbruc 3y ago

I would assume tiny refers to three.

TheRealNGenius 3y ago
[dead]

sebzim4500 3y ago

It's actually really hard to come up with an interesting lower bound that value. IIRC no one has proven that BB(n) + 1 < BB(n + 1) for large 2

kevinventullo 3y ago
Hm, is there some way to “concatenate” Turing machines which would let you prove something like BB(n) + BB(m) <= BB(n+m+c) for some fixed c independent of n and m?
- nyssos 3y ago
  It seems very unlikely: the full joint state space has n*m states, so you're throwing away almost everything for large n and m.
- sebzim4500 3y ago
  You can, but BB(1) = 1 so that doesn't help with BB(n + 1) > BB(n) + 1
deleted 3y ago
[deleted]
Someone 3y ago
Take the machine for BB(n) with non-end states {1,2,3,…n} and end state E. In its program, change every transition that goes to state E to go to a new state n+1 instead. Add transitions “when in state n+1 and on a 1, move right” and “when in state n+1 and on a 0, write a 1 and stop”. Doesn’t that give you a Turing machine with n+1 states that stops after writing one more 1 than BB(n) writes, thus proving that BB(n+1) is at least one more than BB(n+1)?
- sebzim4500 3y ago
  yeah, that shows BB(n+1) >= BB(n) + 1, but if you want to make the inequality strict you need to find a way to add another step.
  - Someone 3y ago
    Oops. Reversing your “BB(n) + 1 < BB(n + 1)” turned out to be too difficult for me today. Thanks for the reply.

im3w1l 3y ago

If BB(745) is independent of ZFC can it even be called a value? It seems like you could easily run into paradoxes if you treated it like just any other value.

pas 3y ago
just because it's not provably constructable from axioms it doesn't mean it's not just a finite number. that's the really mindbreaking part in this. it's really just like 5. except 5 is provably constructable, describable, nameable. (most numbers are not, just as - for example - angle trisection is impossible with just a straightedge and a compass ) https://en.wikipedia.org/wiki/Set-theoretic_definition_of_natural_numbers#Definition_as_von_Neumann_ordinals https://en.wikipedia.org/wiki/Set-theoretic_definition_of_na... http://uu.diva-portal.org/smash/get/diva2:1715729/FULLTEXT01.pdf http://uu.diva-portal.org/smash/get/diva2:1715729/FULLTEXT01...
Kranar 3y ago
There is no paradox and yes, BB(745) is a specific integer, so it's nothing more than a sequence of finite digits. The fact BB(745) can't be constructed using ZFC only means that there is at least one Turing machine among the set of all 745 state Turing machines that runs forever, but can't be proven to run forever using the axioms of ZFC. You'd need a more powerful axiomatic system to prove that this Turing machine actually runs forever. This does not imply any kind of paradox or any kind of issue whatsoever in fact. It just means that ZFC is not powerful enough to prove that certain 745 state Turing Machines run forever.
- thaumasiotes 3y ago
  > The fact BB(745) can't be constructed using ZFC only means that [...] ...so what? The claim wasn't that BB(745) can't be constructed using ZFC, or that it's not computable. The claim was that its value is independent of ZFC, that the ZFC axioms do not make any logical implication about the value. This necessarily means that there are multiple possible values; if there were only one value, that value would be logically implied by ZFC regardless of whether it was provable in ZFC. I should also note that these two observations are not compatible with each other: > BB(745) is a specific integer, so it's nothing more than a sequence of finite digits > BB(745) can't be constructed using ZFC All finite digit sequences can be constructed.

explaininjs 3y ago

It's hard to comprehend just how big that number is. It may indeed be among the largest numbers ever conceived, and we'd have no clue. I wouldn't be surprised if it is larger the number of possible permutations of all particles in the observable universe, for instance. I'd be more surprised if it was less than that.

MichaelDickens 3y ago
Graham's number used to be the largest number ever used in a proof, but BB(745) is much larger—Graham's number has been proven to be smaller than BB(16)[1] (although I don't know how carefully the proof has been checked). [1] https://www.sligocki.com/2022/07/11/bb-16-graham.html https://www.sligocki.com/2022/07/11/bb-16-graham.html
- tromp 3y ago
  A number much larger than Graham's can be represented in less than 64 bits [1], using a functional flavored Busy Beaver function [2]. [1] https://googology.fandom.com/wiki/User_blog:JohnTromp/The_largest_number_representable_in_64_bits https://googology.fandom.com/wiki/User_blog:JohnTromp/The_la... [2] https://oeis.org/A333479 https://oeis.org/A333479
danbruc 3y ago
A commonly quoted number for the number of particles in the observable universe is 10^80 give or take a few orders of magnitude an they have very roughly 10^10^10^2 permutations if you consider all particles distinguishable. The best known lower bound for BB(6, 2) seems to be 10^10^10^10^10^10^10^10^10^10^10^10^10^10^10 which is more like the number of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of permutations of the particles in the universe. Trying to comprehend or compare the size of BB(745) is just futile. Here [1] is a well known attempt to convey the size of 52!, the number of permutations of a deck of cards. [1] https://www.youtube.com/watch?v=ObiqJzfyACM&t=947s https://www.youtube.com/watch?v=ObiqJzfyACM&t=947s