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
-~----------~----~----~----~------~----~------~--~---

Reply via email to