Normal

Normal is an encoding of Unary programs using the binary expansion of π. A Normal program is a pair of integers (P, L) naming the position and length of a bitstring in π. Running a Normal program means computing π out far enough to read those bits back out, decoding them as a Unary program representing a brainfuck program, and executing the result.

The encoding is named after normal numbers, which are numbers whose subsequences of digits are distributed uniformly. If π is normal in base 2 then every bitstring of k bits occurs with probability 2^-k; in particular, if π is normal then every Unary program occurs somewhere within it. Moreover, the expected difficulty of finding a program of length k would scale exponentially in difficulty with k. However, it has not been proven that π is normal. It is also possible that π contains all finite bitstrings even if π is not normal.

Encoding

A Brainfuck program is first translated into a bitstring, 3 bits per instruction:

Instruction	Bits
>	000
<	001
+	010
-	011
.	100
,	101
[	110
]	111

For example, +[.+] (which prints the byte values 1 through 255) encodes as:

+ [ . + ]
010 110 100 010 111

giving the 15-bit string 010110100010111.

Source format

A Normal source file contains exactly two whitespace-separated positive integers and nothing else: the position P and the length L, e.g.

62564 15

Position 1 is defined as the first bit after the binary point of π, so the addressable region begins at the leftmost bit of 11.0010010000...₂.

Computational class

The time complexity of decoding a program is quadratic in its length, using Bellard's algorithm. Assuming π is normal, the time complexity of encoding a program is exponential.

The following example code from User:Corbin, based on some old continued-fraction Python code, decodes programs in quadratic time using one of Gosper's continued-fraction algorithms.

from math import gcd
def pi():
    yield (0, 4)
    p = 1
    q = 1
    while True:
        yield (p, q**2)
        p += 2
        q += 1
def simplified():
    i = pi()
    a, b, c, d = 0, 1, 1, 0
    while True:
        p, q = next(i)
        a, b, c, d = b * q, a + b * p, d * q, c + d * p
        div = gcd(a, b, c, d)
        if div != 1: a, b, c, d = a // div, b // div, c // div, d // div
        ac = a // c if c else None
        bd = b // d if d else None
        while None not in (ac, bd) and ac == bd:
            r = ac
            a, b = 2 * (a - c * r), 2 * (b - d * r)
            yield r
            ac = a // c if c else None
            bd = b // d if d else None
BFS = "><+-.,[]"
def decode(i):
    while True:
        x = next(i) * 4
        x += next(i) * 2
        x += next(i)
        yield BFS[x]
def lookup(p, l):
    cf = simplified()
    for x in range(p): i = next(cf)
    bf = decode(cf)
    for _ in range(l): print(next(bf), end="", flush=True)

Related languages

Normal is part of an informal series of esolangs exploring different notions of computational difficulty, alongside PrimeScript, Square, Trapdoor, Hard, and PrimeIndex. Where Hard is theoretically impossible and the others rely on ordinary computational complexity, Normal's difficulty is mathematical depth: the difficulty of locating a program within an infinite, largely uncomputed sequence, rather than the difficulty of a bounded computation.