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

>>13
it's nice that you mentioned halting problems because one of the ideas behind this machine is that it will always halt, regardless of program and data. also, every program is a valid program.

anyway, we're arguing about semantics of FSMs, Turing machines and pushdown automata instead of trying to find the answer to the topic's question: what would be the best way of emulating such thing if right now I'm more concerned with the code being easy to read (and understand, obviously) than with performance?