Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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.

like image 678
Pindatjuh Avatar asked Feb 04 '23 07:02

Pindatjuh


2 Answers

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.

like image 121
John Avatar answered Mar 28 '23 05:03

John


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.

like image 37
balpha Avatar answered Mar 28 '23 05:03

balpha