Empirical Encounters with Computational Irreducibility and Unpredictability

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)
DOI 10.1007/s11023-011-9262-y
 Save to my reading list
Follow the author(s)
My bibliography
Export citation
Find it on Scholar
Edit this record
Mark as duplicate
Revision history Request removal from index
Download options
PhilPapers Archive

Upload a copy of this paper     Check publisher's policy on self-archival     Papers currently archived: 16,667
External links
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

Add more references

Citations of this work BETA

Add more citations

Similar books and articles
Benny Shanon (1989). A Simple Comment Regarding the Turing Test. Journal for the Theory of Social Behaviour 19 (June):249-56.
Stevan Harnad (1989). Minds, Machines and Searle. Journal of Experimental and Theoretical Artificial Intelligence 1 (4):5-25.

Monthly downloads

Added to index


Total downloads

9 ( #254,415 of 1,726,249 )

Recent downloads (6 months)

1 ( #369,877 of 1,726,249 )

How can I increase my downloads?

My notes
Sign in to use this feature

Start a new thread
There  are no threads in this forum
Nothing in this forum yet.