Compiler that compiles to a Turing machine?

Question

I am interested in finding/writing a compiler that compiles a program written in a simple source language to a Turing machine (instead of assembly). Does anyone know if there is a good approach for writing such a compiler, or if there is a Turing machine compiler already out there (that would be ideal)? Of course it is possible to do this in theory; it's just that it's very challenging (for me at least) to work out the details in practice.

Answer 1

Laconic

This is the highest profile attempt I've heard of so far. It was announced on this paper by Adam Yedidia and Scott Aaronson: https://www.scottaaronson.com/busybeaver.pdf and on this blog post by Scott: https://scottaaronson.blog/?p=2725

• repo toplevel on Adam's GitHub: https://github.com/adamyedidia/parsimony

• Quick start PDF

• https://www.youtube.com/watch?v=Rt_SfOkk0YM video by Adam showing how to use is parsimony repo

• Compiler source under src/laconic/laconic_meta

• "Demo" programs under subdirectory src/laconic/laconic_files E.g. golbach.lac encodes a Turing machine that halts iff the Goldbach conjecture is false.

  Their Goldbach program compiled to a 5,372-state machine. NQL (see below) however has achieved a 27-state machine (not necessarily benchmarked on the same input algorithm), and smaller machines for a few other conjectures, which suggests that it can produce generally smaller machines.

• src/tm/tm2/tm2_files/goldbach.tm2 contains the Turing machine output for goldbach.lac. It contains lines such as:

  States: 4888
  
  data_0:
      a -> data_1; R; b
      b -> data_209_babababba; R; a
  
  data_1:
      a -> data_2; R; b
      b -> data_371_ababbabaa; R; a
  
  data_2:
      a -> data_3; R; b
      b -> data_390_ababaaaab; R; a
  
  cpu_return_pop_top_func_check_if_stack_empty_read_a:
      a -> HALT; L; a
      b -> cpu_return_pop_top_func_remove_H_read_; R; b
  

  where data_0, data_1 and so one are states, data_209_babababba, R means go right, L means go left and a/b.

  I don't know if this Turing machine format can be directly simulated by existing simulators.

Laconic language features

Data types:

• integer:

  int myInteger;
  

• list of integer: list

• list of list: list2

Variable assignment with = and built-in integer functions such as addition + and multipication *:

int x;
x = 1;
x = (a+b)*c

"Functions", though a better term for them would be "macros", since they have no scope, no return value, and just directly modify variables globally:

func addY(x, y) {
 x = x + y;
 return;
}

C-like if and while constructs, e.g.:

while (x < y) {x = x+1;}

The video also mentions the print statement for debug purposes:

print x;

Here's the full Goldbach program to give a better idea:

func zero(x) {
    x = 0;
    return;
}

func one(x) {
    x = 1;
    return;
}

func incr(x) {
    x = x + 1;
    return;
}

/* Computes x modulo y */
func modulus(x, y, out) {
    out = x;
    
    while (out >= y) {
        out = out - y;
    }
    
    return;
}

func assignXtoYminusX(x, y) {
    x = y - x;
    return;
}

/* Figures out if x is prime, and puts the output in y */
/* Does not modify x, modifies y */
func isPrime(x, h, y) {
    if (x == 1) {
        zero(y);
        return;
    }
    
    y = 2;
    
    while (x > y) {
        modulus(x, y, h);
    
        if (h == 0) {
            zero(y);
            return;
        }
        incr(y);
    }
    
    return;
}

int evenNumber;
int primeCounter;
int isThisOnePrime;
int foundSum;
int h;

evenNumber = 2;
one(foundSum);

while (foundSum) {
    zero(foundSum);
    evenNumber = evenNumber + 2;
    one(primeCounter);
    
    while (primeCounter < evenNumber) {    
        isPrime(primeCounter, h, isThisOnePrime);
        
        if (isThisOnePrime) {
            assignXtoYminusX(primeCounter, evenNumber);
            isPrime(primeCounter, h, isThisOnePrime);
            assignXtoYminusX(primeCounter, evenNumber);
            
            if (isThisOnePrime) {
                print evenNumber;
                print primeCounter;
                
                one(foundSum);
            }
        }
        
        incr(primeCounter);  
    }         
}

halt;

Not-Quite-Laconic (NQL)

https://github.com/sorear/metamath-turing-machines

This project proposes a Laconic-like language but with a different compilation technique that has led to smaller Turing machines in certain cases of interest, from the README:

Not-Quite-Laconic is a language and compiler for generating Turing machines with small state counts. It is directly inspired by Adam Yedidia's Laconic, and the language is similar, but the implementation is less so. Laconic and the programme of constructing small Turing machines to establish upper bounds on provable BB(k) values are discussed on Scott Aaronson's blog.

NQL uses a different compilation methodology based on register machines and constructing binary decision diagrams to compress large programs without an explicit call stack. It achieves "a few" times smaller state counts than Laconic for the range of programs relevant to the BB(k) problem; e.g. 1919 states for a ZF proof enumerator. On very small programs it cannot compete with hand-coding, and behavior on much larger programs is unknown; Laconic may regain the upper hand,

It appears that most of the newer research has moved from Laconic to NQL, suggesting that it is a superior implementation. E.g. most of the smallest machines listed at https://bbchallenge.org/story#what-is-known-about-bb are in NQL.

Here's their Goldbach program to give an idea:

proc zero(x) {
    x = 0;
}

proc one(x) {
    x = 1;
}

proc incr(x) {
    x = x + 1;
}

/* Computes x modulo y */
proc modulus(x, y, out) {
    out = x;

    while (out >= y) {
        out = out - y;
    }
}

proc assignXtoYminusX(x, y) {
    x = y - x;
}

/* Figures out if x is prime, and puts the output in y */
/* Does not modify x, modifies y */
proc isPrime(x, h, y) {
    if (x == 1) {
        zero(y);
        return;
    }

    y = 2;

    while (x > y) {
        modulus(x, y, h);

        if (h == 0) {
            zero(y);
            return;
        }
        incr(y);
    }
}

global evenNumber;
global primeCounter;
global isThisOnePrime;
global foundSum;
global h;

proc main() {
    evenNumber = 2;
    one(foundSum);

    while (0 < foundSum) {
        zero(foundSum);
        evenNumber = evenNumber + 2;
        one(primeCounter);

        while (primeCounter < evenNumber) {
            isPrime(primeCounter, h, isThisOnePrime);

            if (0 < isThisOnePrime) {
                assignXtoYminusX(primeCounter, evenNumber);
                isPrime(primeCounter, h, isThisOnePrime);
                assignXtoYminusX(primeCounter, evenNumber);

                if (0 < isThisOnePrime) {
                    /* print evenNumber;
                    print primeCounter; */

                    one(foundSum);
                }
            }

            incr(primeCounter);
        }
    }
    return;
}
```

Answer 2

It's my first approach. I also want to add functions and variables in future. https://github.com/kamosevoyan/TuringLanguage_compiler