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?
$\begingroup$
$\endgroup$
5
-
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$– chiCommented Apr 18, 2019 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 BarrosCommented Apr 26, 2019 at 7:59
-
2$\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$– chiCommented Apr 26, 2019 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 BarrosCommented Apr 26, 2019 at 9:38
-
3$\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 left SECommented May 2, 2019 at 19:17
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
1
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.
answered Apr 17, 2019 at 19:59
-
$\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$– chiCommented Apr 18, 2019 at 10:47
$\begingroup$
$\endgroup$
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.