# Physical Hypercomputation and the Church–Turing Thesis

@article{Shagrir2004PhysicalHA, title={Physical Hypercomputation and the Church–Turing Thesis}, author={Oron Shagrir and Itamar Pitowsky}, journal={Minds and Machines}, year={2004}, volume={13}, pages={87-101} }

We describe a possible physical device that computes a function that cannot be computed by a Turing machine. The device is physical in the sense that it is compatible with General Relativity. We discuss some objections, focusing on those which deny that the device is either a computer or computes a function that is not Turing computable. Finally, we argue that the existence of the device does not refute the Church–Turing thesis, but nevertheless may be a counterexample to Gandy's thesis.

#### Figures and Topics from this paper

#### 67 Citations

From Logic to Physics: How the Meaning of Computation Changed over Time

- Computer Science
- CiE
- 2007

The Church-Turing thesis cannot be proved in the same sense that a mathematical proposition is provable, however, it can be refuted by an example of a function which is not Turing computable, but is nevertheless calculable by some procedure that is intuitively acceptable. Expand

Hypercomputation and the Physical Church‐Turing Thesis

- Computer Science
- The British Journal for the Philosophy of Science
- 2003

A version of the Church‐Turing Thesis states that every effectively realizable physical system can be defined by Turing Machines (‘Thesis P’); in this formulation the Thesis appears an empirical,… Expand

Turing-, Human- and Physical Computability: An Unasked Question

- Computer Science
- Minds and Machines
- 2008

The thesis was presented and justified as formally delineating the class of functions that can be computed by a human carrying out an algorithm but needs to be distinguished from the so-called Physical Church-Turing thesis, according to which all physically computable functions are Turing computable. Expand

Computationalism, The Church–Turing Thesis, and the Church–Turing Fallacy

- Mathematics, Computer Science
- Synthese
- 2005

This work scrutinizes the most prominent arguments for computationalism based on the Church–Turing Thesis in light of recent work on CTT and argues that they are unsound. Expand

What is the Church-Turing Thesis?

- 2020

We aim to put some order to the multiple interpretations of the ChurchTuring Thesis and to the different approaches taken to prove or disprove it. [Answer:] Rosser and its inventor proved that its… Expand

The Physical Church–Turing Thesis: Modest or Bold?

- Computer Science
- The British Journal for the Philosophy of Science
- 2011

It is proposed to explicate the notion of physical computability in terms of a usability constraint, according to which for a process to count as relevant to Physical CT, it must be usable by a finite observer to obtain the desired values of a function. Expand

How to Make a Meaningful Comparison of Models: The Church–Turing Thesis Over the Reals

- Computer Science
- Minds and Machines
- 2016

It is argued that it is possible in both cases to defend an equivalent of the Church–Turing thesis over the reals, and some methodological caveats on the comparison of different computational models are learned. Expand

Physical Computability Theses

- Mathematics
- 2020

The Church-Turing thesis asserts that every effectively computable function is Turing computable. On the other hand, the physical Church-Turing Thesis (PCTT) concerns the computational power of… Expand

Does Quantum Mechanics allow for Infinite Parallelism?

- Physics
- 2004

Recent works have independently suggested that Quantum Mechanics might permit for procedures that transcend the power of Turing Machines as well as of ‘standard’ Quantum Computers. These approaches… Expand

A quantum-information-theoretic complement to a general-relativistic implementation of a beyond-Turing computer

- Computer Science
- Synthese
- 2014

It is suggested that even the foundations of quantum theory and, ultimately, quantum gravity may play an important role in determining the validity of the physical Church–Turing thesis. Expand

#### References

SHOWING 1-10 OF 49 REFERENCES

Computation Beyond the Turing Limit

- Computer Science, Medicine
- Science
- 1995

A simply described but highly chaotic dynamical system called the analog shift map is presented here, which has computational power beyond the Turing limit (super-Turing); it computes exactly like neural networks and analog machines. Expand

Is the Church-Turing thesis true?

- Computer Science
- Minds and Machines
- 2004

It is argued that mundane procedures can be said to be effective in the same sense in which Turing machine procedures can been said toBe effective, and that mundane Procedures differ from Turing machine Procedures in a fundamental way, viz., the former, but not the latter, generate causal processes. Expand

Two Dogmas of Computationalism

- Computer Science
- Minds and Machines
- 2004

It is argued that systems compute even if their processes are not described as algorithmic, and a suggestion for a semantic approach to computation is concluded. Expand

Beyond the universal Turing machine

- Philosophy
- 1999

We describe an emerging field, that of nonclassical computability and nonclassical computing machinery. According to the nonclassicist, the set of well-defined computations is not exhausted by the… Expand

Accelerating Turing Machines

- Computer Science
- Minds and Machines
- 2004

It is argued that accelerating Turing machines are not logically impossible devices, and there are implications concerning the nature of effective procedures and the theoretical limits of computability. Expand

Non-Turing Computers and Non-Turing Computability

- Mathematics
- PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association
- 1994

A true Turing machine (TM) requires an infinitely long paper tape. Thus a TM can be housed in the infinite world of Newtonian spacetime (the spacetime of common sense), but not necessarily in our… Expand

Church's Thesis and Principles for Mechanisms

- Computer Science
- 1980

It is argued that Turing's analysis of computation by a human being does not apply directly to mechanical devices, and it is proved that if a device satisfies the principles then its successive states form a computable sequence. Expand

On Formally Undecidable Propositions of Principia Mathematica and Related Systems

- Computer Science, Mathematics
- 1962

This document is a translation of a large part of Gödel’s proof, where the notation used by Gödel has been largely replaced by other notation. Expand

Unpredictability and undecidability in dynamical systems.

- Physics, Medicine
- Physical review letters
- 1990

It is shown that motion with as few as three degrees of freedom can be equivalent to a Turing machine, and so be capable of universal computation. Expand

Undecidability and intractability in theoretical physics.

- Computer Science, Medicine
- Physical review letters
- 1985

Cellular automata are used to provide explicit examples of various formally undecidable and computationally intractable problems and it is suggested that such problems are common in physical models, and some other potential examples are discussed. Expand