[grav1tas]

It depends on what you want from decompilation. Decompilation by its basic nature is just as decideable as compilation is. It's a translation from one language to another in addition to semantics-preserving translations. Now what a lot of people seem to want from a decompiler that makes them intractable is a guarantee that the output source will look just like the source used to compile the source program for the decompiler.

Program1 -> Compiler -> BinProg1 (compilation)

BinProg1 -> Decompiler -> Program2 (decompilation)

Even if the source language of the Compiler and the target language of the decompiler are the same, you're usually still screwed because the compiler is going to manipulate your program to optimize it or fit it onto your target architecture. The result is going to be a program that looks way more general case than your original program.

Is this undecideable? No way.

[shasta]

We typically reserve the term "undecidable" for the case where there is a mathematical function we are interested in, but it isn't computable by any algorithm. Inverting a many-to-one function is just impossible.