URM computable indicating RAM computability

519 Views Asked by At

How can we show that every URM computable function is RAM computable?

I can see that that from Church's thesis, URM Computability iff p.r., but now sure how to get this claim above.

Taking the hint below:

We need to show that what S(), T(), and J() means in the two state machines above.

1

There are 1 best solutions below

1
On

David Marker's notes http://homepages.math.uic.edu/~marker/math502-03/mm6-9.pdf pp. 45-46 will give you the materials for this. Marker proves the direction RAM computability $\Rightarrow$ URM computability (Exercise 6.18); but the same materials prove the reverse direction (Exercise 6.19).