David Bourget (Western Ontario)
David Chalmers (ANU, NYU)
Rafael De Clercq
Ezio Di Nucci
Jack Alan Reynolds
Learn more about PhilPapers
Minds and Machines 22 (3):149-165 (2012)
The paper presents an exploration of conceptual issues that have arisen in the course of investigating speed-up and slowdown phenomena in small Turing machines, in particular results of a test that may spur experimental approaches to the notion of computational irreducibility. The test involves a systematic attempt to outrun the computation of a large number of small Turing machines (3 and 4 state, 2 symbol) by means of integer sequence prediction using a specialized function for that purpose. The experiment prompts an investigation into rates of convergence of decision procedures and the decidability of sets in addition to a discussion of the (un)predictability of deterministic computing systems in practice. We think this investigation constitutes a novel approach to the discussion of an epistemological question in the context of a computer simulation, and thus represents an interesting exploration at the boundary between philosophical concerns and computational experiments.
|Keywords||Turing machines Computational irreducibility Computing simulation Undecidability and unsolvability Predictability|
|Categories||categorize this paper)|
Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
|Through your library|
References found in this work BETA
Stephen Wolfram (2002). A New Kind of Science. Wolfram Media.
David Deutsch (1997). The Fabric of Reality the Science of Parallel Universes and its Implications. Monograph Collection (Matt - Pseudo).
Albert R. Meyer & Patrick C. Fischer (1972). Computational Speed-Up by Effective Operators. Journal of Symbolic Logic 37 (1):55-68.
Shen Lin, Tibor Rado, Allen H. Brady & Milton W. Green (1975). Computer Studies of Turing Machine Problems. Journal of Symbolic Logic 40 (4):617-617.
John Helm & Paul Young (1971). On Size Vs. Efficiency for Programs Admitting Speed-Ups. Journal of Symbolic Logic 36 (1):21-27.
Citations of this work BETA
Hector Zenil (2013). What Is Nature-Like Computation? A Behavioural Approach and a Notion of Programmability. Philosophy and Technology (3):1-23.
Similar books and articles
Philippe Huneman (2012). Determinism, Predictability and Open-Ended Evolution: Lessons From Computational Emergence. Synthese 185 (2):195-214.
Yaroslav Sergeyev & Alfredo Garro (2010). Observability of Turing Machines: A Refinement of the Theory of Computation. Informatica 21 (3):425–454.
Benny Shanon (1989). A Simple Comment Regarding the Turing Test. Journal for the Theory of Social Behaviour 19 (June):249-56.
Michael Ramscar (2010). Computing Machinery and Understanding. Cognitive Science 34 (6):966-971.
Stevan Harnad (1989). Minds, Machines and Searle. Journal of Experimental and Theoretical Artificial Intelligence 1 (4):5-25.
John Symons (2008). Computational Models of Emergent Properties. Minds and Machines 18 (4):475-491.
Edwin J. Beggs, José Félix Costa & John V. Tucker (2010). Physical Oracles: The Turing Machine and the Wheatstone Bridge. Studia Logica 95 (1/2):279 - 300.
Gordana Dodig-Crnkovic (2011). Significance of Models of Computation, From Turing Model to Natural Computation. Minds and Machines 21 (2):301-322.
Susan G. Sterrett (2000). Turing's Two Tests for Intelligence. Minds and Machines 10 (4):541-559.
Stevan Harnad (1989). Minds, Machines and Searle. Philosophical Explorations.
Stuart M. Shieber (ed.) (2004). The Turing Test: Verbal Behavior as the Hallmark of Intelligence. MIT Press.
Valerie Gray Hardcastle (1995). Computationalism. Synthese 105 (3):303-17.
Hava T. Siegelmann (2003). Neural and Super-Turing Computing. Minds and Machines 13 (1):103-114.
Jonathan Bentwich (2006). The Duality Principle: Irreducibility of Sub-Threshold Psychophysical Computation to Neuronal Brain Activation. Synthese 153 (3):451-455.
Lukáš Sekanina (2007). Evolved Computing Devices and the Implementation Problem. Minds and Machines 17 (3):311-329.
Added to index2011-11-19
Total downloads9 ( #351,306 of 1,793,093 )
Recent downloads (6 months)1 ( #463,412 of 1,793,093 )
How can I increase my downloads?