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.
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
#includewere 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 amakeutility 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).