Brainwang

Brainwang is another simple variant of the Wang B-machine (or possibly brainfuck).

The language has been given a syntax very similar to brainfuck to highlight that the only unusual aspect is the branching.

Like other Turning machine variants it's primary storage consists of a tape where each cell on that tape may have one of a finite number of states (usually 256). Valid data cells only exist to the 'right' of the starting position.

All commands can be given an argument (an octal number N) that alters it's operation.

Command	Action without argument.	Action with argument.
>	Move the pointer to the right	Move the pointer to the right by N cells.
<	Move the pointer to the left	Move the pointer to the left by N cells.
+	Increment the memory cell under the pointer	Increment the memory cell under the pointer by N
-	Decrement the memory cell under the pointer	Decrement the memory cell under the pointer By N
.	Output the character signified by the cell at the pointer	Output the character signified by the value N
,	Input a character and store it in the cell at the pointer, On EOF leave cell unchanged.	Input a character and store it in the cell at the pointer, On EOF store N
?	Execute the next instruction only if the cell under the pointer is 0	Execute the next instruction only if the cell under the pointer is N
|	Exit the program immediately	Jump to the | with the matching argument N

In addition comments must be enclosed in { ... } brackets (which may be nested) and all other non-whitespace characters are not legal.

Examples

The argument available on the commands means that many of the most laborious parts of a Turing machine are very simple.

Hello, World!

110.145.154.154.157.40.127.157.162.154.144.41.12.

Computational Class

It's easy to show Turing completeness by conversion of brainfuck. Where {N} and {M} are unique numbers for each brainfuck loop.

However, it seems that the fact that the | command works in both directions (unlike the traditional GOTO) means that the language is NOT Turing complete without an instruction to unconditionally skip the next instruction (in this case the 1? item). Whereas with a traditional branch to a label that doesn't change the flow, any two of "branch equal", "branch not-equal" and "branch unconditionally" are sufficient.

Brainfuck	Brainwang
> < + -	> < + -
[	?{N}|
]	?{M}|{N}| 1? {M}|

Implementation

As a translation to C in C.

#include <stdio.h>
#include <string.h>

char * bf = "+-><.,?";
char * cc[] = {
    "++*p;",
    "--*p;",
    "p++;",
    "p--;",
    "putchar(*p);",
    "{int ch=getchar(); if(ch!=EOF) *p=ch;}",
    "if (*p==0)"
};

char * ccarg[] = {
    "*p += 0%lo;\n",
    "*p -= 0%lo;\n",
    "p += 0%lo;\n",
    "p -= 0%lo;\n",
    "putchar(0%lo);\n",
    "{int ch=getchar(); if(ch!=EOF) *p=ch else *p=0%lo;}\n",
    "if (*p==0%lo)\n"
};

int main(int argc, char ** argv) {
    char * s;
    int c, comment = 0, ln = 1, col=0;
    long v = -1, nv = -1;
    FILE * fd = argc>1?fopen(argv[1],"r"):stdin;

    puts(      "#include <stdio.h>"
    "\n"       "#include <stdlib.h>"
    "\n"       "#define S 02000"
    "\n"       "unsigned char tape[S*S+S];"
    "\n"       "int main(void){"
    "\n"       "register unsigned char * p = tape+S;"
    "\n"       "setbuf(stdout,0);");

    while((c=getc(fd)) != EOF) {
        if (c == '\n') {ln++; col=0;} else col++;
        if (c == '{') comment++;
        if (comment) {
            if (c == '}') comment--;
            continue;
        }

        if ((s = strchr(bf, c))) {
            if (v>=0)
                printf(ccarg[s-bf], v);
            else
                puts(cc[s-bf]);
        } else if (c == '|') {
            if (v>=0) {
                printf(        "#ifndef F0%lo"
                "\n"   "goto v0%lof;"
                "\n"   "v0%lob:;"
                "\n"   "#define F0%lo"
                "\n"   "#else"
                "\n"   "goto v0%lob;"
                "\n"   "v0%lof:;"
                "\n"   "#endif"
                "\n",  v, v, v, v, v, v);
            } else
                puts("exit(1);\n");
        } else if (c >= '0' && c < '0'+010) {
            if (v<0) v=0;
            nv = v*010+c-'0';
        } else if (c == ' ' || c == '\t' || c == '_')
            nv = v;
        else if (c != ' ' && c != '\t' && c != '\n') {
            printf("#error Illegal character at (%d:%d)\n", ln, col);
        }

        v=nv; nv= -1;
    }

    puts("; return 0;}");
    return 0;
}