On 10 Jun 2009, at 20:17, Jesse Mazer wrote:
>
>
> From: marchal.domain.name.hidden
> To: everything-list.domain.name.hidden
> 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.domain.name.hidden
To unsubscribe from this group, send email to everything-list+unsubscribe.domain.name.hidden
For more options, visit this group at
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Thu Jun 11 2009 - 14:04:17 PDT