17
$\begingroup$

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.

$\endgroup$
9
  • 3
    $\begingroup$ a great undergrad project. have not found this after also looking/ asking. have built one in ruby but its rough. see also a small c-like language TMs can simulate. try Computer Science Chat for more coaching. $\endgroup$
    – vzn
    Commented Dec 16, 2015 at 17:25
  • $\begingroup$ Expect the output of such a compiler to be quite large and not so efficient, compared to one could achieve by defining the TM directly. $\endgroup$
    – chi
    Commented Dec 16, 2015 at 18:14
  • 1
    $\begingroup$ @chi: why would that be? Ordinary compilers for register machines seem to perform quite well with respect to speed, and often can produce small code if needed. $\endgroup$
    – cody
    Commented Dec 17, 2015 at 17:46
  • $\begingroup$ One possible issue is that compiling to TMs might be highly dependent on the number of tapes and symbols, though 2 tapes + 3 symbols (including blank) might offer a good trade-off. $\endgroup$
    – cody
    Commented Dec 17, 2015 at 17:49
  • 1
    $\begingroup$ @chi: fair point. People are mostly interested in performance of TMs up to some constant factor though, so a little inefficiency might be forgiven. Size is more of a problem, but it's extremely difficult to write large and complex TMs by hand at any rate (most proofs either handwave the construction, or explicitly appeal to the Church-Turing thesis). $\endgroup$
    – cody
    Commented Dec 17, 2015 at 18:49

2 Answers 2

5
$\begingroup$

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

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;
}
```
$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.