Oracle Machines and the Verification Problem

Florent Franchette presented an interesting problem in his "Oracle Hypermachines Faced with the Verification Problem". Franchette argues that a physical oracle machine cannot be used to prove that physical hypercomputers exist simply because we cannot verify the results computed by the machine. However, an answer to what can be computed by a form of oracle Turing machine is described in "Computational complexity with experiments as oracles" (see also "Computational complexity with experiments as oracles. II. Upper bounds"). Roughly, their oracle machine, which is called an analog-digital Turing machine, is an ordinary Turing machine coupled to an abstract physical experiment. The authors of these papers prove that this machines have computational power that goes beyond the Church-Turing barrier. Now, if one proves that a machine is actually a hypercomputer, then I think there is no need to verify results computed. After all, we trust the results computed by ordinary machines, so why shouldn't we  trust the results computed by a hypercomputer?


Δημοφιλείς αναρτήσεις από αυτό το ιστολόγιο

New milestone in quantum supremacy