NDLI: Do Accelerating Turing Machines Compute the Uncomputable?

Content Provider	Springer Nature Link
Author	Jack Copeland, B. Shagrir, Oron
Copyright Year	2011
Abstract	Accelerating Turing machines have attracted much attention in the last decade or so. They have been described as “the work-horse of hypercomputation” (Potgieter and Rosinger 2010: 853). But do they really compute beyond the “Turing limit”—e.g., compute the halting function? We argue that the answer depends on what you mean by an accelerating Turing machine, on what you mean by computation, and even on what you mean by a Turing machine. We show first that in the current literature the term “accelerating Turing machine” is used to refer to two very different species of accelerating machine, which we call end-stage-in and end-stage-out machines, respectively. We argue that end-stage-in accelerating machines are not Turing machines at all. We then present two differing conceptions of computation, the internal and the external, and introduce the notion of an epistemic embedding of a computation. We argue that no accelerating Turing machine computes the halting function in the internal sense. Finally, we distinguish between two very different conceptions of the Turing machine, the purist conception and the realist conception; and we argue that Turing himself was no subscriber to the purist conception. We conclude that under the realist conception, but not under the purist conception, an accelerating Turing machine is able to compute the halting function in the external sense. We adopt a relatively informal approach throughout, since we take the key issues to be philosophical rather than mathematical.
Starting Page	221
Ending Page	239
Page Count	19
File Format	PDF
ISSN	09246495
Journal	Minds and Machines
Volume Number	21
Issue Number	2
e-ISSN	15728641
Language	English
Publisher	Springer Netherlands
Publisher Date	2011-03-18
Publisher Place	Dordrecht
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Accelerating Turing machine Supertask Halting problem ATM paradox Hypercomputation External and internal computation Epistemic embedding Ontology of computing Turing-machine purism Turing-machine realism Thompson lamp paradox Systems Theory, Control Philosophy of Mind Interdisciplinary Studies Artificial Intelligence (incl. Robotics)
Content Type	Text
Resource Type	Article
Subject	Philosophy Artificial Intelligence

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

From Symbol to ‘Symbol’, to Abstract Symbol: Response to Copeland and Shagrir on Turing-Machine Realism Versus Turing-Machine Purism

Physical Computation: How General are Gandy’s Principles for Mechanisms?

A Brief Critique of Pure Hypercomputation

Accelerating Turing Machines

Physical Hypercomputation and the Church–Turing Thesis

On the Possibilities of Hypercomputing Supertasks

Quantum Hypercomputability?

Turing’s Responses to Two Objections

Buttresses of the Turing Barrier

Do Accelerating Turing Machines Compute the Uncomputable?

Similar Documents

From Symbol to ‘Symbol’, to Abstract Symbol: Response to Copeland and Shagrir on Turing-Machine Realism Versus Turing-Machine Purism

Physical Computation: How General are Gandy’s Principles for Mechanisms?

A Brief Critique of Pure Hypercomputation

Accelerating Turing Machines

Physical Hypercomputation and the Church–Turing Thesis

On the Possibilities of Hypercomputing Supertasks

Quantum Hypercomputability?

Turing’s Responses to Two Objections

Buttresses of the Turing Barrier

Do Accelerating Turing Machines Compute the Uncomputable?