You'd have to include the source code of the compiler and build tools
used to compile the executable. Then the recipient could verify the
source code by compiling the compiler and using the compiled compiler to
compile the application program to find out whether the binary matches.
It probably wouldn't match due to system-specific differences, so the
image would need to include the build environment for the compiler...
soon we're at <http://bootstrappable.org/> :)
GNU Mes is an attempt to reduce this problem to its smallest compass. It has two parts: mes, a Scheme interpreter written in a tiny dialect of C, and mescc, a C compiler for that dialect written in mes. If either works, the other does. mescc is capable of compiling a patched version of tinycc, which can compile the gcc 2.95 toolchain, which can compile the last non-C++ release of gcc, which can compile the latest gcc. (I may not have all details right, but that's the idea.)