The Diagonal Method and Hypercomputation

DOI10.1093/PHISCI/AXI108MaRDI QIDQ5706684zbMATH OpenOpenAlexFDO

Authors Toby Ord, T. D. Kieu

Publication date 21 November 2005

Published in The British Journal for the Philosophy of Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0307020

zbMATH Keywords

Church-Turing thesisdiagonal methodslimitations of non-computabilityquantum computersTuring machines

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) Turing machines and related notions (03D10)

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.

Recommendations

• scientific article; zbMATH DE number 4004151
• Hypercomputation: Philosophical issues
• Physical constraints on hypercomputation
• What is wrong with Cantor's diagonal argument?
• On the Possibility, or Otherwise, of Hypercomputation

Cited in

(16)

• Is Gold-Putnam diagonalization complete?
• Hypercomputation with quantum adiabatic processes
• Epistemic horizons and the foundations of quantum mechanics
• Cantor-like transfinite sequences and Gödel-like incompleteness revealed by means of Mersenne transfinite dimensional Boolean hypercube concatenation
• On TAE machines and their computational power
• The case for hypercomputation
• Zeno machines and hypercomputation
• On hypercomputation, universal and diagonalization complete problems
• On the Brightness of the Thomson Lamp: A Prolegomenon to Quantum Recursion Theory
• What is wrong with Cantor's diagonal argument?
• scientific article; zbMATH DE number 4004151 (Why is no real title available?)
• Paraconsistent computation and dialetheic machines
• Hypercomputation: fantasy or reality? A position paper
• A note on diagonalization
• Analogy and diagonal argument
• Accelerating machines: a review

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)