next up previous
Next: DIFERENT WAYS TO VIEW Up: CHURCH - TURING HYPOTHESIS Previous: Arguments For Church-Turing Thesis

Random-Access Machine

figure218

Th: A TM can simulate a RAM, provided that the elementary RAM instructions can themselves be simulated by a TM.

Proof: Use a multitape TM.
Tape 0: Memory of RAM. tex2html_wrap_inline479

Tape tex2html_wrap_inline481 : RAM registers.
Tape r+1: location counter.
Tape r+2: memory-address register.
LOAD tex2html_wrap_inline491
ADD tex2html_wrap_inline493


Sushil Prasad
Thu Jul 30 17:32:57 EDT 1998