9 ms·
The compiler isn't part of the input. You could get code that was compiled by a compiler not available to you. When the compiler is part of the input, then yes
by drx 15y ago
The compiler isn't part of the input. You could get code that was compiled by a compiler not available to you.
When the compiler is part of the input, then yes, the problem is decidable.
- shasta 15y agoI'm still doubtful. I think you're trying to invoke Rice's theorem here, but I don't think it really applies. Compilers don't apply arbitrary transformations that preserve behavior - they only employ transformations that are understood to preserve behavior.
- demallien 15y agoI don't think it is decidable even when you have the compiler available to you - what happens if I decide to insert a bunch of assembly code in my gcc-compiled program using the gcc embedded assembly extensions? How do I decide that a particular sequence of generated op-codes is actually impossible from pure C code, and hence must have been assembly in the original program?
- peti 15y agoIn that case, the GCC extension is part of the input language (in a broader sense). Still, your example clearly shows the difficulties involved in practice.
- nandemo 15y agoThe problem only makes sense if the compiler is fixed. Otherwise, it's trivial: for any input x I can say the source code is x. It's source code written in a programming language called MachineLanguage. The compiler is called cat.
- shasta 15y agoI think he had in mind that the language is fixed, but not the compiler.
- nandemo 15y agoIn this context, "programming language" and compiler are really the same thing: a mapping from source code to object code. In any case, the problem with your original argument is not the choice of compiler, it's that your algorithm migh not halt, as explained by kenjackson.