Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site ucbvax.BERKELEY.EDU Path: utzoo!watmath!clyde!burl!ulysses!ucbvax!brahms!weemba From: weemba@brahms.BERKELEY.EDU (Matthew P. Wiener) Newsgroups: net.ai,net.philosophy Subject: Re: A halting problem: a meaty response Message-ID: <11452@ucbvax.BERKELEY.EDU> Date: Sun, 19-Jan-86 07:37:37 EST Article-I.D.: ucbvax.11452 Posted: Sun Jan 19 07:37:37 1986 Date-Received: Tue, 21-Jan-86 00:54:49 EST References: <2175@aecom.UUCP> <14551@rochester.UUCP> <3978@kestrel.ARPA> Sender: usenet@ucbvax.BERKELEY.EDU Reply-To: weemba@brahms.UUCP (Matthew P. Wiener) Distribution: net Organization: University of California, Berkeley Lines: 94 Xref: watmath net.ai:3195 net.philosophy:3848 Summary: someone's light hearted summary is pedantically corrected In article <3978@kestrel.ARPA> ttp@kestrel.ARPA writes: >The question of whether or not people are capable of solving the >Halting problem in general (which, as people have abundantly shown, is >equivalent to solving your favorite outstanding mathematical problem) Not so. Of course, everyone did reply with Fermat's great conjecture, but that is solely because it is so short and famous. However, solving Fermat's conjecture does not solve the halting problem! >does not seem amenable to a rational answer. NO is a rational answer. See me rationalize below. > Sure there are hard >problems, but cleverer people pop up over the centuries and solve some >of the outstanding problems, but then the remaining problems are >harder, etc. That etc. is the topic of this response. There are problems now known which are believed forever insoluble. In set theory, there are questions of the form is ZFC + X consistent? (ZFC is the most common axiomatization of set theory, X is some statement one is interested in.) The statements X one considers are various combina- torial/large cardinal questions. It would not be hard to right a program to loop through all sequences of logical deductions that follow from ZFC+X, and halt upon getting 0=1. What is interesting is that the statements studied have fallen into a nice linear hierarchy. That is, there are natural Xs, say X1, X2, ... with (ZFC+X1)'s consistency following from ZFC+X2, whose own consistency follows from ZFC+X3, etc. This was all predicted by Godel, but his statements were always ones which had a naturally agreed upon truth value. Thus ZFC does not prove that ZFC itself is consistent, but everyone agrees that it is consistent (with a few demented exceptions). And then everyone agrees that the extended axiom system ZFC + "ZFC is consistent" is itself consistent, etc. No matter how many times you repeat this Godelization (finite or infinite) everyone still agrees that the resulting system is consistent. What the statements X1, X2, do, however, is transcend this simple iteration, leading to more and more powerful set theories. The question is: At what point do you get inconsistency? If X135 is inconsistent, then the trivial program mentioned above can find out for us, and presumably the mathematical community will find out on its own anyway. But if it is consistent, then how would we ever find out??? Again, as soon as we leave the simple Godeliz- ations, we enter a new and rather queasy mathematical uncertainty. The first several levels are generally considered tame, the next tolerable, then they get rough, and the highest levels are considered quite dangerous, whose true believers form a cult (it is even centered in LA!). (There are, I should mention, various heuristic reasons given for their reasonablenesses. But that is the best one can ever do apparently.) But now comes the amazing part. The questions are not just relevant to one particular branch of mathematics. There is a theorem due to Matiyasevich which allows one to effectively turn the set theoretic questions into partic- ular number theoretic questions. The putative proofs of ZFC + X implies 0=1 correspond to putative solutions to a certain Diaphontine equation. That is, there are explicit equations (the smallest ones known have ~25 variables), for which the question of whether they have integral solutions falls in that spectrum of uncertainty mentioned above. In fact, it is quite conceivable that certain problems like Fermat's (or even his conjecture itself!) are of this form. Thus, if we consider, not the Fermat loop, but a poly_X loop, where poly_X is a Matiyasevich-derived polynomial corresponding to axiom X, we get a very troublesome situation. When X is one of the tamer propositions, I can assert that I, and much of the set theory community believes that the poly_X loop never halts, but so what? Has our human mind, because of its clever study of the more powerful statements, realized that X is tame enough, and so it knows(?) that the loop halts? That is a rather weak sort of solution, and falls apart as one climbs the consistency strength hierarchy. And are there alien minds whose fundamental mathematical intuition just SEES some ZFC + X is true the way we see ZFC is true? (Or even some human minds?) (As an aside, the C in ZFC stands for the axiom of choice. That axiom had a rather turbulent acceptance period historically, but it is now nearly universally accepted. How much have our minds changed in a hundred years?) The room for unanswerable speculation is very wide here; I find the very existence of this provably more-and-more-uncertain hierarchy the clincher in the question of whether the human mind can zap every infinite loop. > I suspect that I at least am not capable of solving >every problem (such humility). There's no need to suspect! :-) As Bertrand Russell once noticed, if one first defines a religion as a body of beliefs depending on faith, then not only is mathematics a religion, it is the only religion that goes about proving that it is a religion. ucbvax!brahms!weemba Matthew P Wiener UCB Math Dept Berkeley CA 94720