Empirical Encounters with Computational Irreducibility and Unpredictability

Minds and Machines 22 (3):149-165 (2012)
  Copy   BIBTEX

Abstract

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.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 76,168

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

A simple comment regarding the Turing test.Benny Shanon - 1989 - Journal for the Theory of Social Behaviour 19 (June):249-56.
Computing Machinery and Understanding.Michael Ramscar - 2010 - Cognitive Science 34 (6):966-971.
Minds, machines and Searle.Stevan Harnad - 1989 - Journal of Experimental and Theoretical Artificial Intelligence 1 (4):5-25.
Computational Models of Emergent Properties.John Symons - 2008 - Minds and Machines 18 (4):475-491.
Turing's two tests for intelligence.Susan G. Sterrett - 1999 - Minds and Machines 10 (4):541-559.
Minds, machines and Searle.Stevan Harnad - 1989 - Journal of Theoretical and Experimental Artificial Intelligence 1:5-25.
Computationalism.Valerie Gray Hardcastle - 1995 - Synthese 105 (3):303-17.
Neural and super-Turing computing.Hava T. Siegelmann - 2003 - Minds and Machines 13 (1):103-114.

Analytics

Added to PP
2011-11-19

Downloads
18 (#614,279)

6 months
1 (#448,551)

Historical graph of downloads
How can I increase my downloads?

Author Profiles