Universal Turing Machine Problems

Question

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.

Answer 1

The point of the Universal Turning Machine (UTM) is that for any Turing Machine (TM) you could take that TM and create an encoding for it that describes the operation of the TM and have that encoding run on another TM.

The UTM is a TM which has an definition sufficiently powerful such that any other TM definition could be rewritten in it.

Think of the UTM as an interpreter. The TM is a specific task.

Unless the TM is also in the class of interpreters then it is not a UTM as well. (Because a UTM is also a specifically tasked TM).

So to answer your second question: if you can show that the UTM and TM are equivalent then you have shown that TM is also a UTM. To do this you need to be able to show how an encoded program for the UTM can be changed into an equivalent program for the TM.

Answer 2

A Universal Turing Machine can solve any of a huge class of problems.

If your machine(1) can solve 1+1, that doesn't mean it can solve any of the huge class. So it may not be a Universal Turing Machine.

Answer 3

The logicians differentiate between "sufficient" and "neccessary" conditions. Take, for example, the sentence

The sky is blue.

(let's just assume that's always true). What you know now is this:

When you look at the sky, you see the color blue.

What you don't know is this:

When you see the color blue, you're looking at the sky.

-- you might as well be looking at your neighbour's car.

In logical terms, the color blue is neccessary for the sky, but it's not sufficient.

The same is true for your case: Machine (1) does solve your problem, so it's indeed a solvable problem. Hence, being able to solve the problem is a neccessary condition for a UTM, but not a sufficient one, because a UTM must be able to solve any problem (that's solvable at all), not just this single one.

Answer 4

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).

Answer 5

Can someone give an example of a problem to be solved.

Sure: Given encoded turning machine and data, what is the result :) If your machine can solve this problem, it is surely UTM.

Do you know the line of reasoning why those different problems are in NP? Like 'can i solve the 3-sat problem when I have a machine that solves the Hamiltonian problem?' You can surely use the same to answer your question.

Answer 6

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.

Answer 7

Imagine a UTM as if how would you proceed if you have to write a code(High level) for simulating the turing machine.You will require the following: 1.Array to hold the input symbols and the stuff that yiu would do on it. 2.An array(possible 2-d) to hold the transition function that you will prompt the user. 3.An algorithm that read user's inputs of transition functions and simulates it on array 1. 4.Few variables that your program will need to track its own state.

If you think in this way,if you end up getting a perfectly working code you end up with a perfect UTM. However the catch is no matter how efficiently you code you can't stop the user from entering transition functions that can cause your code to run forever.So there will be certain problems for which UTM will fail,and then we say that for those problems we can't develop a membership testing machine.(though notice a membership verification machine is always possible)