Undecidability and Incompleteness are Everywhere

Francisco Antônio Dória

Coppe
University of Rio de Janeiro, Brazil

We prove a version of Rice's Theorem for the language of classical analysis. Main points are a construction of explicit expressions for the halting function (the function that settles the halting problem) in the language of classical analysis, and extensions of those results to all complete arithmetic degrees. We extend these results to incompleteness results for several axiomatic systems.

Main topics to be covered:

• Suppes predicate axiomatics for portions of physics.
• Solution of Hirsch's Problem: is there an algorithmic decision procedure for chaotic systems?
• Solution to Arnol'd's 1974 Hilbert Symposium Problems: is there a decision procedure for the nature of equilibrium - stable or unstable - for autonomous polynomial dynamical systems?
• Proof of the undecidability of Nash games and applications to economics.

Bibliography

N. C. A. da Costa and F. A. Doria, ``Janus-faced physics,'' in C. Calude, ed., From Leibniz to Chaitin, World Scientific 2007. 

P.Suppes, Representation and invariance of scientific structures, CSLI, Stanford, 2002

M.Tsuji, N. C. A. da Costa and F. A. Doria, The incompleteness of theories of games. J. Philos. Logic 27 (1998), no. 6, 553--568..