Last active
May 7, 2023 19:49
-
-
Save nst/0da460d9354fb591ce2255c778d6e680 to your computer and use it in GitHub Desktop.
A tiny Turing machine for 2-symbols Busy Beavers. No variable for state. Program is kept on input string.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// Tiny Turing machine in C | |
// for 2-symbols Busy Beavers | |
// Nicolas Seriot, 2023-05-07 | |
#include <stdlib.h> | |
#include <stdio.h> | |
#define TAPE_LEN 50000 | |
#define MAX_COUNT 100000000 | |
int runMachine(_Bool *t, char *p) { | |
int h = TAPE_LEN/2; | |
int i = 0; // instruction pointer | |
int c = 0; // counter | |
while (++c) { | |
t[h] = p[i]-'0'; // write tape | |
h+=p[i+1]=='R'?1:-1; // move head | |
if(p[i+2]=='H')break; // halt if needed | |
if(h==0||h==TAPE_LEN-1){return -1;} // out of tape | |
if(c==MAX_COUNT){return -2;} // max count reached | |
i = 8*(p[i+2]-'A')+4*t[h]; // set ip for next state | |
} | |
return c; | |
} | |
int main(int argc, const char * argv[]) { | |
char *program = "1LB 1RC 1LC 1LB 1LD 0RE 1RA 1RD 1LH 0RA"; | |
int64_t sigma = 0; | |
_Bool tape[TAPE_LEN] = {0}; | |
printf("* Tiny Turing Machine *\n"); | |
printf("Program: %s\n", program); | |
int c = runMachine(tape, program); | |
for (int i = 0; i < TAPE_LEN; i++) {sigma += tape[i];} | |
printf("S = %d, Sigma = %llu\n", c, sigma); | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment