A Portrait

The distinguished-looking gentleman slowly assesses the audience that fills up the auditorium and wryly smiles. He is of medium height, with closely-cropped hair where amid the white strands one can still find the fair color of his youth. He wears large glasses that barely hide his olive-colored eyes. He dresses informally, in an unremarkable way.

He looks in the middle sixties; it is April 7, 2008, and he will soon start his lecture to the students and faculty massed at Coppe's main lecture hall. Professor Newton da Costa looks a bit over sixty; he will turn 80 in 2009.

Da Costa again surveys the audience, and starts talking. The tone is conversational; he delivers his lecture in a peripathetic way, while marching to and fro. He jokes with the audience from time to time. The talk is deep; yet, its tone is always amusing and refreshing, lighthearted. At the end of it the audience stands up in a single movement and starts a Niagara of applause.

Newton da Costa is the foremost latin-american logician. He is best-known for his development of paraconsistent logics and their applications, but his interests range from foundational issues in the sciences to applications of his ideas in the realm of artificial intelligence. A former professor of mathematics and of philosophy at USP and Unicamp, Newton da Costa is a member of several top-ranking scientific associations such as the celebrated Institut International de Philosophie, in Paris, and, in Brazil, the Brazilian Academy of Philosophy.

The audience that applauded him enthusiastically at the end of his lecture did so to thank Newton da Costa for a wonderful talk, but also to honor an important, influential scientist of our times. The present collection of essays wishes to honor Newton da Costa on his coming 80th anniversary.

SUMÁRIO

Contents

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.

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