Essay Abstract

We state an extended version of Rice's Theorem for classical formal languages which include elementary analysis and present and briefly comment some of its consequences. Other examples are also discussed.

Author Bio

FAD, Rio, 1945, is professor emeritus at Rio's Federal University. With da Costa he proved that chaos theory is undecidable. Another result: Nash markets in their most general form are also undecidable. Newton C.A. da Costa, Curitiba, Brazil, 1929, developed paraconsistent logics. Both da Costa and Doria have worked together on applied undecidability.

Download Essay PDF File

Dear Francisco Doria and Newton da Costa,

I will have to go through this essay with some care a few times before I can hope to sensibly comment, perhaps with an eye on the referenced works. I have in fact come across your work before, and wanted to understand it better---perhaps this essay will yield the needed impetus to really dig in.

I am particularly intrigued by the connection between undecidability and quantum physics---or rather, the lack thereof, in your terms, as if I understand correctly, you show that there are undecidable systems in classical mechanics, as well, and thus, it is not 'quantum magic' that leads to the emergence of undecidability.

I have been looking at the opposite direction---how undecidability of measurement outcomes, by means of Lawvere's fixed-point theorem, leads to quantum phenomena.

Rice's theorem, of course, can be understood in terms of Lawvere's, as well; I wonder if the same holds true of your extended version, or whether it derives from a different source.

Thank you for a challenging essay!

Kind regards

Jochen

    When I first started this work - in 1990 - my idea (as well as da Costa's) was that the UP in QM as well as chaotic systems were the way to Gödel-Turing in physical systems. That was a quite commonplace conjecture. After a talk I gave at the IMSSS, Stanford, Pat Suppes suggested to me that I should take a look into Richardson's results ``as they dealt with sines and cosines,' and might have to do with QM. That led da Costa and I to a totally different path. It was sort of akin to a suggestion of Kreisel's made in 1975, or even 1962 Scarpellini.

    Your essay was informative, even if it was cryptic in ways. This sets a stage for there being a fundamental level of undecidability.

    If we think of all physics as a form of convex sets of states, then there are dualisms of measures p and q that obey 1/p + 1/q = 1. For quantum mechanics this is p = ВЅ as an L^2 measure theory. It then has a corresponding q = ВЅ measure system that I think is spacetime physics. A straight probability system has p = 1, sum of probabilities as unity, and the corresponding q в†' в€ћ has no measure or distribution system. This is any deterministic system, think completely localized, that can be a Turing machine, Conway's Game of life or classical mechanics. A quantum measurement is a transition between p = ВЅ for QM and в€ћ for classicality or 1 for classical probability on a fundamental level.

    The Hamiltonian H_0 = Оё_0H_1 + (1 - ОёВ¬_0)H_2 seems to capture some aspect of this, where one Hamiltonian is for q = ВЅ and the other q в†' в€ћ or 1. The decidability or Оё_0 separates out two possible outcomes, way if we think of a two state system.

    Cheers LC

    So, the crucial portion of our argument is the explicit obstruction of $theta$, the halting function in the language of Peano Arirhmetic (PA). Given that expression in the language of arithmetic extended theory (PA an axiom that asserts the consistency we can safely formulate the trick with $theta$.

    Sorry for the many mistakes: automatic correctors sometimes get a life of their own...

    The ciorrected paragraph reads:

    ``So, the crucial portion of our argument is the explicit use of $theta$, the halting function in the language of Peano Arithmetic (PA). Given that expression in the language of arithmetic extended theory (PA an axiom that asserts the consistency we can safely formulate the trick with $theta$)

    We can also (with the help pf the explicit construction of $theta$) formulate an axiomatization for computer science as Turing machine theory which develops CS in the guise of Diophantine e

    .

    ... formulate an axiomatization for computer science as Turing machine theory which develops CS in the guise of Diophantine equation theory. And we see that several naïvely true formal sentences turn out to be undecidable sentences in our extended theory. An example:

    ``.There is a set P of intuitively time-polynomial Turing machines which can neither be proved nor disproved as such by our extended theory T.''

    So,some intuitive sets of Turing machines can neither be proved nor disproved to be polynomial Turing machines. It's a selva selvaggia of negative results that are difficult to understand...

    Dear Francisco,

    thanks for your replies. I'm sorry I haven't reacted, but I've been a bit pressed for time lately. I am keenly following, though, and I hope to be able to gather my thoughts and give a bit more of a reply soon.

    Dear Jochen,

    I would very much like to read your comments, criticisms, etc

    2 months later

    unpredictability in computer science,wow. Good statistical essay, something New I learnt from you ,prof.-Rice theorem, will research on that thanks. I have done something on anthropocentric bias in empirical science here that you may Read/rate/review. https://fqxi.org/community/forum/topic/3525.all the best in the essay