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

Veja também

capa do livro

Inovação social e sustentabilidade

Desenvolvimento local, empreendedorismo e design

Roberto Bartholo e Carla Cipolla (orgs.)

capa do livro

Diálogos.África.Brasil

Uma plataforma colaborativa para a inovação social

Roberto Bartholo, Ivan Bursztyn e Carla Cipolla (Orgs.)