On 10 Jun 2009, at 20:17, Jesse Mazer wrote: > > > From: marc...@ulb.ac.be > To: everything-list@googlegroups.com > Subject: Re: The seven step-Mathematical preliminaries > Date: Wed, 10 Jun 2009 18:03:26 +0200 > > > On 10 Jun 2009, at 01:50, Jesse Mazer wrote:
> > >Such an hypercomputer is just what Turing called an "oracle". And > the haslting oracle is very low in the hierarchy of possible oracles. > And Turing results is that even a transfinite ladder of more and > more powerful oracles that you can add on Peano Arithmetic, will > not give you a complete theory. Hypercomputing by constructive > extension of PA, with more and more powerful oracles does not help > to overcome incompleteness, unless you add non constructive ordinal > extension of "hypercomputation". > This is the obeject of the study of the degrees of unsolvability, > originated by Emil Post. > > > Interesting, thanks. But I find it hard to imagine what kind of > finite proposition about natural numbers could not be checked simply > by plugging in every possible value for whatever variables appear in > the proposition...certainly as long as the number of variables > appearing in the proposition is finite, the number of possible ways > of substituting specific values for those variables is countably > infinite and a hypercomputer should be able to check every case in a > finite time. Countably infinite does not mean recursively countably infinite. This is something which I will explain in the "seventh step thread". There is theorem by Kleene which links Post-Turing degrees of unsolvability with the shape of arithmetical formula. With "P" denoting decidable predicates (Sigma_0) we have ExP(x) Sigma_1 (mechanical) AxP(x) Pi_1 ExAyP(x,y) Sigma_2 AxEyP(x,y) Pi_2 etc. This will defined countably infinite set which are more and more complex, and which needs more and more non-mechanical procedures. You can intuitively understand, perhaps, that "to be the coded" of an halting procedure (Sigma_1) needs less "hypercomputation" than "to be the coded of an everywhere defined procedure, which is Sigma_2. > Does what you're saying imply you can you have a proposition which > somehow implicitly involves an infinite number of distinct variables > even though it doesn't actually write them all out? The complexity grows up even when you restrict yourself to a finite number of variables. By the theorem of Kleene, the complexity comes from the alternation of the quantifiers. > Can all propositions about arbitrary *real* numbers (which are of > course uncountably infinite) be translated into equivalent > propositions about whole numbers in arithmetic? Here you are jumping from arithmetical truth to analytical truth. In principle analytical truth extends the whole arithmetical hierarchy. So the correct answer is "no". But this is for "arbitrary analytical truth". By a sort of miracle, the analytical truth that we met in the everyday practice of analysis can be translated in arithmetical proposition. A well known example is the Riemann's hypothesis which is equivalent to a Pi_1 arithmetical proposition. I have personally stopped to believe in the relevance of analytical truth in the ontology. Epistemologically, it is not difficult to build arithmetical relation such that you need analytical devices to solve them. A bit like higher cardinal in set theory can provide light in combinatorial problems in braids and knots theory. > Or am I taking the wrong approach here, and the reason a > hypercomputer can't decide every proposition about arithmetic > unrelated to the issue of how many distinct variables can appear in > a proposition? > It is related to the number of variables, but the hierarchy grows up without necessitating to go beyond finite number of variables. The interesting story about the degree of complexity of "hypermachines" happens between the recursively countable and the less and less recursively countable, and they are all captured by formula with finite number of variables. I hope I will be able to put some light on this in the seventh step thread, or in some possible AUDA thread in the future. The quantified "guardian angel", that is the modal logic G* extended with the quantifier, is already "undecidable" even in the presence of an oracle for the whole arithmetical truth. Even a "GOD" or "hypermachine" capable of answering all Sigma_i and Pi_i questions can still not answer general provability question bearing on a machine. The arithmetical "second Plotinian God", that is Plato's NOUS, or intellect, is already beyond the reach of the first Plotinian God (the ONE, or arithmetical truth). No machine can make a complete theory of what machine can and cannot do. When the complexity of machine go above the treshold of universality, they are faced with an intrinsically huge complexity. Machines can understand themselves only very partially. They can progress by transforming themselves in more powerful (with respect to provability) machines, but by doing so, they augment their complexity. Bruno http://iridia.ulb.ac.be/~marchal/ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Everything List" group. To post to this group, send email to everything-list@googlegroups.com To unsubscribe from this group, send email to everything-list+unsubscr...@googlegroups.com For more options, visit this group at http://groups.google.com/group/everything-list?hl=en -~----------~----~----~----~------~----~------~--~---
