Book contents
- Frontmatter
- Contents
- Contributors
- Preface
- Acknowledgments
- Introduction
- I Perspectives on Infinity from History
- II Perspectives on Infinity from Mathematics
- III Technical Perspectives on Infinity from Advanced Mathematics
- 4 The Realm of the Infinite
- 5 A Potential Subtlety Concerning the Distinction between Determinism and Nondeterminism
- 6 Concept Calculus: Much Better Than
- IV Perspectives on Infinity from Physics and Cosmology
- V Perspectives on Infinity from Philosophy and Theology
- Index
- References
5 - A Potential Subtlety Concerning the Distinction between Determinism and Nondeterminism
Published online by Cambridge University Press: 07 June 2011
- Frontmatter
- Contents
- Contributors
- Preface
- Acknowledgments
- Introduction
- I Perspectives on Infinity from History
- II Perspectives on Infinity from Mathematics
- III Technical Perspectives on Infinity from Advanced Mathematics
- 4 The Realm of the Infinite
- 5 A Potential Subtlety Concerning the Distinction between Determinism and Nondeterminism
- 6 Concept Calculus: Much Better Than
- IV Perspectives on Infinity from Physics and Cosmology
- V Perspectives on Infinity from Philosophy and Theology
- Index
- References
Summary
The Coding of Information into Time
It is well known that the property of randomness for finite binary sequences based on information content is not decidable (Li and Vitányi 1997). We produce a dramatic version of this, but it is not our goal to simply reproduce this undecidability result; rather, our intention in this chapter is to illustrate a potentially subtle aspect of the distinction between determinism and nondeterminism. This subtlety is the possibility of coding arbitrary information into time in such a way that a specific deterministic process computes precisely that information (as additional output).
Our basic argument begins as follows. Given any specific set of physical laws, we produce a Turing program e0 with the following feature. First, the output of the program e0 (by virtue of its format) must be a finite binary sequence s, but there may be no output generated. Let t be any nonempty finite binary sequence (e.g., flip a quantum coin 10100 times, and let t be the outcome). Then by “extending time” and preserving all the specified physical laws, one can arrange that in the “new” universe the program e0 generates as additional output exactly the chosen string t (so that in the case in which no output was initially generated by the program, in the new universe the total output generated is exactly t; otherwise, the total output generated is exactly s appended by the sequence t).
- Type
- Chapter
- Information
- InfinityNew Research Frontiers, pp. 119 - 129Publisher: Cambridge University PressPrint publication year: 2011
References
- 4
- Cited by