[seanewest]

Ok, but is finding X given Y tractable?

To me, it seems like compiling is translation of source (usually higher level source to lower level source), whereas simulation is more like translation of behavior.

Edit: and the ability to translate behavior does not seem to imply the ability to translate source

[Solarsail]

Couldn't you translate source given the ability to translate behaviour? If some behaviour in language X can be simulated by a state machine in Y, then you could just emit said state machine as the translation of the behaviour, give its output to the next state machine, etc. And gradually build up the behaviour of a program in X, but using a bunch of generated code in Y instead of just an interpreter. In other terms, if an interpreter for / simulation of X may be expressed in Y, then for each bytecode / AST node in X you could just inline the bytecode handling you would use in Y into the compiled output.

[seanewest]

I think thats a very clever algorithm.

But I think your first articulation amounts to converting a turing machine to a huge generated state machine, which would be impossible. The behavior of the X program given one input could be modeled as a sequence of states if it terminates. But the process of generation that you described would have to be repeated for all possible inputs into the simulated X program, which would be impossible.

Maybe a single "behavior" could be modeled by a state machine, but it would also seem impossible to me to decompose a program into individual units of behavior.

But as for bytecode -- one could always compile the X code into bytecode, and then decompile that bytecode into Y code. If you can always find a common bytecode language for two languages X and Y, then I think that would be a generic algorithm for X->Y.

Edit: I guess that common bytecode could just be in a language that describes a turing machine.