The Diagonal Method and Hypercomputation

From MaRDI portal



Abstract: The diagonal method is often used to show that Turing machines cannot solve their own halting problem. There have been several recent attempts to show that this method also exposes either contradiction or arbitrariness in other theoretical models of computation that claim to be able to solve the halting problem for Turing machines. We show that such arguments are flawed -- a contradiction only occurs if a type of machine can compute its own diagonal function. We then demonstrate why such a situation does not occur for the methods of hypercomputation under attack and why it is unlikely to occur in any other serious methods.


The diagonal method of logic is usually used to show serious limitations of the capabilities of any general computer by proving that Turing machines cannot solve their own ``Halting Problem. Of course, there are other important diagonal methods, too. E.g., Cantor used the (prototype of) diagonal methods in his set theory to prove the existence of transcendental numbers and that the real numbers are not countable. In this philosophical note, the authors present arguments which claim to show logical flaws in discussions by others which attack the methods of ``hypercomputation. Further, they defend the view that some specific hypermachines (e.g., quantum computers) avoid any contradictions associated with diagonalization. However, the arguments seem vaguely similar to heated debates between the artificial intelligence community and many others over the equivalence of mind and machine or consciousness and computation. The reviewer looks forward to seeing hypercomputation techniques applied to: (1) Cantor's diagonal method and, thus, to axiomatic set theory, itself and (2) the law of excluded middle; e.g., recall that the standard proof of Gödel's completeness theorem for the pure functional calculus of first-order uses the law of excluded middle in the syntax language and, thus, the proof provides no effective solution of the important decision problem for the pure functional calculus of first-order.











This page was built for publication: The Diagonal Method and Hypercomputation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5706684)