SH: I noticed that a guy named Kevin asked the same question about
characteristic zero and received a technical (to me) answer from Ketan.

http://weblog.fortnow.com/2008/04/ketan-mulmuley-responds.html
#9 ketan says to Kevin, …

(Exercise: Why is that an “NP” question? That is, if a complex number is an integer from 1 to 2ⁿ, why is there a polynomial-size “proof” or “witness” of that fact? You can assume the ability to recognize the constants 0 and 1. Of course, one also needs to prove that the question is “NP-complete” within this world.)

You can also formulate analogous “P versus NP” questions over the integers and the reals.

To address the obvious question, no implications among the various P versus NP questions are currently known. But the general feeling is that P vs. NP over the reals or complex numbers is likely to be easier than P vs. NP over finite fields, and might therefore be an excellent “warmup” to the finitary question that we ultimately care about. Alas, the real and complex cases seem incredibly hard in their own right.

If you want to read more about nonstandard analogues of P vs. NP, the place to go is the beautiful book Complexity and Real Computation by Blum, Cucker, Shub, and Smale. I don’t know if you’ll find the time for it, but I’m almost certain you’d like it.

SH: I was first introduced to the logician John Myhill in Hofstadter’s GEB
and I’ll produce a partial quote of Myhill’s ideas (Impossibility, Barrow).
“In 1952, the American logician John Myhill produced the most interesting
of these. Myhill classified possibilities by borrowing some terminology
from mathematical logic and dividing ideas into three classes: ‘effective’,
‘constructive’, and ‘prospective’. The most accessible and quantifiable
aspects of the world have the attribute of computability. There exists a
definite mechanical procedure for deciding if anything does or does not
possess a particular property. Computers and human beings can be trained
to respond to the presence or absence of such attributes. Truth is not a
computable property, while being a prime number is.

A more elusive set of attributes are those which are merely listable. For
these, we can construct a procedure which will list all the cases that
possess the desired attribute (although you might need to wait for an
infinite time for the listing to be completed). There is, however, no way of producing a listing of all the cases that do not possess the attribute. Many
logical systems are listable, but not computable: all their theorems can be
listed, but there is no mechanical procedure for deciding whether any given
statement is or is not a theorem. In a mathematical world with no Gödel
theorem, every statement would be listable. In a world without Turing’s
uncomputable operations, every property of the world would be computable.”

SH: The “Truth vs. Higher Truth” thread title reminded me that Myhill thinks truth is not computable. I think listable has more to do with P!=NP.
I’ve actually read Seth Lloyds’s description of the universe as a quantum
computer and I’ll assume it’s not that different than Scott’s since his review
of NKS was not all that favorable. Wolfram thinks the universe might be a
simple CA rule unfolding in complexity over billions of years; it displays
pseudo-randomness which is a lack of predictability. Quantum randomness
is conceptually different, there is no pattern, which just can’t be predicted.

Apparently a quantum computer cannot be employed to speed up the process of unfolding a CA rule. Thus we can inspect the computations from within the universe and be unable to distinguish the provenance of
our finite observations of random quantum theory origin from pseudo-random CA rule computation (if one or the other description is correct).
There is no algorithmic operation to transform the “listable” output property
into a computable procedure which distinguishes its origins. One can’t tell
from a finite sequence or digits (or observed events) whether the source
of those digits/events has a random or pseudo-random foundation.
Finishing the quote:
“The problem of deciding whether this page possesses the attribute of
grammatically correct English is a computable one. But the page could still
be meaningless to a non-English reader. With time, the reader could learn
more and more English, so that bits of the page became intelligible, but
there is no way of predicting where the meaningful parts will be located on
the page. The attribute of meaningfulness is thus listable but not
computable.
Not every attribute of things is listable or computable. The property of
being a true statement of arithmetic is an example. Attributes which are
neither listable not computable are called ‘prospective’: they can be neither
recognized nor generated in a finite number of deductive steps.”

SH: This reminded me of the Chinese Room Argument a bit which evoked
the Systems reply. In the comments about Penrose I noticed that the
‘meaning of meaning’ came into question. I think in AI this philosophical
notion often falls under original intentionality vs. derived intentionality.

“Beauty, simplicity, ugliness, and truth are all prospective properties.
Prospective properties are beyond the reach of mere technique. They are
outside the grasp of any mathematical Theory of Everything. That is why
no non-poetic account of reality can be complete.” (Dyson-> poetic level)

Debugging is twice as hard as writing the code in the first place. Therefore, if you write the code as cleverly as possible, you are, by definition, not smart enough to debug it. — Brian W. Kernighan

A fine post. But Scott, there are people who are optimistic, and anyone who thinks they might be right, qualifies as optimistic too.

So you might be closer to optimism than you think.

Incidentally, for those who are curious: I have nothing whatsoever to say about the Israel/Gaza situation that isn’t being said 10⁵⁰⁰ other places on the web. I think it’s horrible that hundreds of civilians are getting killed in Gaza, and also horrible that Hamas will probably soon be firing missiles at Tel Aviv. I hope there will be peace in my lifetime, but am not too optimistic.

Jeffrey Shallit on recursivity has just nominated him for Blowhard of the Month, and I think he has a point.

(http://recursed.blogspot.com/2009/01/blowhard-of-month-freeman-dyson.html)