From Esolang
Jump to navigation Jump to search

One is a language invented by User:Tailcalled. It is an uncomputable extension to a Brainfuck dialect, but it is designed to not be significantly more powerful than ordinary Brainfuck.

One has nine instructions, eight of which are similar to brainfuck. The syntax rules are the same as in Brainfuck. In addition to the memory pointer, there is an internal counter, C.

Instruction Description Name
Increment Increments the value pointed to. There is no maximal value. +
Decrement Decrements the value pointed to. There is no minimal value. -
Next Increments the pointer. There is no maximal index. >
Previous Decrements the pointer. There is no minimal index. <
Loop (begin) Loops the body while the value pointed to is not zero. [
Loop (end) ]
Output Outputs the value pointed to as a unicode codepoint if valid; otherwise noops. .
Input Inputs a unicode codepoint and stores it as the value pointed to. Stores zero on EOF. ,
Instruction Consider the Busy Beaver function for Brainfuck. Let x be the value pointed to. Instruction stores the xth bit of the Cth Busy Beaver number as the value pointed to, followed by incrementing C. Stores zero on negative input, as the fractional part of any Busy Beaver number is zero. I

Intuitively, Instruction seems hard to compute and not very useful. It is not immediately obvious how to prove those statements.

Busy Beaver

Since the Busy Beaver function is not completely unambiguous, I will define exactly what it is here. When I talk about Brainfuck, I am referring to One, without Instruction and without comments.

Consider Brainfuck, but augmented with a hidden counter C and an instruction for incrementing C, which I will call J, a shortening of Jnstruction. Call this language Jrainfuck. The time of an ordinary Brainfuck program P is the final value of C given running P as a Jrainfuck program with the following modifications:

  1. A J is inserted before every character.
  2. Every , is replaced by [-].

If the program does not halt, the time is said to be 0.

Busy beaver of x is then given by the maximal time of a program of at most x length. In particular, BB(0) is 0, as only the empty program has zero length. BB(1) is 1, as any 1-length program executes the same amount of instructions. Note that the time of [] is 1. The time of -, is zero, as it does not halt after the modification.