Alex Rivera | Logout

Universal Turing Machine Problems

Asked 2010-01-20T12:10:05.260
9

If I have a machine, call it machine 1, that is able to solve a problem: it's just a machine, not per se a Turing machine. It can solve one specific problem. If this exact same problem can be solved on a Universal Turing Machine, then is my original machine, 1, a Universal Turing Machine too?

This does not hold for all problems, which is already ansered. Are there any problems which have this described property at all? If it is absolutely not true, then why?

Can someone give an example of a problem to be solved. If this problem is solved by my original machine, 1, definately makes this a Universal Turning Machine? Or does such a problem not exists? If it doesn't exists, why?

I'm very interested, but can't figure it out... Thanks.

Edit: made the question more clear.

turing-machines universal
Edit
Report

2 Answers

1

A universal turing machine can solve any code that any specific turing machine can solve.

So your universal turing machine (2) can solve the problem that your original turing machine (1) was designed to solve.

Your original turing machine (1) however can solve only that exact problem and can't solve any other problem (including the "problem" of being a universal turing machine).

So no, your original turing machine is not a universal turing machine according to your description. (It might be if the you define it to, but that's kind of cheating).

answered 2010-01-20T12:14:05.390
1

Proving the Turing completeness of a particular system is not trivial, unless you can easily show that it's equivalent/isomorphic to another system that is know to be Turing complete. So short answer: there is no simple test that you can put your machine through to check whether it is Turing complete. You have to analyze and show properties of the system as a whole.

If you want to learn more about this topic, read these articles about Turing completeness and computability theory.

answered 2010-04-03T04:01:40.283

Your Answer