Member Avatar for alireza1989

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

  • 2 Contributors
  • 1 Reply
  • 90 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Rashakil Fol
Member Avatar for Rashakil Fol

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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.