# The Computability-Theoretic Content of Emergence

*S. Barry Cooper*

No 1113, ASSRU Discussion Papers from ASSRU - Algorithmic Social Science Research Unit

**Abstract:**
In dealing with emergent phenomena, a common task is to identify useful descriptions of them in terms of the underlying atomic processes, and to extract enough computational content from these descriptions to enable predictions to be made. Generally, the underlying atomic processes are quite well understood, and (with important exceptions) captured by mathematics from which it is relatively easy to extract algorithmic con- tent. A widespread view is that the difficulty in describing transitions from algorithmic activity to the emergence associated with chaotic situations is a simple case of complexity outstripping computational resources and human ingenuity. Or, on the other hand, that phenomena transcending the standard Turing model of computation, if they exist, must necessarily lie outside the domain of classical computability theory. In this article we suggest that much of the current confusion arises from conceptual gaps and the lack of a suitably fundamental model within which to situate emergence. We examine the potential for placing emer- gent relations in a familiar context based on Turing's 1939 model for interactive computation over structures described in terms of reals. The explanatory power of this model is explored, formalising informal descrip- tions in terms of mathematical definability and invariance, and relating a range of basic scientific puzzles to results and intractable problems in computability theory

**Date:** 2011

**References:** View complete reference list from CitEc

**Citations** Track citations by RSS feed

**Downloads:** (external link)

http://www.assru.economia.unitn.it/files/DP_1_2011_II.pdf (application/pdf)

**Related works:**

This item may be available elsewhere in EconPapers: Search for items with the same title.

**Export reference:** BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text

**Persistent link:** http://EconPapers.repec.org/RePEc:trn:utwpas:1113

Access Statistics for this paper

More papers in ASSRU Discussion Papers from ASSRU - Algorithmic Social Science Research Unit

Contact information at EDIRC.

Series data maintained by assru.tm@gmail.com ().