Minds and Machines 7 (3):321-44 (1997)

Authors
Oron Shagrir
Hebrew University of Jerusalem
Abstract
  This paper challenges two orthodox theses: (a) that computational processes must be algorithmic; and (b) that all computed functions must be Turing-computable. Section 2 advances the claim that the works in computability theory, including Turing's analysis of the effective computable functions, do not substantiate the two theses. It is then shown (Section 3) that we can describe a system that computes a number-theoretic function which is not Turing-computable. The argument against the first thesis proceeds in two stages. It is first shown (Section 4) that whether a process is algorithmic depends on the way we describe the process. It is then argued (Section 5) that systems compute even if their processes are not described as algorithmic. The paper concludes with a suggestion for a semantic approach to computation
Keywords Algorithm  Computationalism  Science  Turing Machines
Categories (categorize this paper)
Reprint years 2004
ISBN(s)
DOI 10.1023/A:1008236522699
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 70,192
Through your library

References found in this work BETA

The Emperor’s New Mind.Roger Penrose - 1989 - Oxford University Press.
Computing Machinery and Intelligence.Alan M. Turing - 1950 - Mind 59 (October):433-60.
On Computable Numbers, with an Application to the N Tscheidungsproblem.Alan Turing - 1936 - Proceedings of the London Mathematical Society 42 (1):230-265.

View all 34 references / Add more references

Citations of this work BETA

Computation Without Representation.Gualtiero Piccinini - 2008 - Philosophical Studies 137 (2):205-241.
Why We View the Brain as a Computer.Oron Shagrir - 2006 - Synthese 153 (3):393-416.
The Physical Church–Turing Thesis: Modest or Bold?Gualtiero Piccinini - 2011 - British Journal for the Philosophy of Science 62 (4):733-769.

View all 12 citations / Add more citations

Similar books and articles

Is Computationalism Trivial?Marcin Miłkowski - 2007 - In Gordana Dodig Crnkovic & Susan Stuart (eds.), Computation, Information, Cognition: The Nexus and the Liminal. Cambridge Scholars Press.
How Minds Can Be Computational Systems.William J. Rapaport - 1998 - Journal of Experimental and Theoretical Artificial Intelligence 10 (4):403-419.
Church's Thesis and the Conceptual Analysis of Computability.Michael Rescorla - 2007 - Notre Dame Journal of Formal Logic 48 (2):253-280.
The Broad Conception of Computation.Jack Copeland - 1997 - American Behavioral Scientist 40 (6):690-716.
Is the Church-Turing Thesis True?Carol E. Cleland - 1993 - Minds and Machines 3 (3):283-312.

Analytics

Added to PP index
2009-01-28

Total views
120 ( #97,512 of 2,507,400 )

Recent downloads (6 months)
4 ( #170,014 of 2,507,400 )

How can I increase my downloads?

Downloads

My notes