Been reading up about the <Busy Beaver function> a...
# random
y
Been reading up about the Busy Beaver function and some of its equivalents Which makes me wonder what a Kotlin equivalent would look like? Bytes, syntactic tokens, maybe FIR nodes? Would be fun to see what amount of bytes/tokens/etc is needed for really complex programs to appear! Also, it'd be interesting to see what's the smallest Kotlin program using that metric that's independent of ZFC (handwaving the foundation of modern math). For reference, normal Busy Beaver has that at 230, meaning 230-state Turing machine! What this entails is writing a small program that runs thru all the (infinitely many) proofs in ZFC and checks them for consistency (I can explain more if anyone's interested!) Of course, if you build a small Turing Machine simulator in Kotlin, you can already get an upper bound on this! I hypothesize that a direct implementation would be smaller though!
🤔 1
g
I am not that interested in the actual minimal values of the metrics. Instead, it's interesting to understand what makes a small program halt iff something is satisfied. I mean, it was very surprising to me that instead of ZFC you can put, for example, Riemann hypothesis. And for Riemann hypothesis, the machines are even smaller. I didn't dive into this area of CS (and I am not going to research anything there), but it's interesting to hear and talk about!
y
A SWE way to think of this is: imagine you have truly infinite time; design a test suite that, if hypothesis Foo is wrong, finds proof that it is (e.g. a counterexample) For ZFC, I believe the program generates all proofs one-by-one, and checks if their result is
0=1
. We do this all the time with property-based testing, where we use sampling instead of infinite time. I think it's then interesting to compare machine size (or whatever metric we use for Kotlin) for these different hypotheses, perhaps as a measurement of their complexity, or maybe a measurement of how much we understand them. A fun thought experiment is that, if there exists closed time-like curves in our world, then (I think) you can chuck a computer with such a test suite in there, and it'd instantly give you an answer.