CounterScript

CounterScript is a minimal counter-based programming language designed for Busy Beaver–style program enumeration and analysis.

It features a very small instruction set operating over an unbounded set of nonnegative integer variables (counters).

BBCS(n) is the Busy Beaver function for CounterScript programs.

Definition

A CounterScript program consists of a finite sequence of instructions drawn from three primitives:

• Increment a counter
• Conditional decrement
• While loop

All counters are initialized to 0 and can grow without bound.

The model is closely related to Minsky register machines, Fractran and Brainfuck, and is therefore Turing-complete.

Instructions

Instructions are executed one by one from left to right.

Name	Command	Definition
Increment	A++	Increment counter A by 1
Decrement	A--	Decrement counter A by 1 if A > 0
While loop	while A {...}	Executes the loop body while x > 0

Macros

In order to improve readability we define the following macros.

	Macro	Definition	Size	Function
Constant Addition	A+=n;	increment A by n	n	A++; repeated n times
Transfer	A>>B*n;	increment B by A*n then set A to 0	3	while A {A--; B++;}

BBCS

The Busy Beaver function for CounterScript, denoted BBCS(n), returns the largest score a CounterScript program of length n can have when halting.

The score of a program is the maximum value of its counters.

The length of a CounterScript program is defined as the total number of instructions.

By example, A++; B++; while A {A--; C++; C++;} has length 6 and its score is 2.

n	BBCS(n)	Champion
1	1	A++;
2	2	A+=2;
3	3	A+=3;
4	4	A+=4;
5	5	A+=5;
6	6	A+=6;
7	7	A+=7;
8	9	A+=3; A>>B*3;
9	12	A+=4; A>>B*3;
10	16	A+=4; A>>B*4;
11	≥ 20	A+=5; A>>B*4;
12	≥ 25	A+=5; A>>B*5;
13	≥ 30	A+=6; A>>B*5;
14	≥ 84	A+=3; while A {A--; B++; B>>C*2; C>>B*2;}
15	≥ 340	A+=4; while A {A--; B++; B>>C*2; C>>B*2;}
16	≥ 1,554	A+=4; while A {A--; B++; B>>C*3; C>>B*2;}
17	≥ 9,330	A+=5; while A {A--; B++; B>>C*3; C>>B*2;}
18	≥ 66,429	A+=5; while A {A--; B++; B>>C*3; C>>B*3;}
19	≥ 597,870	A+=6; while A {A--; B++; B>>C*3; C>>B*3;}
20	≥ 4^1365	A+=3; while A {A--; B++; while B {B--; C++; C>>D*2; D>>C*2;} C>>B;}
21	≥ 4^4^1365	A+=4; while A {A--; B++; while B {B--; C++; C>>D*2; D>>C*2;} C>>B;}
22	≥ 4^4^4^1365	A+=5; while A {A--; B++; while B {B--; C++; C>>D*2; D>>C*2;} C>>B;}
23	≥ 4^4^4^4^1365	A+=6; while A {A--; B++; while B {B--; C++; C>>D*2; D>>C*2;} C>>B;}
24	≥ 4^4^4^4^4^1365	A+=7; while A {A--; B++; while B {B--; C++; C>>D*2; D>>C*2;} C>>B;}
25	≥ 2^^2^15	A+=3; while A {A--; B++; while B {B--; C++; while C {C--; D++; D>>E*2; E>>D;} D>>C;} C>>B;}
26	≥ 2^^2^^2^15	A+=4; while A {A--; B++; while B {B--; C++; while C {C--; D++; D>>E*2; E>>D;} D>>C;} C>>B;}
65	> Graham's number

Cryptids

TODO