Transform any program into a semantically equivalent one

Question

I recently found this theorem here, (at the bottom):

Any program can be transformed into a semantically equivalent program of one procedure containing one switch statement inside a while loop.

The Article went on to say :

A corollary to this theorem is that any program can be rewritten into a program consisting of a single recursive function containing only conditional statements

My questions are, are both these theorems applicable today ? Does similarly transforming a program reap any benefits ? I mean to say, is such a code optimized ? (Although recursion calls are slower, I know)

I read, from here, that switch-cases are almost always faster when optimized by the compiler. Does that make a difference. ?

PS: I'm trying to get some idea about compiler optimizations from here

And I've added the c tag as that's the only language I've seen optimized.

Answer 1

Its true. A Turing machine is essentially a switch statement on symbols that repeats forever, so its based pretty directly on Turing-machines-compute everything. A switch statement is just a bunch of conditionals, so you can clearly write such a program as a loop with just conditionals. Once you have that, making the loop from recursion is pretty easy although you may have to pass a lot of state variables as parameters if your language doesn't have true lexical scoping.

There's little reason to do any of this in practice. Such programs generally operate more slowly than the originals, and may take more space. So why would you possibly slow your program down, and/or make its load image bigger?

The only place this makes sense is if you intend to obfuscate the code. This kind of technique is often used as "control flow obfuscation".

Answer 2

This is basically what happens when a compiler translates a program into machine code. The machine code runs on a processor, which executes instructions one-by-one in a loop. The complex structure of the program has become part of the data in memory.

Answer 3

Recursive loops through a switch statement can be used to create a rudimentary virtual machine. If your virtual machine is Turing complete then, in theory, any program could be rewritten to work on this machine.

int opcode[] {
   PUSH,
   ADD
   ....
};

while (true) {
    switch (*opcode++) {
    case PUSH:
        *stack++ = <var>;
        break;
    case ADD:
        stack[-1] += stack[0];
        --stack;
        break;
     ....
    }
}

Of course writing a compiler for this virtual machine would be another matter. :-)