Given a programming language A unknown to be Turing Complete, if one can create a compiler for a TC programming language B using A does this imply that A is itself Turing Complete? If so, what is the formal thinking behind the idea?

  • 1
    $\begingroup$ The question is ambiguous. Is the compiler translating B programs into A programs? Or is the compiler translating B programs into C (?) programs, where the compiler is written using language A? That is: is A the target language of the compiler, or the language the compiler is written in? $\endgroup$ – chi Apr 18 at 10:44
  • $\begingroup$ @chi, the compiler is written using language A but I do not know if A is turing complete or not. $\endgroup$ – Vinícius Barros Apr 26 at 7:59
  • 1
    $\begingroup$ You need to be more clear. A compiler is something written in language X which translates programs in language Y to programs in language Z. There are three languages involved here, but you pretend there are only two, making the question ambiguous. $\endgroup$ – chi Apr 26 at 8:25
  • $\begingroup$ I do not think it is ambiguous. The question only cites two languages: A and B. I do not know where you're getting the third language from. However, to try and make things clearer: compiler is built using language A; compiler compiles code written in language B. B is Turing Complete. Does this imply A is also Turing Complete? Anyways, @Derek Elkins answered it in a clear way IMO. Thank you. $\endgroup$ – Vinícius Barros Apr 26 at 9:38
  • 2
    $\begingroup$ @ViníciusBarros The third language is the language B is being compiled to. That might be machine code, but machine code is a programming language. I could, for example, use Haskell to write a compiler for Scheme that produces C code. $\endgroup$ – Derek Elkins May 2 at 19:17

No. It's usually relatively easy to compile a language (Turing complete or otherwise). At a very simplistic level, a compiler flattens an abstract syntax tree into a list of instructions. This can usually be done by a simple structural induction over the syntax tree. Optimization passes often do data flow or control flow analyses that would be harder to represent as a simple structural induction.

You can make a practical demonstration by programming a compiler for the untyped lambda calculus into some simple Turing complete stack-based machine in Agda or some other non-Turing complete language.

However, just as an extreme example, the "compiler" could be the identity function. If you meant that you could write a compiler for any Turing complete language, then that wouldn't be possible simply because the semantics of the language may require executing arbitrary code (e.g. Common Lisp macros) to elaborate the syntax or otherwise to produce a correct compiler.

  • $\begingroup$ Maybe you should add that this answer assumes that A is only the language use to code the compiler for B. The OP might have instead wanted A to be the target language of the compiler (the question is ambiguous, IMO). $\endgroup$ – chi Apr 18 at 10:47

I don't think that's the case.

Looks to me that you are questioning if the Turing-completeness is specification-wise or implementation-wise. And the answer is in the specification-wise.

If I have a language A, I've specified its semantics - and it is not Turing complete by definition (say, CSS for example). This means that whatever compiler you write will have to follow that specification regardless of what language your compiler's backend will spit out.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.