Computation, hypercomputation, and physical science

DOI10.1016/J.JAL.2008.09.007MaRDI QIDQ959046zbMATH OpenOpenAlexFDO

Authors Konstantine Arkoudas

Publication date 11 December 2008

Published in Journal of Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jal.2008.09.007

zbMATH Keywords

Church-Turing thesisGandy's thesishypercomputationquantum computabilityquantum computersTuring limit

Mathematics Subject Classification ID

Philosophical and critical aspects of logic and foundations (03A05) Turing machines and related notions (03D10) Recursive functions and relations, subrecursive hierarchies (03D20) General topics in the theory of computing (68Q01) General topics in artificial intelligence (68T01) Quantum computation (81P68)

Review text

In this logico-philosophical paper, the author (1) investigates, in great detail, the role of the Church-Turing Thesis in computability theory and (2) criticizes the works of several people on their interpretations of the Church-Turing Thesis. He especially argues against some of the results of B. J. Copeland, who holds that the Church-Turing Thesis is widely misunderstood by philosophers and cognitive scientists. The overall conclusion of the paper under review is that prospects for a scientific theory of hypercomputation are very poor, since ``physical science does not have the wherewithal to investigate computability or to discover its ultimate `limit'. However, in the reviewer's opinion, physical theory does have the capability to move toward an ultimate `limit' with (nondeterministic) quantum systems using entropy flow as a measure of information flow in pico-computers. That is, for every calculable function there exists a quantum computer/stochastic automaton (not necessarily subject to the Church-Turing Thesis) that computes it. The computational capability of quantum computers can be identified with hypercomputation. The physical science used to develop quantum computers is a well-understood part of quantum theory being used by several physicists.

Recommendations

• scientific article; zbMATH DE number 1909825
• Physics and computation
• Physical perspectives on computation, computational perspectives on physics
• Physics and the new computation
• SOFSEM 2006: Theory and Practice of Computer Science
• Information, Physics, and Computation
• Computability in analysis and physics
• scientific article; zbMATH DE number 42077
• The computational status of physics
• Limits of Computation and Physical Reality

Cites work

• Computability and Recursion
• Does a rock implement every finite-state automaton?
• scientific article; zbMATH DE number 3131080 (Why is no real title available?)
• scientific article; zbMATH DE number 3728250 (Why is no real title available?)
• scientific article; zbMATH DE number 3467028 (Why is no real title available?)
• scientific article; zbMATH DE number 3577197 (Why is no real title available?)
• scientific article; zbMATH DE number 3586480 (Why is no real title available?)
• scientific article; zbMATH DE number 727991 (Why is no real title available?)
• scientific article; zbMATH DE number 1865918 (Why is no real title available?)
• scientific article; zbMATH DE number 1909820 (Why is no real title available?)
• scientific article; zbMATH DE number 1909827 (Why is no real title available?)
• scientific article; zbMATH DE number 5064395 (Why is no real title available?)
• scientific article; zbMATH DE number 3187218 (Why is no real title available?)
• On code generation in a PASCAL compiler
• The B-Book
• The Mechanical Evaluation of Expressions
• The wave equation with computable initial data such that its unique solution is not computable
• Turing's O-machines, Searle, Penrose and the brain

Cited in

(12)

• Computability of physical operations
• Computational universes
• Heterotic Computing
• scientific article; zbMATH DE number 1273618 (Why is no real title available?)
• On the Possibility, or Otherwise, of Hypercomputation
• scientific article; zbMATH DE number 1909825 (Why is no real title available?)
• Mathematical and technological computability
• Computation and its limits.
• Church's thesis and physical computation
• The hypercomputation thesis: stakes and philosophical problems
• General relativistic hypercomputing and foundation of mathematics
• The computational status of physics

Describes a project that uses

Uses Software

• ALGOL 60

This page was built for publication: Computation, hypercomputation, and physical science

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