BBCPP:Main

From RPGDL

Jump to: navigation, search

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

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

BBCPP:FunctionSandbox

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).

Personal tools