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.

  • 2
    $\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
    Dec 16 '15 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
    Dec 16 '15 at 18:14
  • $\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
    Dec 17 '15 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
    Dec 17 '15 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
    Dec 17 '15 at 18:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.