954,499 Members — Technology Publication meets Social Media
Username:
Password:
Lost login information?
Have something to say? Contribute New Article Reply to this Article

URM computes iff TM computes?!

Hi

I'm am trying to prove that a partial function is only computable by a Unlimited Register Machine iff it is computable by a standard TM. How should approach this proof. Does it have anything to do with reductions?

Thanks in advance

alireza1989
Newbie Poster
1 post since May 2010
Reputation Points: 10
Solved Threads: 0
 

Just show that you can simulate a TM on a URM. That means a URM can run anything a TM can run, because it can just pass the input through the TM.

Then show that you can simulate a URM with a TM. This shows the same thing in the other direction.

Rashakil Fol
Super Senior Demiposter
Team Colleague
2,658 posts since Jun 2005
Reputation Points: 1,135
Solved Threads: 177
 

This article has been dead for over three months

Post: Markdown Syntax: Formatting Help
You
View similar articles that have also been tagged: