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.

Naturopathy

If it has four legs, is it a cat? – Avigdor

What is persé? A desert? – Septal

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.

Launalaunce

Ahh. Can you give me an example of this "encoding" for a UTM? If one shows it for the simplest UTM, then it's applicable for all UTMs, I'm aware of: but this still requires one to show the simplest UTM also be working on my machine, right? – Naturopathy

There is something on wikipedia ( en.wikipedia.org/wiki/Universal_Turing_machine ), I would have to search the CS class notes to find more... – Bowlds

Basically you define what a TM is inside a TM, so you basically encode the state transitions some how (if symbol is x then do y) then the state transitions of the UTM are all about interpreting these state transitions and applying them to input data. – Launalaunce

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.

Warpath

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.

Huh

I understand that. Is there a problem sufficient enough, when solved, my machine becomes a UTM, is basically my question. – Naturopathy

@Pindatjuh: Yes, there is a problem that, when solved, is sufficient for a UTM: Being able to simulate any Turing machine -- That's the definition of a UTM. – Huh

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

Thorwald

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.

Bowlds

No I don't know that. What are NP problems, 3-sat, Hamiltonian? Do I really need to know those, before I can understand my question? – Naturopathy

Umm..no...but the NP class is defined as 'problems that can be solved on non-deterministic TM in polynomial time'. There is a very nice proof of showing that a certain problem ('tiling problem') is in NP. The proof goes this way: let's have a turing machine. Encode it in the tiles. If we solve the 'tiling problem', we can easily convert the result to the result, that the turing machine would produce. – Bowlds

Just a note: the 'tiling problem' is not an example of turing machine, as it is equivalent only to TM problems running in nondeterministic-polynomial time - but it is one of the ideas how to encode the turing machine. See e.g. here: cs.uml.edu/~wang/cs502/tiling.pdf – Bowlds

Another definition of NP is "problems where any proposed solution can be checked efficiently". Being able to solve a problem on a non-deterministic Turing machine in polynomial time is equivalent to being able to check a proposed solution to see if it works on a deterministic Turing machine (which is analogous to a real computer) in polynomial time (which I call "efficient" here). – Apothecium

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.

Septal

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)

Chaldron