Oron Shagrir
Skip Abstract Section
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.
- Amit, D. (1989), Modeling Brain Function, Cambridge: Cambridge University Press.Google Scholar
- Block, N. and Fodor, J.A. (1972), 'Cognitivism and the Analog/Digital Distinction', unpublished manuscript.Google Scholar
- Church, A. (1936a), 'An Unsolvable Problem of Elementary Number Theory', Am. J. Math., 58 pp. 345-363. Reprinted in Davis (1965), pp. 88-107.Google ScholarCross Ref
- Church, A. (1936b), 'A Note on the Entscheidungsproblem', Journal of Symbolic Logic, 1, pp. 40-41. Reprinted in Davis (1965), pp. 108-115.Google ScholarCross Ref
- Churchland, P.S. and Sejnowski, T. (1992), The Computational Brain, Cambridge, MA: The MIT Press. Google ScholarDigital Library
- Cleland, C. (1993), 'Is the Church-Turing Thesis True?', Minds and Machines, 3, 283-312.Google ScholarCross Ref
- Cummins, R. (1989), Meaning and Mental Represenation, Cambridge, MA: The MIT Press.Google Scholar
- Cummins R. and Schwarz G. (1991), 'Connectionism, Computation, and Cognition', in Horgan, T. and Tienson, J. (eds.), Connectionism and the Philosophy of Mind, Dordrecht: Kluwer, pp. 60-73.Google Scholar
- Davis, M. (ed.) (1965), The Undecidable: Basic Papers on Undecidable Propositions, Unsolvable Problems and Computable Functions, New-York: Raven. Google ScholarDigital Library
- Demopoulos, W. (1987), 'On Some Fundamental Distinctions of Computationalism', Synthese, 70, pp. 79-96.Google ScholarCross Ref
- Dietrich, E. (1990), 'Computationalism', Social Epistemology, 4, pp. 135-154.Google ScholarCross Ref
- Earman, J. (1986), A Primer for Determinism, Holland: D. Reidel.Google Scholar
- Fetzer, J.H. (1994), 'Mental Algorithms: Are Minds Computational Systems?', Pragmatics and Cognition, 2, pp. 1-29.Google ScholarCross Ref
- Gandy, R.O. (1980), 'Church's Thesis and Principles of Mechanisms', in Barwise J., Keisler J.J. and Kunen K. (eds.), The Kleene Symposium, Amsterdam: North-Holland, pp. 123-145.Google ScholarCross Ref
- Gandy R.O. (1988), 'The Confluence of Ideas in 1936', in Herken, R. (1988), pp. 55-111.Google Scholar
- Gödel, K. (1931), 'Uber formal unentscheidbare Satze der Principia Mathematica und verwandter Systeme I', J. Monast. Math. Ph., 38, pp. 173-198. Translated and reprinted in Davis (1965), pp. 4-38.Google ScholarCross Ref
- Gödel, K. (1946), 'Remarks before the Princeton Bicentennial Conference on Problems in Mathematics', Reprinted in Davis (1965), pp. 84-88.Google Scholar
- Goel, V. (1991), 'Notationality and the Information-Processing Mind', Minds and Machines, 1, pp. 129-165.Google ScholarCross Ref
- Goodman, N. (1968), Languages of Art, Indianapolis: Bobbs-Merrill.Google Scholar
- Grzegorczyk, A. (1955), 'Computable Functionals', Fund. Math., 42, pp. 168-202.Google ScholarCross Ref
- Grzegorczyk, A. (1957), 'On the Definitions of Computable Real Continuous Functions', Fund. Math., 44, pp. 61-71.Google ScholarCross Ref
- Haugeland, J. (1981), 'Analog and Analog', Philosophical Topics, 12, pp. 213-225.Google ScholarCross Ref
- Herken, R. (ed.) (1988), The Universal Turing-Machine, A Half-Century Survey, Oxford: Oxford University Press. Google ScholarDigital Library
- Hilbert, D. and Ackermann, W. (1928), Grundzuge der Theoretischen Logic, Berlin.Google Scholar
- Hopfield, J.J. (1982), 'Neural Networks and Physical Systems with Emergent Collective Computational Abilities', Proceedings of the National Academy of Science, USA, 79, pp. 2554-2556.Google ScholarCross Ref
- Kleene, S.C. (1936a), 'General Recursive Functions of Natural Numbers', Math. Annal., 112, pp. 727-742. Reprinted in Davis (1965), pp. 236-253.Google ScholarCross Ref
- Kleene, S.C. (1936b), '¿-definability and Recursiveness', Duke Math. J., 2, pp. 340-353.Google ScholarCross Ref
- Kleene, S.C. (1988), 'Turing's Analysis of Computability, and Major Applications of It', in Herken (1988), pp. 17-54. Google ScholarDigital Library
- Lewis, D. (1971), 'Analog and Digital', Noûs, 5, pp. 321-327.Google ScholarCross Ref
- Morris, P., (1991), 'On the Density of Solutions in Equilibrium Points for the N-Queens Problem', Technical Note TR-M 91-2.Google Scholar
- Penrose, R.; (1989), The Emperor's New Mind, Oxford: Oxford University Press.Google Scholar
- Penrose, R. (1994), Shadows of the Mind, Oxford: Oxford University Press.Google Scholar
- Pitowsky, I. (1990), 'The Physical Church Thesis and Physical Computational Complexity', lyuum, A Jerusalem Philosophical Quarterly, 39, pp. 81-99.Google Scholar
- Post, E.L. (1936), 'Finite Combinatory Processes - Formulation I', Journal of Symbolic Logic, 1, pp. 103-105. Reprinted in Davis (1965), pp. 288-291.Google ScholarCross Ref
- Pour-El, M.B. (1974), 'Abstract Computability and its Relation to the General Purpose Analog Computer', Trans. Amer. Math. Soc., 199, pp, 1-29.Google Scholar
- Pour-El, M.B. and Caldwell, J. (1975), 'On a Simple Definitions of Computable Functions of a Real Variable with Applications to Functions of a Complex Variable', Z. Math. Logik. Grundlagen Math., 21, pp. 1-19.Google ScholarCross Ref
- Pour-El, M.B. and Richards, I. (1981), 'The Wave Equation with Computable Initial Data such that its Unique Solution is not Computable'. Adv. in Math., 39, pp. 215-239.Google ScholarCross Ref
- Pylyshyn, Z.W. (1984), Computation and Cognition, Cambridge, MA: The MIT Press.Google Scholar
- Shagrir, O., (1992), 'A Neural Net with SelfInhibiting Units for the N-Queens Problem', International Journal of Neural Systems, 3, 349-352.Google ScholarCross Ref
- Shapiro, S. (1983), 'Remarks on the Development of Computability', History and Philosophy of Logic, 4, pp. 203-220.Google ScholarCross Ref
- Sieg, W. (1994), 'Mechanical Procedures and Mathematical Experience', in George, A. (ed.), Mathematics and Mind, Oxford: Oxford University Press, pp. 71-114.Google Scholar
- Sosic, R. and Gu, J., (1990), 'A Polynomial Time Algorithm for the N-Queens Problem', SIGART Bulletin, 1, pp. 7-11. Google ScholarDigital Library
- Sosic, R. and Gu, J., (1991), '3,000,000 Queens in Less Than One Minute', SIGART Bulletin, 2, pp. 22-24. Google ScholarDigital Library
- Turing, A.M. (1936-7), 'On Computable Numbers, with an Application to the Entscheidungsproblem', P. Lond. Math. Soc. (2), 42 (1936), pp. 230-265. plus a correction, ibid., 43 (1937), pp. 544-546. Reprinted in Davis (1965), pp. 115-154.Google Scholar
- Turing, A. (1950), 'Computing, Machinery, and Intelligence', Mind, 59, 433-460.Google ScholarCross Ref
- van Heijenoort, J., (1967), From Frege to Gödel: A Source Book in Mathematical Logic 1879-1931, Cambridge, MA: Harvard University Press.Google Scholar
Recommendations
Toward Analog Neural Computation
Computationalism about the brain is the view that the brain literally performs computations. For the view to be interesting, we need an account of computation. The most well-developed account of computation is Turing Machine computation, the account ...
Enumerations of Π10 Classes: Acceptability and Decidable Classes
A @P"1^0 class is an effectively closed set of reals. One way to view it is as the set of infinite paths through a computable tree. We consider the notion of acceptably equivalent numberings of @P"1^0 classes. We show that a permutation exists between ...
Towards practical computable functions on context-free languages
TAMC'06: Proceedings of the Third international conference on Theory and Applications of Models of ComputationMany structures used in computer science and software can be represented by context-free languages. This paper discusses computable functions on such languages, which give a useful model for studies of computability and algorithms involving complex data ...
Comments