HGFTSNOA/TuringCompleteness proof
Jump to navigation
Jump to search
HGFTSNOA is able to interpret a Turingcomplete variation of brainfuck, and is thus itself Turingcomplete.
HGF
HGF is a version of brainfuck with no input. The conversion table is as follows:
Brainfuck  HGF 

+ 
1

 
2

< 
3

> 
4

. 
5

[ 
T

] 
t

Note that the 5
command outputs the current cell as a number rather than an ASCII character.
HGFTSNOA implementation
The following is an implementation of HGF in HGFTSNOA. It uses wrapping eightbit cells, and its tape is unbounded in both directions. The string on the second line contains the program to be executed; the current program (converted from this Code Golf answer) prints the ASCII values of the string Hello, World!.
T tttttt TTTTT "241444144222T1111111111T41111114111413332t231t4141545242255424254T4533t4T14t3354115" tttttt TTTTT t tttttt 0 "000" 0 TT t TTTTT tttttt ttttttt tttttttt ttttttttt T tttttttttt TTTTT tttttt TTTT ttttttt TTT tttttttttt TTTTT "" TTT 0 TTTTTT TTTT "" TTTTTT TTT tttttttttt TTTTT "1" tttttttt TTTTT tt tttttttt ttttttttt TTTTTT TTT tttttttttt TTTTT "2" tttttttt TTTTT ttt tttttttt ttttttttt TTTTTT TTT tttttttttt TTTTT "3" ttttttttt TTTTT ttttttttt TTTTTTTT 3 TTT ttttttttt TTTTT 3 tttttttt TTTTT "000" TTTTTTTT tttttttt ttttttttt TTTTT 0 TTTTTT TTTTTT TTT tttttttttt TTTTT "4" ttttttttt TTTTT ttttttttt TTTTTTTT 3 TTT tttttttt TTTT ttttttttt TTTTT "" tttttttt TTTTT tttttttt TTTTTTTT "000" TTTTTT TTTTTT TTT tttttttttt TTTTT "5" ttttt tttttttt ttttttttt TTTTTT TTT tttttttttt TTTTT "T" TTT 0 TTTTT ttttt tttttttt ttttttttt ttttttt TTTTT tttttttttttt tttttt ttttttt 1 "T" "t" 0 TTTTTT TTTTTT TTT tttttttttt TTTTT "t" TTT ttttt tttttttt ttttttttt ttttttt TTTTT tttttttttttt tttttt ttttttt 1 "t" "T" 0 TTTTTT TTTTTT TTTT t tttttt ttttttt TTTTTTTT 1 tttttttt ttttttttt TT tt TTTTT tttttt ttttttt T tttttttt TTTTT tttttt TTTT ttttttt ttttttttt TTTTT ttttttt TTTTTTTT 1 ttttttttt TTTTT tttttt TTTT ttttttttt tttttttttt TTTTT ttttttt TTTTTTTT 2 tttttttttt TTTTT tttttt TTTT tttttttttt ttttttttttt TTTTT tttttttt TTTTTTTT ttttttttt TTTTTTTT tttttttttt ttttttttttt TTTTT 1 TTTTTTTT ttttttttttt TTT ttttttttttt TTTTTTTT 256 ttttttttttt TTTTT "" TTTTTTTT ttttttttttt tttttttt TTTTT ttttttttttt TTTT 0 ttttttttt TTTTT ttttttttttt TTTT 1 tttttttttt TTTTT ttttttttttt TTTT 2 ttttttttttt TTTTT tttttttt TTT ttttttttt ttttttttttt TTTTT ttttttttttt TTTTTTTT ttttttttt TTT tttttttttt ttttttttttt TTTTT ttttttttttt TTTTTTTT tttttttttt TTTTTTT ttttttttttt TTTTT "0" TTTTTTTT ttttttttttt TTTTTT TTTTTTT ttttttttttt TTTTT "00" TTTTTTTT ttttttttttt TTTTTT TTTTTTT ttttttttttt TTTTT "000" TTTTTT tttttt TTTTT tttt tttttt 0 ttttttt ttttttttttt TTTT 0 tttttt TTTTT tttt tttttt 0 ttttttt TTTTTTTT 1 ttttttttttt TTTT 1 tttttt TTTTT tttt tttttt 0 ttttttt TTTTTTTT 2 ttttttttttt TTTT 2 TTT 0 TTTTTT TTTT tttttt TT ttt TTTTT tttttt ttttttt T tttttttt TTTTT tttttt TTTT ttttttt ttttttttt TTTTT ttttttt TTTTTTTT 1 ttttttttt TTTTT tttttt TTTT ttttttttt tttttttttt TTTTT ttttttt TTTTTTTT 2 tttttttttt TTTTT tttttt TTTT tttttttttt ttttttttttt TTTTT tttttttt TTTTTTTT ttttttttt TTTTTTTT tttttttttt ttttttttttt TTTTT 1 TTTTTTTT ttttttttttt TTT ttttttttttt TTTTTTTT 1 ttttttttttt TTTTT "" TTTTTTTT ttttttttttt tttttttt TTTTT ttttttttttt TTTT 0 ttttttttt TTTTT ttttttttttt TTTT 1 tttttttttt TTTTT ttttttttttt TTTT 2 ttttttttttt TTTTT tttttttt TTT ttttttttt ttttttttttt TTTTT ttttttttttt TTTTTTTT ttttttttt TTT tttttttttt ttttttttttt TTTTT ttttttttttt TTTTTTTT tttttttttt TTTTTTT ttttttttttt TTTTT "0" TTTTTTTT ttttttttttt TTTTTT TTTTTTT ttttttttttt TTTTT "00" TTTTTTTT ttttttttttt TTTTTT TTTTTTT ttttttttttt TTTTT "255" TTTTTT tttttt TTTTT tttt tttttt 0 ttttttt ttttttttttt TTTT 0 tttttt TTTTT tttt tttttt 0 ttttttt TTTTTTTT 1 ttttttttttt TTTT 1 tttttt TTTTT tttt tttttt 0 ttttttt TTTTTTTT 2 ttttttttttt TTTT 2 TTT 0 TTTTTT TTTT tttttt TT tttt TTTTT tttttt ttttttt tttttttt ttttttttt T TTT tttttt TTTT ttttttt TTT ttttttt TTTTT tttttttt tttttttttt TTTTT ttttttttt TTTTTTT tttttttttt TTTTT tttttt TTTT ttttttt TTTTTT TTTT tttttttttt TTTTTTTT tttt tttttt ttttttt TTTTTTTT 1 tttttttt ttttttttt TTTTTTT TTTT "" TTTTTT TT ttttt TTTTT tttttt ttttttt T tttttttt TTTTT tttttt TTTT ttttttt ttttttttt TTTTT ttttttt TTTTTTTT 1 ttttttttt TTTTT tttttt TTTT ttttttttt tttttttttt TTTTT ttttttt TTTTTTTT 2 tttttttttt TTTTT tttttt TTTT tttttttttt tttttttt TTTTT tttttttt TTTTTTTT ttttttttt TTTTTTTT tttttttttt TTT 0 TTTTTT TTTT 0 TTTTTTTT tttttttt TT tttttttttttt TTTTT tttttt ttttttt tttttttt ttttttttt tttttttttt ttttttttttt T TTT tttttt TTTT ttttttt TTTTT ttttttttt ttttttttttt TTTTT ttttttttttt TTTTTTTT 1 TTTTTTT TTT tttttt TTTT ttttttt TTTTT tttttttttt ttttttttttt TTTTT ttttttttttt TTTTTTTT 1 TTT ttttttttttt TTTTT 0 TTT 0 TTTTTT TTTT ttttttt TTTTTT TTTTTTT TTT tttttt TTTT ttttttt TTTTT "" TTT tttttttt TTTTT 1 tttttt TTTTT " T" TTTTTTT tttttt TTTTT " t" TTTTTT tttttt TTTTT "TT" TTTT 3 TTTTTTTT tttttt tttttt TTTTT "TTTTTT" TTTT 3 TTTTTTTT tttttt tttttt TTTTT "TTT" TTTT 0 TTTTTTTT tttttt tttttt TTTTT "TTT" TTTT 1 TTTTTTTT tttttt tttttt TTTTT "TTTT" TTTT 1 TTTTTTTT " " TTTTTTTT tttttt tttttt TTTTT "T" TTTT 4 TTTTTTTT tttttt tttttt TTTTT "TTTTTTTT" TTTT 1 TTTTTTTT tttttt tttttt TTTTT "TT" TTTT 3 TTTTTTTT " " TTTTTTTT tttttt tttttt TTTTT "TTT" TTTT 0 TTTTTTTT tttttt tttttt TTTTT "TT" TTTT 3 TTTTTTTT tttttt tttttt 42 TTTT 42 TTTTTT TTTTTT TTTTTT TTTT tttttttttttt tttttt ttttttt TTTTTTTT tttttttt tttttttt ttttttttt tttttttttt ttttttttttt TT
Conversion script
The following JavaScript program functions as a converter from brainfuck to HGF.
const program = ">+>>>+>>[++++++++++[>++++++>+++>+<<<]<+]>+>+.>.>..>>.>[>.<<]>[+>]<<.>++."; if(program.indexOf(",") > 1) { throw new Error("Input is not supported"); } else { console.log(program.replace(/[^<>.\[\]+]/g, "") .replace(/\+/g, "1") .replace(//g, "2") .replace(/</g, "3") .replace(/>/g, "4") .replace(/\./g, "5") .replace(/\[/g, "T") .replace(/\]/g, "t")); }