Brainfoctal

Brainfoctal is a Gödel numbering language, where code is represented and executed direcetly by Gödel numbers. It uses brainf**k as its base, to form a base 8 (octal) number.

Brainfoctal is intended to be a practical way to experiment with Gödel number manipulation and computation by having ready sources of pre-existing code to convert, and pre-existing interpreters.

The Gödel numbering system for numbering all possible bf programs is effectively a TrivialBrainfuckSubstitution to form an octal value, and treating the result as an integer:

 TrivialBrainfuckSubstitution("1","2","3","4","5","6","7","0")

The base-8 Gödel numbering has been extended to base-4 for TinyBF and base-2 for Spoon (which seemed like the best choice out of the multiple binary bfs). See #Variants below.

Brainfoctal is also a Matrioshka language in that its implementation would bundle existing brainf**k, TinyBF, Spoon (and possibly other) implementations together with conversion and helper functions.

It is additionally a Matrioshka language because it implies and bundles at least two other languages which can be used to explore Brainfoctal: #Deadf'shoctal, and #+b. (see below for details)

Why?

With Brainfoctal Gödel numbering, each possible program is a unique number (or symbol), and can be operated on mathematically. A single program number also represents different programs and functionality in other Brainfoctal variants, other languages, and numbering systems. All simultaneously.

History

This is a kind of meta-esolang concept, which probably has been thought up before. It originated from thinking about ZISC languages and initialising memory, and how potentially everything could be included as a lookup table stored in memory, then executing a program to obtain a particular result is simply a matter of determining the lookup index.

Not that the world needed another variant of brainf**k, but this really isn't another language, but a way of representing existing languages, and converting code between languages by treating code as data, and also enabling mathematical operations on code etc.

Language overview

A Brainfoctal program consists of standard bf code (shamelessly ripped from some pre-existing source) converted into an integer by treating the commands as octal digits.

bf	>	<	+	-	.	,	[	]
bf8	1	2	3	4	5	6	7	0

There are other possible mappings, varying these could be interesting, but will likely cause confusion with compatibility.

The resulting value is a natural number and therefore has no intrinsic base in Brainfoctal, so can be represented in any valid way a natural number can be. I believe this distinguishes it from Unary, which even though the octal method is mentioned in discussion, seems to insist upon a specific representation of the result. Brainfoctal differs in that the octal conversion is used to generate the code, which is simply an integer (zero-dimensional). Therefore Unary is closer to #+b.

Here is an example bf Hello, World! in octal, decimal, and hex, showing the compression afforded by the different representations. All are exactly the same program.

 hw_oct = 0o3333333371333371331333133313222240131314113720240115144453333333553335115245253335444444544444444511351335
 hw_dec = 228855768768422936408264393456423041692937029376710995071693817276469283765324982920591645725405
 hw_hex = 0x1b6db6f96dbe5b2db2db2d24a02cb3097d050134c92b6db6ed6dd26a9556dd92492c92492525d2dd

The following all represent the same Brainfoctal program:

42
0x2a
0o52
0b101010
Fourty Two
"Answer to the Ultimate Question of Life, the Universe, and Everything"
XLII
6**2+6

...etc

Converted to bf (as standard bf8) is: -< which decrements the initial cell, then moves the pointer one to the left (not a very interesting program).

Example operations

{specifc_cat_program} * a + b = {specific_hello_world_program}

any Brainfoctal program can be written in terms of any other program using this form. This could be taken advantage for compressing multiple programs into a software bundle.

b can be removed (set to zero) when we do not fix the exact content of the programs, only their behaviour:

{variable_cat} * a = {variable_Hello_World}

If a is a positive integer, it also represents a Brainfoctal program, so we can have equations like this:

{variable_cat} * {variable_Hello_World} = {variable_99_bottles}

The * operator could be replaced with any operation or function. More correctly

f({variable_cat}, {variable_Hello_World}) = {variable_99_bottles}

Because all three variable above are free, f(x,y) could be the multiplication operation, equally addition, or something more complex.

Other functions should be possible to produce useful computational results: if O is some code that produces output, r(n, O) could output a value that repeats O n times.

This could be achieved by repeating O n times (multiply/byte shift and add), OR more interestingly by multiplying/byte shifting and adding a loop value NNNN000...000NN.

O(c) could return the Brainfoctal value of the code that outputs character c.

Programming in Brainfoctal then becomes a sequence of applying mathematical functions to some set of primative numbers representing simple programs.

Example Hello World generation

# This code by User:Salpynx is python, but is meant to
# represent pseudo-code for the mathematical
# function definitions and calculations
# and could be implemented in any language,
# or performed on a calculator with sufficient range.
import math

## The following fn.s all take integers as input, and return only integers

# size(n) => returns the 'size' of a bf8 int (number of bf symbols it represents)
size = lambda n: int(math.floor(math.log(n, 8)) + 1)

# rep(r, n) => repeats r times the code n (not a loop, and where 0<n<8)
rep = lambda r, n: (8**r-1)//7 * n

# out(c) => returns bf8 code that prints ASCII value c
out = lambda c: 8**(c+1) + rep(c, 3) * 8 + 5

# repeatout(n) => appends another output command to n
repeatout = lambda n: n * 8 + 5

# seq(a, b) => combines two bf8 progams in sequence ab
seq = lambda a, b: b + a * 8**size(b)

## Every variable(int) below is a standalone Brainfoctal program

h = out(ord('H'))
e = out(ord('e'))
l = out(ord('l'))
o = out(ord('o'))
w = out(ord('W'))
r = out(ord('r'))
d = out(ord('d'))
space = out(32)

hello = seq(h, seq(e, seq(repeatout(l), o)))
world = seq(w, seq(o, seq(r, seq(l, d))))

## This variable collects the final Hello World program, it is an int:
output = seq(hello, seq(space, world))

output =

5415635422699800391725693308419945869938047256733346713550460407095814114319569289794141598310221088923228113803592018583030904866616648743565156080354766258033679557467368102287883757372922292462388444344193832459294241211772759005779050565902544938820784809992232358898535748305157841941882294645670253116496913308504657721322832626892850043645997020747665515066716600292331134259311112482496040430434745069686188630377239466642921401009963995757022467209504867761343530249208583811705435730071633462308933895519148492626582397887441416187256057555255090301021135300528828921864634932238309287992585566695583871875173079793755657972457358361648901338160944754000551653766720698310341420752283578949816857373064991251470993101534298790120015991067351908598435249178378793540802171934140494304183843041304096491202311676946447702212935980368781632268520340743861243328221

(decimal)

Which outputs Hello World

For comparison, the variable h =

1203569047640653562261920316384804940787372518863418414334982600413

(decimal)

Which outputs H

This is a inefficient "Hello World", but illustrates how entire programs can be created by mathematical operations on Gödel numbers of basic sub-units. In Gödel numbering, a basic command can be thought of as a "program", and more complex programs can be thought of as "symbols" since there is no real distinction between symbol, program, or command; They are equally represented by single points on the number line.

Interpreters and Converters

Ruby interpreter

#!/usr/bin/env ruby
eval 'm=Hash.new(p=0);'+ARGF.read.gsub(/[^0-9]/,"").to_i.to_s(8).gsub(/./,
     '1' => 'p+=1;',
     '2' => 'p-=1;',
     '3' => 'm[p]+=1;',
     '4' => 'm[p]-=1;',
     '5' => 'putc m[p];',
     '6' => 'm[p]=STDIN.getbyte if !STDIN.eof;',
     '7' => '(',
     '0' => ')while((m[p]&=255)!=0);')

Ruby converter from brainfuck

#!/usr/bin/env ruby
puts ARGF.read.gsub(/.|\n/,'>'=>'1','<'=>'2','+'=>'3','-'=>'4','.'=>'5',','=>'6','['=>'7',']'=>'0').to_i(8).to_s

Bash converter and interpreter (using bff4)

#!/bin/bash
# Brainfoctal interpreter.
# REQUIREMENTS:
#  python3 to convert
#  bff4, http://mazonka.com/brainf/bff4.c to interpret,
#    $BFI should point to the compiled interpreter
# USAGE:
#  ./bf8 <bf8 Gödel number in dec|oct|hex|bin> <input data>
# EX.
#  ./bf8 0o6565 Hi
#  ./bf8 0xd75 Hi

BFI=./bff4
BF="]><+-.,["
BF8PY="""s=oct(int(\"$1\", 0))[2:]
for i,c in enumerate(\"$BF\"):s=s.replace(str(i),c)
print(s)"""
conv=$(python3 -c "$BF8PY");echo $conv
if [ -e $BFI ];then $BFI <<<$conv\!$2;echo;fi

Variants

Standard (bf8)

Described above

TinyBF variant (bf4)

TinyBF only has 4 commands, left-pad if needed, and convert to base 4:

tinyBF	bf4
=	0
>	1
+	2
\|	3

 hw = 4940483681439512375152791588159563144649591892023146755932736226550973701915040

Spoon variant (bf10)

Take the Spoon source code (binary), left-pad if needed, and interpret as a binary value.

Hello World in Brainfoctal, Spoon variant:

 hw = 92882107805187148442659988738423240956700204522415511965308556301926681873629017444630245917502249114582992255321462493556906145290

Example of mathematical operations on bf10

 bf4(hw) => "Hello, World!"
 bf4(hw/2) => "Hello, World"

Left-padding

Brainfoctal may require a NOP left padding to avoid issues with representing zero padded numerals in the various bases.

bf8 with ] as 0, no valid program can begin with a zero, so bf8 is safe from this issue. A previous revision had < as zero, thank you to User:Rdebath for suggesting the current numbering system which avoids this problem completely.

bf4 should mostly be safe, as 0 is equivalent to = which changes the direction, which is unlikely to be useful as they first command of a TinyBF program. If it does occur for some reason, the code should be left padded with 1010

bf10, Spoon, there are multiple commands that could result in the leftmost symbol being 0. If the leftmost character is 0, then prefix 1000 (increment followed by decrement) to avoid issues with zero padded code.

For any future extensions, all left-padding operations should only consist of the symbols 0 or 1, regardless of the base.

Conversions

These variants imply some basic conversion operators on Brainfoctal values:

bf8_to_bf4(n) => returns the equivalent bf4 code value for a bf8 program
bf4_to_bf8(n) => inverse of above
bf10_to_bf8(n)
bf8_to_bf10(n)

... and so on.

Computability: Unfortunately many valid Brainfoctal programs (i.e. some Integers) do not represent validly executing bf programs. Often because of mis-matched jumps, or range errors.

Hypothetical function: min_valid(n) => returns the smallest absolute value (in either +ve or -ve dir) to add to n in order to make it represent validly executing bf.

Another possible solution to this problem is to use bf / TinyBF / Spoon interpreters that do not barf on these errors but unambiguously and sensibly handle them somehow to produce deterministic results.

Alternatively, accept that exceptions are valid results from Brainfoctal execution. Certainly, not all Brainfoctal programs will produce useful or visible output anyway, or even terminate execution.

Polyglots

A Polyglot is a Gödel number that produces the same (or possibly other interesting) output when interpreted as different variants of Brainfoctal (or any other language's Gödel numbering system).

 1980162504590663524427895128832287108919003518751113534748489908152745653289288576638392714501426799307977736019325527189300780074184832951279861236626358272

Is a polyglot Truth-machine in Brainfoctal and simultaneously in Factor, which demonstrates this concept.

Quines

A Brainfoctal quine will be a integer that represents a bf program that prints out that integer.

Similar to Talk:Unary#A_quine_in_Unary, unfortunately that number does not translate directly into Brainfoctal as a Quine (even though it is a valid Brainfoctal program), and a similar method must be used to determine a different Quine number.

Brainfoctal Sub-languages

Deadf'shoctal

A Turing-complete, "extreme" code-golfing combination of Brainfoctal and Deadfish, in which is is frequently difficult to produce even trivial programs with byte counts less than the number of atoms in the known observable universe, ~10^82 (IANAL / YMMV, source: https://www.universetoday.com/36302/atoms-in-the-universe/)

Fortunately there is a compressed notation which allows Deadf'shoctal programs to be represented accurately and unambiguously, so they can be analysed in finite space / our universe without converting all matter to computronium, which would likely be prohibitively expensive.

Deadf'shoctal is standard Deadfish, with one extra command, b, which interprets the accumulator value as a Brainfoctal program and executes it.

Example: Hello World in Deadf'shoctal (compressed notation):

iisisiiiiis{i*54}s{i*1837}s{i*613412}s{i*383341247286}s{i*395233025718914908448622}s{i*864233217216978385839621542064993608838041819004}b

Which at 864233217216978385839621937298019328136292130232 bytes uncompressed, comes in well under the universe atoms byte count threshold.

256

Deadf'shoctal cannot represent the bf8 program 0x400 (256), which happens to be non-executable (decrement cell, followed by two unmatched close loops), so there is no real consequence to this limitation.

Code Golf Challenge: Produce the shortest possible Hello World program in Deadf'shoctal. The above example does not make use of d decrement operators to get more favourable squares in fewer characters. Other strategies that will likely have more effect:

use a series of shorter bf programs to produce each character of output so the source has many b characters.
pad the bf source so that the Brainfoctal value is better represented as a sequence of squares.

+b

Combination of the joke language + and Brainfoctal, which by adding just one command b makes + Turing complete. This is actually the most illustrative application of the Brainfoctal concept, taking an absolutely minimal language and enabling it to represent any possible bf program as data using the simplest form of data storage.

+b adds one extra command to the + command, b, which interprets the accumulator value as a Brainfoctal program and executes it.

+: Increment the accumulator
b: Interpret the accumulator value as a Brainfoctal program and execute it

Like Deadf'shoctal, +b code is likely to run into storage issues due to the physical size limits of our universe. Fortunately there is also a compressed notation:

 +{*<Brainfoctal code value>}b

We can calculate the storage size difference between a +b program and its equivalent Deadf'shoctal implementation to illustrate the code-golfing value of Deadf'shoctal.

 +{*228855768768422936408264393456423041692937029376710995071693817276469283765324982920591645725405}b

Which is the same Hello World as in the Deadf'shoctal example above. The +b version does exceed the universe atoms byte count threshold (~23 trillion times), while Deadf'shoctal does not. This clearly demonstrates the code golfing excellence of the latter by reducing the code down to 3.776 perquindecillion of its b+ size.

Task: Implement +'s parent, HQ9+, in +b?

Self-Confirming Self-interpreter in +b

 +{*x}b

Where x = self confirming +b interpreter in Brainfoctal

There should be some method to use the above structure to iterate through all integers to find x and test whether it correctly interprets itself.

Criteria:

f(f()) => "FOUND IT!"
f(<Hello World in +b>) => "Hello, World!"
f(<arbitrary +b code>) => correctly interprets arbitrary +b code

Unfortunately there probably exist any number of false positives, so the fitness test may need to be more sophisticated that simply looking for the "FOUND IT!" string output when given itself as input. (Beware of false negatives too! Theoretically there exists an otherwise perfectly valid +b interpreter that outputs "NOPE, THIS IS DEFINITELY NOT A +B INTERPRETER. KEEP GOING." when given itself as input.)

Given that bf interpreters in bf exist, x should also exist, right?

Happy hunting!

Tasks

Create a +b Self-confirming Self-interpreter False Positive which accepts input then returns "FOUND IT!" to illustrate the form of the task, and also so that it can be excluded from subsequent searches.
Arguably more helpful / honest: a version of the above which outputs "DIDN'T FIND IT!
How many bits can be stored in a Hydrogen atom anyway? This "atoms in the universe" threshold is a bit arbitrary.

Brainfoctal

Contents

Why?

History

Language overview

Example operations

Example Hello World generation

Interpreters and Converters

Ruby interpreter

Ruby converter from brainfuck

Bash converter and interpreter (using bff4)

Variants

Standard (bf8)

TinyBF variant (bf4)

Spoon variant (bf10)

Left-padding

Conversions

Polyglots

Quines

Brainfoctal Sub-languages

Deadf'shoctal

256

+b

Self-Confirming Self-interpreter in +b

Tasks

Navigation menu

Brainfoctal

Why?

History

Language overview

Example operations

Example Hello World generation

Interpreters and Converters

Ruby interpreter

Ruby converter from brainfuck

Bash converter and interpreter (using bff4)

Variants

Standard (bf8)

TinyBF variant (bf4)

Spoon variant (bf10)

Left-padding

Conversions

Polyglots

Quines

Brainfoctal Sub-languages

Deadf'shoctal

256

+b

Self-Confirming Self-interpreter in +b

Tasks

Navigation menu

Search