# Is oracle computer capable of doing infinite loops?

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...

• 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. – Yuval Filmus Jun 26 '13 at 19:43
• (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. – Patrick87 Jun 26 '13 at 23:01