Universal Turing Machine Problems

views:

375

answers:

+8 Q:

Universal Turing Machine Problems

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.

+1 A:

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

Joachim Sauer 2010-01-20 12:14:05

+4 A:

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.

John 2010-01-20 12:15:50

+1 for simplicity

Alon 2010-01-20 12:40:37

+1 A:

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.

cyborg 2010-01-20 12:20:18

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?

Pindatjuh 2010-01-20 12:32:53

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

ondra 2010-01-20 12:39:48

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.

cyborg 2010-01-20 12:55:38

+2 A:

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.

balpha 2010-01-20 12:26:34

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

Pindatjuh 2010-01-20 12:29:04

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

balpha 2010-01-20 12:38:36

+1 A:

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.

ondra 2010-01-20 12:33:41

Where can I get such an encoded UTM and it's data?

Pindatjuh 2010-01-20 12:35:29

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?

Pindatjuh 2010-01-20 12:37:38

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.

ondra 2010-01-20 21:23:17

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: http://www.cs.uml.edu/~wang/cs502/tiling.pdf

ondra 2010-01-20 21:28:16

Thanks very much! Very good reference, thank you very much!

Pindatjuh 2010-01-20 22:08:43

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

David Thornley 2010-02-18 21:08:00

+1 A:

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.

Felixyz 2010-04-03 04:01:40

ansaurus

tags:

views:

answers:

Universal Turing Machine Problems

related questions