Editora E-papers

Seu carrinho está vazio

capa do livro

Chaos, Computers, Games and Time

A quarter century of joint work with Newton da Costa

Francisco Antonio Doria

1 The Halting Function
- 1.1 The Halting Problem and Gödel incompleteness in S
- 1.2 Finite instances of the Halting Problem
- 1.3 An explicit expression for the Halting Function, I
- 1.4 A Rice–like theorem, I
- 1.5 A more detailed view
- 1.6 A first example of generalized incompleteness; Rice’s Theorem again
- 1.7 Richardson’s map
- 1.8 Richardson’s map: multidimensional version
- 1.9 Richardson’s map: one–dimensional version
- 1.10 Undecidability of the computation of fixed points
- 1.11 The Halting Function, II
- 1.12 Undecidability and incompleteness
- 1.13 Main undecidability and incompleteness result
- 1.14 Undecidability and incompleteness, II
- 1.15 More metamathematical results
- 1.16 Higher–level intractability
- 1.17 First application: chaos is undecidable
- 1.18 Envoi: the Halting Function Theta and Chaitin’s Omega number
2 Hilbert’s 6th Problem
- 2.1 Hamiltonian mechanics
- 2.2 General relativity
3 Some Results
- 3.1 The integrability problem in classical mechanics
- 3.2 The Hirsch problem: the decision problem for chaos
- 3.3 Wolfram’s conjecture and Penrose’s thesis
- 3.4 Arnol’d’s problems
- 3.5 An application to economics: the Tsuji–da Costa–Doria result on Nash games
- 3.6 More undecidability and incompleteness results
4 An Example: Games

4.1 The Tsuji paper: introduction
4.2 Internal and external epistemological questions
4.3 Previous results
4.4 On descriptions of finite sets
4.5 Summary of the paper
4.6 Preliminary concepts and notation
4.7 Undecidability and Incompleteness in T
4.8 Richardson’s functor and the incompleteness of analysis
4.9 Equality is undecidable in LT
4.10 The Halting Function and expressions for complete degrees in the arithmetical hierarchy
4.11 Problems equivalent to some specific intractable problem
4.12 On the incompleteness of theories of noncooperative games
4.13 Undecidability and incompleteness theorems
4.14 Incompleteness of weak theories of noncooperative games
4.15 Finite or in?nite games?
4.16 A blocked backroute or a problem to be found everywhere?
4.17 Finite games: from informal theories to axiomatic ones
4.18 Conclusion
4.19 Two comments

5 Complexity
- 5.1 The formal sentences [P = NP] and [P < NP]
- 5.2 A possible research path
- 5.3 Fast–growing total recursive functions and provability of Π2 arithmetic sentences in formal theories
- 5.4 Why independence?
- 5.5 More notation and preliminary data
- 5.6 Da Costa and Doria 2003
- 5.7 Next effort: two conjectures
- 5.8 A plausibility argument for Hypothesis 5.29
- 5.9 Preliminary results
- 5.10 Conclusion of the first argument
- 5.11 More on the counterexample function
- 5.12 Quasi–trivial machines
- 5.13 Proof of non–domination
- 5.14 Exotic BGSF machines
- 5.15 Still more on the counterexample function f
- 5.16 More conjectures
- 5.17 Some results on fast–growing recursive functions
- 5.18 Construction of function G
6 On Hypercomputer
- 6.1 Prelude
- 6.2 The hypercomputation problem
- 6.3 Structure of the text
- 6.4 Motivation
- 6.5 Style of the text
- 6.6 Hypercomputation theory
- 6.7 From Richardson’s transforms to the Halting Function
- 6.8 Richardson’s map, revisited
- 6.9 Richardson’s map: multidimensional version, revisited
- 6.10 Richardson’s map: one–dimensional version, revisited
- 6.11 The Halting Function revisited
- 6.12 How to build a hypercomputer
- 6.13 Our proposal for a hypercomputer
- 6.14 Can there be a Turing–Fefermann hypercomputer?
- 6.15 Conclusion
7 Time and Space
- 7.1 Time structures
- 7.2 Time structures and broken symmetries
- 7.3 On cosmic time
- 7.4 Exotica
- 7.5 Counterintuitive stuff
- 7.6 Results about the nongenericity of global time
- 7.7 Is cosmic time decidable?
- 7.8 Acknowledgements
8 Envoi
- 8.1 A list of joint papers by da Costa and Doria
- 8.2 Papers
- 8.3 Book chapters
- 8.4 Books
- 8.5 A few references to the joint work of da Costa and Doria