Oracles

An oracle is a hypothetical device that would solve a computational program, free of charge.

Say you create a subroutine to multiply two matrices. After the subroutine has been created, then you can just simply think about it as a “black box” that you give two matrices and outcomes their product.

We could also consider that we have oracles for problems that are unsolvable or problems that we don’t know how to solve.

Then after we assuming that oracle can solve such problems, the hierarchies of unsolvability could be created.

It can tell us things like “this problem can’t be solvable, because if it were, it would allow us to solve other unsolvable problem”

Given: A:\{0, 1\}^*\rightarrow \{0, 1\}

where the input is any string of any length and the output is a 0 or 1 answering the problem, then

we write M^A for a TM M with access to Oracle A. Assuming that M is a multi-tape TM and one of its tape is a special “Oracle tape”. M can then ask a question, some string x, for the oracle on the oracle tape, and in the next step, the oracle will write its answer, A(x), on the oracle tape.

Example 1: Diophantine equations

Given: x^n + y^n =z^n, n\leq 3, xyz\not = 0, Is there a solution in just integers?

Actually, there is no solution involving just integers, and this was an unsolved problem for 350 years.

What if we had an oracle for the halting problem? Can we solve this problem?

To solve this problem, we might try every possible solution in order, (x,y,z,n), s.t.

x + y + z + n = 1

x + y + z + n = 2

x + y + z + n = 3

x + y + z + n = \cdots

try them all, one by one in order, and then pause when we find the solution. However, if there is no solution, it would just go on forever. So our question to the oracle would be, “Does this program halt or not?”, and if so, the Diophantine equation would be solvable.

But if we solve the Diophantine problem, can we also then solve the halting problem?

in 1970 it was shown that there was no algorithm to solve Diophantine equations because if there were, then there would also be an algorithm to solve the halting problem. Therefore, the halting problem is reducible to this problem.

Turing Degrees

A Turing degree is a maximal set of all problems that are reducible to each other.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s