Make Plan 9 Cat Turing Complete in as Few Bytes as Possible [closed]

Question

Your task is to modify the original Plan 9 cat tool for UNIX, in order to make it a fully turing complete language interpreter. You may make use of ANSI escape codes and the backspace character (\x08) to aid in this.

You must submit:

• A modified version of the Plan 9 cat tool
• A hexdump of the turing machine that can be run like so: cat turing_machine where turing_machine is the file you wrote.

Your score is the number of bytes you changed in the Plan 9 cat source code (where replacing a character counts as two bytes because you have to remove it and then replace it).

Here is the Plan 9 cat source code, taken from here.

#include <u.h>
#include <libc.h>

void
cat(int f, char *s)
{
    char buf[8192];
    long n;

    while((n=read(f, buf, (long)sizeof buf))>0)
        if(write(1, buf, n)!=n)
            sysfatal("write error copying %s: %r", s);
    if(n < 0)
        sysfatal("error reading %s: %r", s);
}

void
main(int argc, char *argv[])
{
    int f, i;

    argv0 = "cat";
    if(argc == 1)
        cat(0, "<stdin>");
    else for(i=1; i<argc; i++){
        f = open(argv[i], OREAD);
        if(f < 0)
            sysfatal("can't open %s: %r", argv[i]);
        else{
            cat(f, argv[i]);
            close(f);
        }
    }
    exits(0);
}

The headers in the above source are u.h and libc.h. Your code must conform to the C99 standard.

Answer 1

266 256 250 245 149 bytes (probably)

Thanks to @someone for suggesting using a cyclic tag system (originally I was using a modified version of Brainfuck).

Real computers aren't actually Turing-complete, because they have a finite amount of memory, whereas a Turing-machine has an infinite amount of memory. This is an implementation of a cyclic tag system with 9999 bytes of memory (although you could very easily change that), and with an initial word of 1 (I'm not entirely sure if cyclic tag systems with a fixed initial word are Turing-complete, but they probably are). The length of the program must be ≤8192, in this format:

00 (the first byte is ignored) 
01 01 02 00 (first rule: 001 (null character to mark end))
02 02 02 01 02 00 (second rule: 11101)
03 (marks end of program)

There is no I/O. The added code should be C99-compliant (provided the input code doesn't use more than 9999 bytes of memory at once), but I'm pretty sure you can't (portably) declare main as void in C99.

#include <u.h>
#include <libc.h>

void
cat(int f, char *s)
{
    char buf[8192],m[9999];
    long n;

    while((n=read(f, buf, (long)sizeof buf))>0){char m[9999],*M=m+9998,*s=m,*e=m+1,*i=buf;*m=2;m[1]=0;do{for(i++;*i;i++){if(*i>2)i=buf+1;if(*s>1){*e++=*i;if(e>M)e=s;}}if(++s>M)s=m;}while(*s);
        /*if(write(1, buf, n)!=n)
            sysfatal("write error copying %s: %r");*/}
    if(n < 0)
        sysfatal("error reading %s: %r", s);
}

void
main(int argc, char *argv[])
{
    int f, i;

    argv0 = "cat";
    if(argc == 1)
        cat(0, "<stdin>");
    else for(i=1; i<argc; i++){
        f = open(argv[i], OREAD);
        if(f < 0)
            sysfatal("can't open %s: %r", argv[i]);
        else{
            cat(f, argv[i]);
            close(f);
        }
    }
    exits(0);
}

Slightly de-golfed, and printing each step:

#include <u.h>
#include <libc.h>

void
cat(int f, char *s)
{
    char buf[8192];
    size_t n;

    while((n=read(f, buf, (long)sizeof buf))>0) {
        char mem[9999];
        *mem=2;mem[1]=0;
        char* mem_end = &mem[9998];
        char*start=mem,*end=mem+1,*i=buf;
        do {
            for (char* p = start; p < end; p++) {
                printf("%d",*p - 1);
            }
            printf("\n");
            for (i++;*i;i++) {
                if(*i>2)i = buf+1;
                if (*start > 1){
                    *end++=*i;
                    if (end > mem_end)
                        end = mem;
                }
            }
            if (++start>mem_end)start=mem;
        } while (*start);
        /*if(write(1, buf, n)!=n)
            sysfatal("write error copying %s: %r");*/
    }
    if(n < 0)
        sysfatal("error reading %s: %r", s);
}

void
main(int argc, char *argv[])
{
    int f, i;

    argv0 = "cat";
    if(argc == 1)
        cat(0, "<stdin>");
    else for(i=1; i<argc; i++){
        f = open(argv[i], OREAD);
        if(f < 0)
            sysfatal("can't open %s: %r", argv[i]);
        else{
            cat(f, argv[i]);
            close(f);
        }
    }
    exits(0);
}

The following Python script converts any cyclic tag system into code which is accepted by this program:

productions =   [[0,0,1],
                 [0],
                 [0,0],
                 [0,1,1,1]]
f = open("turing_machine","w")
f.write("\0") # First byte is ignored
for production in productions:
    for c in production:
        f.write(chr(c+1))
    f.write("\0")
f.write("\3")
f.close()

When you run the output of this program with the de-golfed version, you get:

1
001
01
1
0111
111
110
1000
0000111
000111
00111
0111
111
11001
10010
001000
01000
1000
0000
000
00
0