In October 1989 I began a sabbatical term at Pat Suppes' lab at Stanford sponsored by a joint Fulbright/CNPq program as a Senior Fulbright Scholar. Before leaving Brazil I had mentioned to Newton that it was my last chance to do some work of interest and later he told me he thought I was raving mad. Yet miracles happen, and a miracle did happen to me while I was at Stanford in 1990.

It went like this: in May 1990 I gave a talk at Suppes' IMSSS seminar on possible candidates for undecidable sentences in physics. The results da Costa and I had at that point were quite unsatisfactory, but Suppes suggested during that talk that I should take a look at Richardson's undecidability results since "as they deal with sines and cosines, they may bear on quantum mechanics." I vividly recall going that afternoon to the math library to look for Richardson's 1968 paper. When I browsed through it it became evident that Richardson's results implied that chaos theory is in fact undecidable, as it follows in a straightforward way from Richardson's constructions, that ergodic theory is undecidable. A few more days of work plus many phone calls to da Costa in Brazil (which of course led to a big phone bill) and we had a first expression for the halting function in computer science as the limit of a succession of integrals. Then da Costa suggested a modification and we got the improper-integral form we first published in the IJTP in 1991.

So far nobody had considered the possibility that the halting function – the function that settles the halting problem in computer science – could be explicitly given a reasonably simple expression in one of the usual mathematical languages.

That led to a – devastating, if I may say so – kind of Rice-like theorem in the realm of classical analysis, and even in arcane domains of mathematics whose impact has yet to be assessed.

Such was the beginning of our collaboration – and of course of our friendship. The contents of this review have been divided into three main sections:

1. The first one discusses our construction of an expression for the halting function in the language of classical analysis plus its consequences. Our main result is the proof of a Rice-like theorem that encompasses most "useful," "interesting" areas in mathematics, and out of it we derive several undecidability and incompleteness theorems.

Common wisdom among mathematicians has that the usual number-theoretic problems are in general much more difficult than "smooth" problems. We showed that this is definitely not the case. We gave an explicit example of a dynamical system where the proof that there will be chaos is equivalent to the proof of Fermat's last theorem (or the proof of Riemann's hypothesis, or the decision of the P vs. NP question). We also proved that (given some conditions) those 'nasty' problems are dense in the space of all dynamical systems.

The language of analysis is assuredly much richer than the language of arithmetic, as we can express the halting function in analysis. Also we can explicitly construct with our techniques "natural"-looking problems which lie beyond the arithmetical hierarchy (see Prop. 1.25).

One of the features of the main set-theoretic forcing constructions is that we add "generic," faceless sets to our formal theories. However there are no explicit expressions for those objects. We informally sketched how to write down an expression for a "faceless" Hamiltonian: the only thing we can prove about it is that it definitely is a Hamiltonian, and nothing more.

2. The next part of the review has to do with our discussion of the P vs. NP problem. We use a Paris-Harrington like argument to deal with it and, given a few simple (quite intuitive) hypotheses for which we offer plausibility arguments, we argue that the formal sentences [P < NP] and [P = NP] are independent of ZFC supposed consistent, and of even stronger axiomatic systems that extend it.

If our conjectures hold, then given those simple and, we stress, rather (apparently) intuitive hypotheses, we get the desired independence result. As a result we will then exhibit a Π2 arithmetic sentence that has a very natural meaning and that will turn out to be independent of a whole sequence of strong formal systems.

3. The remaining sections deal with topics of a more concrete (or perhaps philosophical) flavor, as we discuss game theory and time-structures in general relativity. One of the main results is a theorem that asserts that Gödel-like time structures are so to say the rule, and not the exception, in general relativity.

This review is freely based on the author's work with da Costa, which is quoted at length when we feel that it best suits our purposes. Proofs are sketched whenever needed for the fluency of the argument; if not, they are referred to the original paper.

SUMÁRIO