Is the decision problem of compiling a program decidable?

96 Views Asked by At

Let C be a compiler, an abstract machine consisting of the following procedures:

  • Preprocessing
  • Syntactic analysis
  • Semantic analysis
  • Intermediate representation
  • Optimization
  • Code generation

that compiles a programming language P, that is Turing-complete by definition. The output generated by C is some low level Turing-complete language, for practical purposes the output is x86_64 or something like it.
Consider the decision problem D to be a problem that receives as an input a compiler C that compiles P, and a string S. D outputs 1 if C is able to finish and 0 otherwise.
My question then being, is D decidable?
Important notes:

  • The compiler is not more powerful than a Turing machine, but it is as powerful as one
  • The compiler works under the specification of P, not a subset of it like compilers in practice works
  • From more practical examples, imagine P as being C/C++, C#, Java, Python, etc.
1

There are 1 best solutions below

0
On BEST ANSWER

It depends on the target language, but in many cases the translation steps are defined as procedures which necessarily terminate.

That's certainly not the case for C++, since C++ template metaprogramming is Turing complete. That's apparently also true of Rust. Languages which include compile-time macros may well be Turing complete as well, depending on the details of the macro language, although it's also possible to define macro languages which are not Turing-complete. For example, C's macro expansion would be guaranteed to terminate if recursive #include were prohibited, and I'm pretty sure that even without that requirement, the macro expansion algorithm is decidable. (The classic "C preprocessor is Turing complete" argument also requires a make utility with the capability to invoke the preprocessor multiple times, which is not within the boundaries of "the C language".)

Perhaps the most important issue here is that there is no relationship whatsoever between the Turing-completeness of the compiler and the Turing-completeness of the program being compiled. In theory, at least, a program written in some programming language could be compiled into a Turing machine in a deterministic fashion; compiling the program doesn't involve evaluating it for any given input. Perhaps less usefully, we could write a Turing-complete compiler only capable of producing binaries which necessarily terminate (even though the compiler might never produce anything for a given input program).