Writing an emulator for a slightly unusual abstract FSM

what would be a relatively hassle-free way of writing an elegant, intuitive code that emulates a finite state machine (no jumps or conditionals) with a self-modifying instruction set (or maybe just two instruction sets: one for modifying data, other for modifying the first instruction set)? I don't care about performance right now (I doubt it will get to the stage when I need to care about that but if it does, some fuckery with C function pointers will be inevitable; right now I care about readability and being able to prototype quickly) so functional is OK but I'm thinking of instructions having four-bit length and I'm not sure how good purefuncs are at handling that

>>25

every instruction must be a bijection so that given a program and its output, it's trivial to create a program which calculates the initial input

Cannot be done like this. 2+x=4 can be uniquely solved, but y+x=4 cannot be. Even AND, OR, and XOR cannot be uniquely mapped to their original inputs based only on an output. Just thinking about it now, I'm don't see how any binary function can avoid information loss without preserving one of the inputs, but that would defeat the purpose of being reversible.

if this ever reaches production (>imblyign), each instruction should take equal amount of time to execute

That's a waste of time. A naive implementation of multiplication (the one your processor uses, not fancy shit in bignum libraries) is O(n²), while addition is O(n), where n is the number of bits. Addition (or any other simpler instruction, such as logical operations) is going to have to stall 240 operations to have the same operation as multiplication on a 16 bit number.

0x012 might mean 'add 0x12' in one step of execution and 'xor 0x12' in another.

Did you mean "self-modifying instruction set" literally, as in, the instructions that opcodes map to are changed? Why not just change the program itself? Well, if that's what you want, there's this:
int add = 0, sub = 1, ..., swap_op = 15;
eval (int opcode, int param, int param2) {
if(opcode == add) ...;
else if(opcode == sub) ...;
else if(opcode == swap_op) int a = param; param = param2; param2 = a;
}
Such that eval (15, 0, 1) changes the meaning of opcodes.