Journal Article

Hypercomputation and the Physical Church‐Turing Thesis

Paolo Cotogno

in The British Journal for the Philosophy of Science

Published on behalf of British Society for the Philosophy of Science

Volume 54, issue 2, pages 181-223
Published in print June 2003 | ISSN: 0007-0882
Published online June 2003 | e-ISSN: 1464-3537 | DOI: http://dx.doi.org/10.1093/bjps/54.2.181
Hypercomputation and the Physical Church‐Turing Thesis

More Like This

Show all results sharing these subjects:

  • Philosophy of Science
  • Science and Mathematics

GO

Show Summary Details

Preview

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, more than a logico‐mathematical, proposition. We review the main approaches to computation beyond Turing definability (‘hypercomputation’): supertask, non‐well‐founded, analog, quantum, and retrocausal computation. These models depend on infinite computation, explicitly or implicitly, and appear physically implausible; moreover, even if infinite computation were realizable, the Halting Problem would not be affected. Therefore, Thesis P is not essentially different from the standard Church‐Turing Thesis.

1 Introduction

2 Computability and incomputability

3 The physical interpretation of the Church‐Turing Thesis

4 Supertasks and infinite computation

5 Computation on non‐well‐founded domains

6 Analog computation

7 Quantum computation

8 Retrocausal computation

9 Conclusions

Journal Article.  0 words. 

Subjects: Philosophy of Science ; Science and Mathematics

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.