Simple example, an assembly language instruction changes a memory address to a new value, mov [eax], $FFFFFFFF where eax contains the address where the $FFFFFFFF should go.

But now your virtual machine intercepts that instruction before it executes.

Before it stores the value to the address, it saves a copy of what the address was BEFORE the mov/store -- in OTHER MEMORY (as a stack data structure, since this could occur multiple times for individual memory locations...).

If/when eax changed, that would also have to be stored in OTHER MEMORY...

To reverse it then, we restore eax if it changed, then look at the memory location referenced, and restore the previous value (from the stack in other memory that we buffered it in).

With this approach a virtual machine can be created that can go back (rewind) as many instructions as you have memory for.

A machine like this also must buffer the state of things that a program interacts with, such as files and sockets, and be able to restore previous states of those in steps.

It's a bit complex... but it can be done in software, and software alone... but again, you couldn't reverse a program that had run infinitely long, you could only reverse for as many steps as fit into the other memory area that you buffered previous states in...

Also, drawback: It would be much slower than a regular virtual machine...

But it could be done...