All Turing-complete languages are brainfuck equivalents

From Esolang
Jump to navigation Jump to search

All Turing-complete languages are brainfuck equivalents is a family of esoteric programming languages and esoteric subsets first realized by User:PythonshellDebugwindow.

Requirements for inclusion

The only requirements for inclusion in this family are Turing-completeness and brainfuck equivalency, although the second implies (and actively enforces) the first. It is possible that all (or at least most) Turing-complete languages have at least one subset in this family.

Subset details

Each member subset must have exactly eight different "commands", no more, no less, one for each of brainfuck's. TrivialBrainfuckSubstitutions, simple translations of brainfuck, and the members of Category:Brainfuck equivalents all fit into this family. For example, Alphuck is a member:

Brainfuck Alphuck
+ a
- c
> e
< i
, j
. o
[ p
] s

Example members (languages and subsets)

Alphuck

Brainfuck Alphuck
+ a
- c
> e
< i
, j
. o
[ p
] s

A subset of browser JavaScript

Brainfuck This subset
+ if(!window.p) p=0; if(!window.m) m=[0]; m[p]++;
- if(!window.p) p=0; if(!window.m) m=[0]; m[p]--;
> if(!window.p) p=0; if(!window.m) m=[0]; p++; if(p==m.length) m.push(0);
< if(!window.p || !window.m) throw new Error("p < 0"); else p--;
, if(!window.p) p=0; if(!window.m) m=[0]; m[p]=(prompt()+"\0").charCodeAt(0);
. if(!window.p) p=0; if(!window.m) m=[0]; alert(String.fromCharCode(m[p]));
[ if(!window.p) p=0; if(!window.m) m[0]; while(m[p]) {
] }

A subset of x86 code

This makes some assumptions about the state of registers and the host environment. In particular, it assumes that ESI is initialized to the position of a tape, EDI is initialized to 0, and ESP has a valid stack. One can prepend each instruction with an initializer if necessary. It also assumes that the scope of each block of x86 assembly is somehow localized - this is why it's x86 code and not x86 assembly. The code is position-independent, so it remains a trivial substitution.

Brainfuck This subset
+ test edi, edi ; jnz next ; inc byte [esi] ; next:
- test edi, edi ; jnz next ; dec byte [esi] ; next:
> test edi, edi ; jnz next ; inc esi ; next:
< test edi, edi ; jnz next ; dec esi ; next:
, test edi, edi ; jnz nope ; xor eax, eax ; mov [esi], al ; mov al, 3 ; xor ebx, ebx ; mov ecx, esi ; xor edx, edx ; inc edx ; int 0x80 ; nope:
. test edi, edi ; jnz nope ; xor eax, eax ; mov al, 4 ; xor ebx, ebx ; inc ebx ; mov ecx, esi ; xor edx, edx ; inc edx ; int 0x80 ; nope:
[ test edi, edi ; jnz nope ; top: ; mov al, [esi] ; test al, al ; jz nope ; call yup ; yup: ; pop eax ; sub eax, yup - top ; push eax ; jmp yup2 ; nope: ; inc edi ; yup2:
] test edi, edi ; jnz nope ; ret ; nope: ; dec edi