HGFTSNOA/Turing-Completeness proof
Jump to navigation
Jump to search
HGFTSNOA is able to interpret a Turing-complete variation of brainfuck, and is thus itself Turing-complete.
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 eight-bit 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"));
}