Oracles in the Hypercomputation Debate
Florent Franchette
The hypercomputation debate consists of deciding upon the possibility of constructing a hypercomputing device. Amongst potential building strategies, strategy O – where O stands for oracle – refers to the construction of a device that could hypercompute with the aid of a physical oracle, namely external information coming from nature. Although a number of oracular devices have been devised, they are not generally considered as viable proposals, especially given they supposedly involve conceptual and physical issues. This article is intended to defend strategy O though. It will be argued that strategy O is unfairly criticised, for criticisms are largely the result of misunderstandings about what physical oracles are and what they are capable of. This will allow the concept of an oracle to be better understood, so that the hypercomputation debate can make progress.
Keywords: Hypercomputation, computability, hypermachine, Turing machine, oracle, oracular computation, randomness