capa do livro

On the Foundations of Science (LIVRO)

Essays, First Series

Newton C. A. da Costa e Francisco Antonio Doria


Chaos is undecidable
First step in the da Costa-Doria research program dealt with a question formulated by Morris Hirsch in 1983: do we have an algorithmic procedure to test whether a given dynamical system will turn out to be chaotic? The answer is no, no matter the definition we may concoct for chaos – it is enough that such a definition isn't trivial.
As summarized by Smale in a slogan, we show: chaos is undecidable.
The proof stems from a very general result, a version of computer science's Rice Theorem within the language of elementary classical analysis, that is, the language of physics. As related results we obtain several undecidability results in classical mechanics. The corresponding incompleteness theorems are also stated and proved.

On Penrose's Thesis
Penrose claims in his book The Emperor's New Mind that classical physics admits no metamathematical phenomena. He actually voices an old conjecture, that quantum mechanical phenomena are some kind of counterpart to undecidability and incompleteness.
We show here that Penrose's claim doesn't hold.

Forcing in physics
We now go back to the axiomatization of physics and to Boolean-valued models and forcing models and their impact on physics.
Results that might bear on Shannon's Theorem are discussed here.

As difficult as Fermat
Are there mathematical questions whose proof turns out to be as difficult as the proof of Fermat's Last Theorem? Or, say, of Riemann's Hypothesis? The answer is – yes, there are infinitely many such questions.
This is discussed and proved in the ensuing paper.

Arnol'd's problems, I
Given a dynamical system which has an equilibrium point at the origin, can we algorithmically decide whether that equilibrium is stable or unstable? The answer is no: here one proves it for dynamical systems in a language that includes elementary functions.
The question had been formulated by Arnol'd in 1974.

Arnol'd's problems, II
We exhibit here a proof that Arnol'd's question is undecidable for a restricted case, autonomous dynamical systems over the polynomials with rational coefficients.
This settles the full Arnol'd Problem on the decidability of equilibria.

The social sciences
Which are the consequences of the preceding results for the social sciences? We discuss the matter here, and sketch a proof of a theorem originally conceived by M. Tsuji on the undecidability (and incompleteness, for axiomatic versions) of Nash equilibria in finite games.
The result on the undecidableNash games and on Arrow-Debreu markets is given here.

Summing it up
Summing it up: a review paper that discusses the preceding results.

Exotic P vs. NP, I
The paper on the “exotic” formulations for the P vs.NP question.

Exotic P vs. NP, II
This much longer paper coauthored with E. Bir presents evidence that supports our “exotic” approach to P vs. NP.

Another much-debated matter: our discussion of computation theory beyond the Turing barrier.

Veja também

capa do livro

Análise de Dados Composicionais

Uma abordagem aplicada e computacional no ambiente R

Luis Paulo Vieira Braga

capa do livro

A geografia trágica em Nietzsche

Carlos Alberto Franco da Silva