The easiest simulation that comes to mind would be to represent any cell of an ordinary TM by a pair of cells of the RTM. The odd cells of the RTM correspond to the cells of the corresponding TM, whereas the even cells are merely of an auxiliary nature. Now you simulate:


TM action ----- simulator ----> RTM actions:

Reverse and move R -----------> R; R

Keep cell value and move R ---> R; L; R; R

Reverse and move L ------------> L; L

Keep cell value and move L ----> L; R; L; L


This simulation (Rob van Glabbeek) increase the performing time by a factor 4 however (at worst).


The best simulator uses the same idea, but in more complex and efficient way. Any cell of TM tape is represented by one (not 2) cell of RTM tape. Let simulate:

Reverse, move R, goto S -----------> R; goto simulate S

Keep cell, move R, goto S ----------> R; L; R; goto simulate corr(S)

...

if state S is represented by line:

S: [V0 A0 S0] [V1 A1 S1]

and interpreted (in Pascal notation) as:

If ReadValue=0

then begin Write(V0); Move(A0); goto(S0) end

else begin Write(V1); Move(A1); goto(S1) end;

The state corr(S) is defined as:

corr(S): [V1 A1 S1] [V0 A0 S0]

Note that corr(corr(S)) = S