You gain an oracle turing machine.
Moderators: phlip, Moderators General, Prelates

 Posts: 41
 Joined: Sun May 01, 2011 5:18 am UTC
You gain an oracle turing machine.
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?
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]
That link kills spam[/size][/b][/u]
 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.
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 nonquantum 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.
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.
Re: You gain an oracle turing machine.
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 nonquantum 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 bruteforce 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 multibillion years and more energy then the Sun produces).
Re: You gain an oracle turing machine.
Use binary seach or "bucket search". This also enables you to search arbitrary mathematical proofs.
Re: You gain an oracle turing machine.
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.
 phlip
 Restorer of Worlds
 Posts: 7550
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: You gain an oracle turing machine.
Right...
Write a program that bruteforces 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/loopforever 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)...
Write a program that bruteforces 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/loopforever 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)⚠);}
Re: You gain an oracle turing machine.
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.
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.
Re: You gain an oracle turing machine.
phlip wrote:Right...
Write a program that bruteforces 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/loopforever 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.
Re: You gain an oracle turing machine.
I'd post a "hypothetical" thread like this to glean all possible use from it in secret. *squint*
Re: You gain an oracle turing machine.
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...
 SuperJedi224
 Posts: 17
 Joined: Thu Apr 16, 2015 4:19 pm UTC
Re: You gain an oracle turing machine.
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.
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?
Yeah, I'm wearing groucho glasses over a ninja mask. You have a problem with that?
Re: You gain an oracle turing machine.
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.
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.elasto wrote:At the very least one would worry that this kind of scenario could come about...
There's no such thing as a funny sig.
Re: You gain an oracle turing machine.
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.
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.
Re: You gain an oracle turing machine.
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 twoway 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.
Re: You gain an oracle turing machine.
Oh also: is there a type of oracle that could answer questions that could not be answered with a halting oracle?
 SuperJedi224
 Posts: 17
 Joined: Thu Apr 16, 2015 4:19 pm UTC
Re: You gain an oracle turing machine.
This topic seems to be primarily about order1 halting oracles. We could also consider order2 halting oracles, order3 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 order0 halting oracles as solving the halting problem for some subturingcomplete 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?
Yeah, I'm wearing groucho glasses over a ninja mask. You have a problem with that?
 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.
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.
Re: You gain an oracle turing machine.
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 order1 halting oracles. We could also consider order2 halting oracles[..]
I was unable to google a definition of orders on halting oracles. Do you have a link?
 phlip
 Restorer of Worlds
 Posts: 7550
 Joined: Sat Sep 23, 2006 3:56 am UTC
 Location: Australia
 Contact:
Re: You gain an oracle turing machine.
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 order1 halting oracle solves the halting problem for Turing machines. An order2 halting oracle solves the halting problem for Turing machines that have access to a blackbox order1 halting oracle. And so on.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
 SuperJedi224
 Posts: 17
 Joined: Thu Apr 16, 2015 4:19 pm UTC
Re: You gain an oracle turing machine.
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?
Yeah, I'm wearing groucho glasses over a ninja mask. You have a problem with that?
Who is online
Users browsing this forum: No registered users and 4 guests