Hacker News Reader

Comment by drx | Hacker News Reader

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.

I'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.

I 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?

In 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.

The 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.

I think he had in mind that the language is fixed, but not the compiler.

In 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.

Reply on news.ycombinator.com