Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:16 AM
[math] sometimes I think about the Busy Beaver Function and get kind of dizzy about scale
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:17 AM
here's the deal with beaver
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:17 AM
it's a function, that takes one integer as an input
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:18 AM
and the output is, to simplify a bit
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:18 AM
if you put in X
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:18 AM
then the output is, if you made a turing machine - the basic fundamenttal form of computer programs - with X possible states
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:19 AM
and put it on an infinite memory strip of 0's
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:19 AM
the largest possible non-infinite number of 1's the program could write before halting
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:19 AM
so like if you had a two-state machine it could be something like
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:19 AM
State 1: If the pointer is on a 0, write a 1, move to the right, and enter State 2
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:19 AM
State 2: Halt
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:20 AM
the program would write 1 once, then halt, creating a total of a single 1 on the memory strip
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:20 AM
but the more states you have, the more complex you can make the program, so it can fill more and more memory before halting
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:20 AM
so that's what the Busy Beaver function is
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:21 AM
BB(x) = the largest finite number of 1s you could design a turing machine to write to memory using X states
Villain
@Overbringer
Thu, Feb 9, 2023 2:21 AM
this is challenging my concept of what a mathematical function is
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:21 AM
but here's what's interesting
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:21 AM
if you write literally ANY other math function
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:21 AM
say, f(x) = x^x^x^x^x^x * 100,000,000,000,000
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:21 AM
literally anything
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:21 AM
then for a high enough value of X, BB(X) will be bigger.
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:21 AM
It is the Biggest Function.
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:21 AM
Period.
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:22 AM
here's some numbers to show what that looks like.
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:23 AM
the values of BB(x) are only known with certainty up to 4.
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:23 AM
BB(2) = 6
BB(3) = 21
BB(4) = 107
連続犬
@svensational
Thu, Feb 9, 2023 2:23 AM
oh.
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:23 AM
the busiest known beaver for BB(5) outputs 47,176,870 1's to memory before haltingg.
Villain
@Overbringer
Thu, Feb 9, 2023 2:23 AM
BB(5) = some terrifyingly huge number?
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:24 AM
BB(6)'s value is unknown, but the lowest it can be is about
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:24 AM
3.5 * 10^18267
連続犬
@svensational
Thu, Feb 9, 2023 2:24 AM
i think i'm starting to conceptualize why this is called the Busy Beaver function
Villain
@Overbringer
Thu, Feb 9, 2023 2:24 AM
that beaver is very busy
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:25 AM
BB(7)'s lower bound has been shown, as a simple variation of the BB(6) machine
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:25 AM
to stand at 10^10^10^10^18705353
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:25 AM
but in reality the value is probably MUCH higher than that
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:26 AM
Thu, Feb 9, 2023 2:26 AM
calculating the scope of BB(8) has to my knowledge never been seriously attempted
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:26 AM
shut up plurk
Villain
@Overbringer
Thu, Feb 9, 2023 2:26 AM
so if you graphed it out
Villain
@Overbringer
Thu, Feb 9, 2023 2:26 AM
it would functionally just look like a line going straight up
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:26 AM
it would just look like a vertical line yeah
Villain
@Overbringer
Thu, Feb 9, 2023 2:26 AM
with a tiny hook at the bottom if you zoomed in enough
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:27 AM
but no matter what absurd function you made up to try and go higher, BB(x) will ALWAYS eventually overshoot it
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:27 AM
just, with nearly all imaginable functions, "eventually" means "before 10"
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:27 AM
the exact value of BB(x) for larger values is believed to be essentially impossible to calculate
連続犬
@svensational
Thu, Feb 9, 2023 2:28 AM
significantly larger than a googolplex by several orders of magnitude
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:28 AM
like, "if you made a computer the size of the universe and it ran for a trillion years it wouldn't be certain of the answer by the end"
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:29 AM
I don't know how they proved that it's the Biggest Function but it's wild that we just, know what that is
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:30 AM
and it's VERY big
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:32 AM
numbers so big you need to dip into Knuth Notation to even try to express them
EsperBot
@PikaBot
Thu, Feb 9, 2023 2:35 AM
I imagine the proof is related to its definition as being the largest possible output from the number of states
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:35 AM
probably
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:36 AM
regarding knuth notation as long as I'm here
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:36 AM
it goes like this
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:37 AM
A x B = A + A + A + A + .... [B times]
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:37 AM
A^B = A x A x A x A x ... [B times]
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:38 AM
A↑↑B = A ^ A ^ A ^ A ^ A ^ .... [B times]
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:39 AM
A↑↑↑B = A ↑↑ A ↑↑ A ↑↑ A ↑↑ A ↑↑ ... [B times]
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:40 AM
A↑↑↑↑B = A ↑↑↑ A ↑↑↑ A ↑↑↑ A ↑↑↑ .... [B times]
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:41 AM
these numbers get nonsensically big extremely fast
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 2:41 AM
3↑↑↑3 is a stack of 3^3^3^3^... thatt's 7.6 trillion exponents tall
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 3:08 PM
here's my suspicion of how the proof is shaped
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 3:09 PM
roughly
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 3:09 PM
- f(x) can be defined by a turing machine
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 3:09 PM
- BB(x) is definitionally based on the definition of a turing machine
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 3:09 PM
- BB(x)'s turing machine is defined as the maximal machine, so it's by definition producing a bigger result than f(x)
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 3:10 PM
it can't just be that because the first line is provably false by diagonalization
Quinn Angstrom
@quinn2win
Thu, Feb 9, 2023 3:10 PM
but it's probably something like that
載入新的回覆