Papers (math physics, logic, computer science, foundations of science) + violon d'Ingres texts on genealogy
Papers & other texts by Francisco Antonio Doria - with thanks to Lawrence Ferlinghetti :))
Papers (math physics, logic, computer science, foundations of science) + violon d'Ingres texts on genealogy
My name is Francisco Antonio Doria, or Francisco Antonio de Moraes Acciaioli Doria. I was born in Rio, Brazil, in 1945; got my B.S. in chemical engineering (from Rio's Federal University) in 1968, and my PhD in mathematical physics under the guidance of mathematician Leopoldo Nachbin at the Brazilian Center for Research in Physics (CBPF, 1977).
I am currently a Professor of Communications, Emeritus, at Rio's Federal University. I'm attached to the Production Engineering Program at that university through its Fuzzy Sets Lab and Advanced Studies Group. I am also a member of the Brazilian Academy of Philosophy. (To contact me use the link.)
I have collaborated with Newton da Costa since 1986. Together we have discovered many examples of undecidability and (Gödel) incompleteness in mathematics, physics and mathematical economics.
The idea behind the 2003 paper is simple. We define a formal sentence noted [P=NP]* that is intuitively the same as P=NP but such that (consistent) ZFC can neither prove nor disprove the equivalence [P=NP]<—>[P=NP]*. Moreover one has:
(We give a variant of the omega-consistency conditional result in the 2003 paper, which is much less straightforward than the above statement.) That result is in the line of well-known previous results by DeMillo, Lipton, Maté and others.
Can we go beyond that? da Costa and I have recently finished a paper whose title is explicit enough: “Hypotheses that imply the ndependence of P=NP from strong axiomatic systems,” soon to be posted here.
We've - Newton da Costa and I - only followed the trail of folklore, which is very rich in this area. We first learned that P<NP or P≠NP (or P=! NP) can be formalized as a ∏-2 sentence, roughly, “for every polynomial Turing machine there is an instance of a satisfiable Boolean expression - binarily coded - so that the machine will fail to output a correct satisfying line of truth-values for the input.” (The binary coding for the Boolean expression is quite straightforward and ‘natural,’ and we suppose that there is a recursive enumeration for the polynomial Turing machines - see below.)
Nearly everybody thinks that P<NP can be proved, say, in Peano Arithmetic (PA). Therefore given such a formalization as above we must consider the counterexample function (the map : poly machine ---> first failed instance of a satisfiable Boolean expression). If that function grows faster (in its peaks) than any PA-provably total recursive function, then P<NP cannot be proved in PA. Follows the consistency of PA + P=NP (where P=NP is the negation of P<NP).
OK, but - the thing isn't so easy as stated. First of all, the set of all time-polynomial Turing machines isn't recursive at all. We can use an ersatz family of poly machines, the so-called BGS set (for Baker-Gill-Solovay) of coupled Turing machines plus a polynomial clock. The BGS family has the following properties:
We can formulate P<NP over the BGS set, and form the counterexample function over BGS.
Now it is somewhat easy to show that the full counterexample function (over all poly machines) overtakes in its peaks any naïvely total recursive function. (Actually its peaks grow at least as fast as the Busy Beaver Function.) But how about the counterexample function over the BGS set? Well, here comes the big surprise: if [P<NP]* notes a ∏-2 sentence that naïvely translates the desired concept, but such that we can show that the associated counterexample function grows faster than some given set of total recursive functions (bounded by an explicitly given naïvely total recursive function; I know this is vague, but I'm just trying to give the key idea), then the equivalence [P<NP] <--> [P<NP]* turns out to be independent of several rather strong axiomatic systems! For instance, if we take ZFC (supposed consistent) to be our formal background, then for a reasonable [P<NP]* we have that [P<NP] <--> [P<NP]* is independent of ZFC!
We also easily prove the following two results: for consistent PA,
(Roughly; I'm not being rigorous here - just trying to give an idea of what's going on.) That is: prove independence and you'll prove the truth of P<NP. The question we are now pursuing is: given a consistent ZFC, we know that:
Now [P=NP]* is the same as P=NP in the standard model. If ZFC proves [P=NP]*, then we are done, for the equivalence [P=NP] <--> [P=NP]* holds in the standard model. But if it doesn't prove the sentence, the above theory only holds in models for ZFC with nonstandard arithmetic, and the desired interpretation for [P=NP]* may not hold - the equivalence [P=NP] <--> [P=NP]* may then break down (I can give later more details on that). So, the question becomes:
However... you'll see that if you try to prove independence, several (apparent?) paradoxes creep up. That's why this problem is so fun :))
Newton da Costa and I were trying to show (as we actually did in 1990) that chaos theory is undecidable. Chief tool we developed was a function explicitly written in the language of calculus whose values were algorithmically undecidable. Only after we had reached our main goal did we notice that such a function (actually the expression for such a function) was an explicit expression for the Halting Function in Turing machine theory. It sort of `codes' an analog computer - an idealized analog computer, we must stress - that settles the Halting Problem for an universal Turing machine. Can it be implemented with nuts & bolts & electronic circuitry?
I don't know - but if it doesn't work, there are other possibilities, for sure.
Hilbert's 6th Problem is the ugly duckling among the 23 Hilbert problems. It deals with the axiomatization of physics, and most researchers basically agree that no solution for it will ever be of practical, or general interest. Newton da Costa and I had to axiomatize portions of physics in order to prove incompleteness theorems about mechanics etc. We used a general procedure, which is as good as any alternative axiomatization technique, at least for our goals.
Recently Cris Calude edited a beautiful collection of essays in honor of Greg Chaitin, Randomness and Complexity, World Scientific, 2007. We contributed a paper on H6, which you can find here.
The starting point was quite simple: once my friend Roberto Moreira made a side-remark in one of his electromagnetism classes, that the Maxwell equations could be written in a Dirac-like form. I was intrigued, went home and opened up the Maxwellian system into its component equations; the result came up quite naturally. I then noticed that the linearized Einstein equations, and also the full Einstein system, can be written in the same form. Well, this is quite well-known, I later learned, since the paper where Bargmann introduced what we know as the Bargmann-Wigner equations and since a 1960 paper by Penrose on the spinorial formulation for General Relativity. My contribution has been to formulate everything in a simple, compact, algebraic formalism. We proceed with the Lagrangian density as if it were a standard scalar lagrangian density - formal operations, which do work but which at that time I didn't really bother to put upon a firm footing.
Newton and I had long believed that chaos theory was undecidable and incomplete, namely that there would be no algorithm to test a dynamical system for chaotic behavior and that there would be an incompleteness counterpart to such an impossibility. Things fell into place when Pat Suppes told me about Daniel Richardson's 1968 paper on the limits to the algorithmic manipulation of algebraic expressions. So it turned out that the result we had been looking for was part of a much more general phenomenon; moreover Richardson's results led to an explicit expression for the Halting Fuction within the language of classical analysis. Here you can find Ian Stewart's review of our work.
If you wish to relax by going through a cloak-and-dagger-like family tale that ends in 19th century bourgeois respectability (and if you read Portuguese), then you should be interested in this text.
When I go to Europe people sometimes ask me about my family's connections with the historical Genoese Doria family. Here is the link: - a pedigree of the Costa Doria family in Brazil.
The 10th century family of the Lords of Maia, a region in northern Portugal, is of obvious Arab descent. My contention is that they were Idrissid princes. Before you disagree with my viewpoint please do download my text and ponder it.
Descendants of the da Maia family are legion; I believe that the whole western world can (ideally at least) trace a line to the Maia clan. Besides several friends who helped me a lot with documents, references, etc, I must stress my great debt to Marshall Kirk in the preparation of that text.
If you wish to read (in portuguese) my own personal memories — memories with a slightly Proustian flavor — the link is here.