BBCPP:Main
From RPGDL
Contents |
Busy Beaver with C++esque syntax
Introduction
"What's the biggest number you can write in 10 seconds?"
"What's the biggest number you can output from 5 lines of code?"
This has been a fun mathematical game for a long time. There are people who study this formally with Turing machines (the Busy Beaver Project) and informally with telling kids to write a big number in 10 seconds (big number game).
What I wanted to get was the best of both worlds. The Busy Beaver project is neat, but Turing Machine code is extremely hard to read. On the opposite end of the spectrum, the intuitive "use any operations you want to write the biggest number you can on a piece of paper" feels like allowing everything just encourages you to get extremely obscure and not well-defined.
So...is there a way to do a busy-beaver like project with
- Readable code.
- Code with well-defined limitations
- Produces numbers small enough that we can compare them
Here's what I've been playing with:
Record Holders
| Program Cost | Program Output | Source Code Link | Strategy |
|---|---|---|---|
| 1 | 1 | BBCPP:Cost1 | Increment |
| 2 | 2 | BBCPP:Cost2 | Increment |
| 3 | 3 | BBCPP:Cost3 | Increment |
| 4 | 4 | BBCPP:Cost4 | Increment |
| 5 | 6 | BBCPP:Cost5 | Double-layer Increment |
| 6 | 9 | BBCPP:Cost6 | Double-layer Increment |
| 7 | 12 | BBCPP:Cost7 | Double-layer Increment |
| 8 | 18 | BBCPP:Cost8 | Triple-layer Increment |
| 9 | 27 | BBCPP:Cost9 | Triple-layer Increment |
| 10 | 512 | BBCPP:Cost10 | Single-Layer Exponentiation |
| 11 | ~10^(10^19) | BBCPP:Cost11 | Double-Layer Exponentiation |
| 12 | ~2^^^^^^^^^^14 | BBCPP:Cost12 | Ackermann |
Experimenting with alternate rulesets/notation
BBP:Main - n-variable functions have cost n. Notation = python.
Legal Tokens
These are the legal things to put into your program. Note that all variables are assumed to be numbers, and that numbers have no maximum size. Oh, also, your program must halt (i.e. get to an "Answer" token) and not run forever in order to qualify.
Function Calls
Cost 1
If you define a function foo(a, b), then anywhere you call that function in your program, it adds 1 to the cost.
PlusOne and MinusOne
Cost 1
PlusOne( num ) returns num+1.
If you're wondering why not just use ++ and --, for a variety of reasons. First, they work differently since they assign, and because of the assignment effect aren't well-defined in their behavior--the following does not have fixed behavior in c++: Function( a++, a++ ). Second, they don't bold well at all, which makes counting cost harder.
ifzero
Cost 1
A standard branching operator; takes an integer. i.e.
ifzero( num )
{
return PlusOne( num )
}
Could I add a whole lot of >=, <= etc operators? Sure, but it's a lot of added complexity for no observable gain that I can see.
Function declaration
Free
You can declare as many functions as you want with up to two variables (here's why 2 variables, for the curious) (2 variables still allows general recursion). You pay for functions through the function calls, so having an arbitrary number doesn't help you if you only have cost 10 to play with (and therefore can only call 10 functions).
Function variable reference
Free
You can use these variables as you wish. (Currently you can not modify the variables mid-function, but there are other ways to achieve similar effects).
Return
Free
Your standard function return.
Answer
Free
Like "return" but for your program
0
Free
The only number you are allowed to use directly is 0; all higher/lower numbers must be constructed through PlusOne and MinusOne.
Brackets ( ) { }, Comments //
Free
By all means make your program readable. (That's kinda the idea).
