You gain an oracle turing machine.

A place to discuss the science of computers and programs, from algorithms to computability.

Formal proofs preferred.

Moderators: phlip, Moderators General, Prelates

blademan9999
Posts: 40
Joined: Sun May 01, 2011 5:18 am UTC

You gain an oracle turing machine.

Postby blademan9999 » Sun Nov 30, 2014 12:07 pm UTC

Lets say somehow you end up with an Oracle turing machine.
Don't ask how you manage to get it, let's say you just have it.
You also do not know how it works, so trying to take it apart would likely just permanently ruin it.
What would you do with it?
http://officeofstrategicinfluence.com/spam/
That link kills spam[/size][/b][/u]

User avatar
scarecrovv
It's pronounced 'double u'
Posts: 674
Joined: Wed Jul 30, 2008 4:09 pm UTC
Location: California

Re: You gain an oracle turing machine.

Postby scarecrovv » Mon Dec 01, 2014 1:11 am UTC

It depends on the type of oracle the machine includes. I suspect you mean a halting oracle though, which can solve the halting problem for any normal Turing machine in a short constant time. If I had a halting oracle the only safe course of action would be to destroy it, after solving a handful of math problems in secret. I wouldn't trust any government with such a machine, and any private owner of such a machine would probably get robbed, assassinated, or both. This is because you could write a program that solves any cryptographic puzzle by brute force, and then either halts or infinite loops depending on a particular bit of the answer. By asking the oracle whether the program will halt for each bit of the key, you could break any non-quantum cryptosystem very quickly.

If I had plans for building an inexpensive halting oracle though, rather than just a single oracle that couldn't be duplicated, I would instead publish the plans for free on the internet. All classical crypto would be useless, but I'm sure society could cope if everyone had that power, and we'd probably get a bunch of shiny new technologies from the oracle in return. The ability to solve any computational problem in time proportional to the size of the answer would be pretty cool.

wumpus
Posts: 501
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: You gain an oracle turing machine.

Postby wumpus » Sun Dec 07, 2014 5:55 pm UTC

scarecrovv wrote:It depends on the type of oracle the machine includes. I suspect you mean a halting oracle though, which can solve the halting problem for any normal Turing machine in a short constant time. If I had a halting oracle the only safe course of action would be to destroy it, after solving a handful of math problems in secret. I wouldn't trust any government with such a machine, and any private owner of such a machine would probably get robbed, assassinated, or both. This is because you could write a program that solves any cryptographic puzzle by brute force, and then either halts or infinite loops depending on a particular bit of the answer. By asking the oracle whether the program will halt for each bit of the key, you could break any non-quantum cryptosystem very quickly.

If I had plans for building an inexpensive halting oracle though, rather than just a single oracle that couldn't be duplicated, I would instead publish the plans for free on the internet. All classical crypto would be useless, but I'm sure society could cope if everyone had that power, and we'd probably get a bunch of shiny new technologies from the oracle in return. The ability to solve any computational problem in time proportional to the size of the answer would be pretty cool.


I think not. How does your "turing machine cryptobreaker" allow you to eliminate more than one possible key per request? If it can't do that, you merely have a device that can run at some constant multiple of the time needed for a brute-force attack, which would still almost certainly take longer than the universe will last (simply running through 2**256 states in a finite state machine requires multi-billion years and more energy then the Sun produces).

korona
Posts: 495
Joined: Sun Jul 04, 2010 8:40 pm UTC

Re: You gain an oracle turing machine.

Postby korona » Sun Dec 07, 2014 6:17 pm UTC

Use binary seach or "bucket search". This also enables you to search arbitrary mathematical proofs.

wumpus
Posts: 501
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: You gain an oracle turing machine.

Postby wumpus » Mon Dec 08, 2014 1:00 am UTC

korona wrote:Use binary seach or "bucket search". This also enables you to search arbitrary mathematical proofs.


Looks like that will work, just put the oracle between outer and inner loops. Didn't think long enough on that one.

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: You gain an oracle turing machine.

Postby phlip » Mon Dec 08, 2014 1:15 am UTC

Right...

Write a program that brute-forces an encryption key, or some other super long intractable problem. Then, if the first bit of the result is a 1, halt, otherwise loop forever.

Obviously, that program would take a ridiculously long time to run if it does halt, and if it doesn't halt then that trivially takes a long time too. But still, it's a program that will either halt or it wont, feed it into the halting oracle and see what it says. If it says "halt", the first bit of our output is a 1, if it doesn't, then either the first bit of our output is a 0, or the original algorithm doesn't halt (can be easily verified by swapping the halt/loop-forever cases and trying again).

Of course, the resolution to that is that the oracle doesn't run in constant time... but I can't think of any way to figure out how that would work that isn't either (a) poorly defined (eg "it takes as long as it would normally take to run if it did halt, even if it doesn't..." or similar handwaving) or (b) completely unusable (eg it runs in O(BB(n)) time where BB is the busy beaver function)...

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: You gain an oracle turing machine.

Postby WarDaft » Wed Dec 10, 2014 1:21 am UTC

With such a machine, you could test whether or not our universe is 'simply' describable.

So, at least, so far as we seem to *hope*... our universe obeys predictable laws. That means there's a computation that advances our universe from one state to the next soonest possible state.

Also, our universe seems to be progressing from lower entropy to higher entropy. That suggests that our universe started off with very low entropy.


So, low starting entropy... fixed set of rules...

That means there's (in theory) a fixed set of bits which fully describes our existence. A fixed bit count means a fixed informational entropy, which means a fixed size of turing machine to perfectly calculate our universe. Take a large enough chunk of quantum random information, and the ideal compression of that chunk will be to calculate our universe which produces that chunk.


Use the oracle to determine which compression (and so, which machine) it is that is running our universe.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

wumpus
Posts: 501
Joined: Thu Feb 21, 2008 12:16 am UTC

Re: You gain an oracle turing machine.

Postby wumpus » Wed Dec 10, 2014 2:24 pm UTC

phlip wrote:Right...

Write a program that brute-forces an encryption key, or some other super long intractable problem. Then, if the first bit of the result is a 1, halt, otherwise loop forever.

Obviously, that program would take a ridiculously long time to run if it does halt, and if it doesn't halt then that trivially takes a long time too. But still, it's a program that will either halt or it wont, feed it into the halting oracle and see what it says. If it says "halt", the first bit of our output is a 1, if it doesn't, then either the first bit of our output is a 0, or the original algorithm doesn't halt (can be easily verified by swapping the halt/loop-forever cases and trying again).

Of course, the resolution to that is that the oracle doesn't run in constant time... but I can't think of any way to figure out how that would work that isn't either (a) poorly defined (eg "it takes as long as it would normally take to run if it did halt, even if it doesn't..." or similar handwaving) or (b) completely unusable (eg it runs in O(BB(n)) time where BB is the busy beaver function)...


If the oracle "knows" that it is examining more than one loop (and as an oracle it can determine if something was unrolled and would change if scaled...), this might work. I'd still assume that it can still pretty much determine the "real" theory of everything (and also break encryption) with even more cleverness.

Tyndmyr
Posts: 10170
Joined: Wed Jul 25, 2012 8:38 pm UTC

Re: You gain an oracle turing machine.

Postby Tyndmyr » Wed Dec 31, 2014 5:23 pm UTC

I'd post a "hypothetical" thread like this to glean all possible use from it in secret. *squint*

elasto
Posts: 3126
Joined: Mon May 10, 2010 1:53 am UTC

Re: You gain an oracle turing machine.

Postby elasto » Thu Jan 01, 2015 3:09 am UTC

WarDaft wrote:With such a machine, you could test whether or not our universe is 'simply' describable.

So, at least, so far as we seem to *hope*... our universe obeys predictable laws. That means there's a computation that advances our universe from one state to the next soonest possible state.

Also, our universe seems to be progressing from lower entropy to higher entropy. That suggests that our universe started off with very low entropy.


So, low starting entropy... fixed set of rules...

That means there's (in theory) a fixed set of bits which fully describes our existence. A fixed bit count means a fixed informational entropy, which means a fixed size of turing machine to perfectly calculate our universe. Take a large enough chunk of quantum random information, and the ideal compression of that chunk will be to calculate our universe which produces that chunk.


Use the oracle to determine which compression (and so, which machine) it is that is running our universe.

Wouldn't the existence of such a machine prove the universe wasn't simply describable though? Something feels wrong about the oracle being able to simulate a universe which contains the oracle. eg. Could one could set up a situation where the 'outer' oracle stops iff the 'inner' one doesn't (or something) - and yet they are meant to be the same object...

At the very least one would worry that this kind of scenario could come about...

User avatar
SuperJedi224
Posts: 17
Joined: Thu Apr 16, 2015 4:19 pm UTC

Re: You gain an oracle turing machine.

Postby SuperJedi224 » Mon Jun 08, 2015 2:35 pm UTC

I'd use it to test the properties of infinite sequences.

Write a program that halts if and only if it finds a term in the sequence for which the statement being tested is false. Call a halting oracle on it. The end.

Also, it could be used, albeit less efficiently, to compute Rado's Sigma Function and the Max Shifts Function.
Striving for neutral good while caught in the crossfire of a struggle between lawful stupid, chaotic stupid, and, on occasion, just plain stupid.
Yeah, I'm wearing groucho glasses over a ninja mask. You have a problem with that?

User avatar
Wildcard
Candlestick!
Posts: 251
Joined: Wed Jul 02, 2008 12:42 am UTC
Location: Outside of the box

Re: You gain an oracle turing machine.

Postby Wildcard » Tue Jun 09, 2015 7:03 pm UTC

WarDaft wrote:So, at least, so far as we seem to *hope*... our universe obeys predictable laws. That means there's a computation that advances our universe from one state to the next soonest possible state.

I just want to point out that this is a "leap of faith" which is a logical disconnect from the premise. It contains a similar logical flaw to the argument, "The universe is more complex than any system we have developed to simulate it. That means it was created by intelligent design." It simply doesn't follow. In either argument, there are other unstated assumptions which it is necessary to accept before that conclusion will logically follow. I'm also aware of the potential for a flame war on this point, and I have no interest in that.

elasto wrote:At the very least one would worry that this kind of scenario could come about...
Nice! I like that story. I had come across it some years ago, along with other writings from the same author. Only thing that bothered me about his ultimate computer virus story (not the one you linked to) was the idea that it could infect old transistor radios...which is physically impossible as they aren't computing devices of any sort and can't "run a program" based on signals broadcast to them.
There's no such thing as a funny sig.

Tub
Posts: 321
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: You gain an oracle turing machine.

Postby Tub » Thu Jun 11, 2015 8:45 am UTC

If you have a halting oracle which runs on constant time and is reusable as often as you want, you can run any computable function in O(n) time, where n is the size of the output. Not quite infinite processing power, but close enough for most practical purposes if the halting oracle's constant runtime is reasonably small.

So what would I do? Looking at the millenium problems to see which of them can be solved by brute force would be a start. Sure could use that money so I could quit my job and focus more on playing with the oracle.


Of course, sooner or later I'd write a program which calls the halting oracle on itself, then enters an infinite loop iff the oracle predicted termination. Just to see what happens.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: You gain an oracle turing machine.

Postby quintopia » Sun Jun 14, 2015 6:40 pm UTC

Tub wrote:Of course, sooner or later I'd write a program which calls the halting oracle on itself, then enters an infinite loop iff the oracle predicted termination. Just to see what happens.


I would guess it's a "weak" halting oracle: it's not callable. You put in a program and it gives you an answer. No two-way communication. Yes, if you could figure out what algorithm the thing uses, you could feed it a copy of itself, but by assumption we can't know how it works.

User avatar
quintopia
Posts: 2906
Joined: Fri Nov 17, 2006 2:53 am UTC
Location: atlanta, ga

Re: You gain an oracle turing machine.

Postby quintopia » Sun Jun 14, 2015 6:43 pm UTC

Oh also: is there a type of oracle that could answer questions that could not be answered with a halting oracle?

User avatar
SuperJedi224
Posts: 17
Joined: Thu Apr 16, 2015 4:19 pm UTC

Re: You gain an oracle turing machine.

Postby SuperJedi224 » Sun Jun 14, 2015 7:47 pm UTC

This topic seems to be primarily about order-1 halting oracles. We could also consider order-2 halting oracles, order-3 halting oracles, ..., order-ω halting oracles, order-ω+1 halting oracles, order-ω+2 halting oracles, and so on for any countable ordinal we want. (Except, perhaps, 0; though we could define order-0 halting oracles as solving the halting problem for some sub-turing-complete system, which most likely IS computable in that case.)
Striving for neutral good while caught in the crossfire of a struggle between lawful stupid, chaotic stupid, and, on occasion, just plain stupid.
Yeah, I'm wearing groucho glasses over a ninja mask. You have a problem with that?

User avatar
scarecrovv
It's pronounced 'double u'
Posts: 674
Joined: Wed Jul 30, 2008 4:09 pm UTC
Location: California

Re: You gain an oracle turing machine.

Postby scarecrovv » Sun Jun 14, 2015 9:20 pm UTC

Though the halting oracle is the most famous, you could come up with any oracle you like. Others include the random oracle which generates random numbers, and the matrioid oracle (not really understanding what a matroid is I can't elaborate, but wikipedia seems to think it's important). You could also imagine a SAT oracle capable of solving the Boolean satisfiability problem in (for instance) polynomial time. Even if P!=NP without the SAT oracle, the oracle would allow you to behave as though P=NP.

Tub
Posts: 321
Joined: Wed Jul 27, 2011 3:13 pm UTC

Re: You gain an oracle turing machine.

Postby Tub » Mon Jun 15, 2015 6:55 am UTC

quintopia wrote:Oh also: is there a type of oracle that could answer questions that could not be answered with a halting oracle?

The oracle does not solve the fundamental problem of computability: there is a countably infinite number of turing machines, but an uncountably infinite number of questions.
As best, the oracle adds another countably infinite set of answers, but that still leaves an uncountably infinite number of problems.

SuperJedi224 wrote:This topic seems to be primarily about order-1 halting oracles. We could also consider order-2 halting oracles[..]

I was unable to google a definition of orders on halting oracles. Do you have a link?

User avatar
phlip
Restorer of Worlds
Posts: 7543
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

Re: You gain an oracle turing machine.

Postby phlip » Mon Jun 15, 2015 7:10 am UTC

Tub wrote:I was unable to google a definition of orders on halting oracles. Do you have a link?

The usual definitions I've come across are along the lines of: A order-1 halting oracle solves the halting problem for Turing machines. An order-2 halting oracle solves the halting problem for Turing machines that have access to a black-box order-1 halting oracle. And so on.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

User avatar
SuperJedi224
Posts: 17
Joined: Thu Apr 16, 2015 4:19 pm UTC

Re: You gain an oracle turing machine.

Postby SuperJedi224 » Mon Jun 15, 2015 12:31 pm UTC

Yeah, that's pretty much it.
Striving for neutral good while caught in the crossfire of a struggle between lawful stupid, chaotic stupid, and, on occasion, just plain stupid.
Yeah, I'm wearing groucho glasses over a ninja mask. You have a problem with that?


Return to “Computer Science”

Who is online

Users browsing this forum: No registered users and 6 guests