1
$\begingroup$

Solve this problem: "build an infinite binary oscilator"

With a Turing Machine we can solve it

a=False
While True:
   a=not a
   print a,

then output will be

True False True False True False ...

(for ever)

I think an oracle can't do it, because its definition, it could solve in "one operation", but here there's not halting as a request of the problem statement. Is it true?

EDIT: Oracle definition from wikipedia

".. an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any complexity class. Even undecidable problems, like the halting problem, can be used."

So what if that TM ask its black box oracle to create an infinite binary oscilation?

   1- oracle black box can't do infinite loops
   2-TM can't ask that problem to oracle 
   3- Does it return a string with a source code as answer? weird
   4-or other options...
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It depends on your definitions. The usual definitions also don't recognize your Turing machine example as valid. Perhaps there are definitions of oracles in which this example does make sense. $\endgroup$
    – Yuval Filmus
    Jun 26, 2013 at 19:43
  • 1
    $\begingroup$ (1) An oracle can answer questions that would require a TM to perform infinitely many computation steps. (2) A TM can only ask an oracle a question with a finite answer: yes/no, a finite string of symbols, a finite number, etc. (3) It is certainly possible that you could have an oracle that returns the source code corresponding to a binary oscillator, if that's what you want your oracle to do. It's not a particularly interesting oracle, though, as it always spits out the same answer. (4) See my answer for a comparison to hypercomputation, i.e., giving an infinite answer in finite time. $\endgroup$
    – Patrick87
    Jun 26, 2013 at 23:01

2 Answers 2

Reset to default
2
$\begingroup$

I'm with Yuval Filmus on this. Oracle seems to be the wrong characterization. An oracle is normally thought of as something that can decide a problem asymptotically faster than a Turing machine (or at all, for undecidable problems).

What you're describing sounds, perhaps, more like hypercomputation. Consider, for instance, a Zeno machine. It could output "True" after 1 minute, "False" after an additional 30 seconds, "True" 15 seconds later, and so on, completing the task you set out for it in two minutes.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I'm not sure hypercomputation is a correct analogy. It seems more like a synchronous distributed model in which you do something every round. You can delegate work to oracles this way even if they run forever - as long as you define your computation model accordingly. $\endgroup$
    – Yuval Filmus
    Jun 26, 2013 at 21:09
1
$\begingroup$

A simple model that is close to what you need is a TM with an oracle that receives its (finite) input on a semi-infinite query tape and puts the answer on an semi-infinite oracle result tape (accessible by the TM control: after the oracle produces its (possibly infinite) result, the TM head on the oracle result tape is moved on the leftmost cell).

An oracle "Doing an infinite loop" is equivalent to an oracle that writes an infinite sequence of 0-1 on the oracle result tape.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.