Problem Detail: 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...
Asked By : Hernan_eche
Answered By : Patrick87
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.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/12917
