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