On 12 Jun 2009, at 20:31, Jesse Mazer wrote:
> >Even for just an arithmetical realist. (All mathematicians are
> arithmetical realist, much less are mathematical realist. I am not
> an arithmetical realist).
>
>
> I assume you meant to write "I am not a mathematical realist"?
Yes.
> OK, but this leads to a further question. I remember from Penrose's
> book that he talked about various levels of oracle machines
> (hypercomputers)--for example, a first order-oracle machine was like
> a Turing machine but with an added operation that could decide in
> one step whether any Turing program halts or not, a second-order
> oracle machine was like a Turing machine but with operations that
> could decide whether a Turing machine program *or* a first-order
> oracle machine program halts, and so forth.
>
>
>
> >Hmm... let us say "OK" (but this could be ambiguous). This gives
> mainly the arithmetical hierarchy when you start from the oracle for
> the halting problem. There are relativized hierarchy based on any
> oracle, and then starting from the halting problem in that oracle.
> The degrees are structured in a very complex way.
>
>
> I don't know the meaning of the phrases "arithmetical hierarchy" or
> "relativized hierarchy", is there any simple way of explaining? In
> any case, the problem I am mainly concerned with is the set of all
> propositions that would be considered well-formed-formulas (WFFs) in
> the context of Peano arithmetic (so it would involve arithmetical
> symbols like + and x as well as logical symbols from first-order
> logic, and they'd be ordered in such a way that the symbol-string
> would express a coherent statement about arithmetic that could be
> either true or false). Is there some way to come up with a rule that
> would allow you to judge the true or falsity of *every* member of
> this set of propositions using some kind of sufficiently powerful
> hypercomputer (presumably a fairly powerful one like the 'omega-
> order oracle machine' or beyond), just by checking every possible
> value for the numbers that could be substituted in for variable
> symbols? That would allow us to make sense of the distinction
> between "truths about arithmetic" and "statements about arithmetic
> provable by some axiomatic system like the Peano axioms" (the issue
> Brent Meeker was talking about in the post at http://www.mail-archive.com/everything-list.domain.name.hidden/msg16562.html
> ), without having to worry about the "meaning" that we assign to
> arithmetical symbols like the number "2", or about philosophical
> questions about where our understanding of that meaning comes from.
I think you are asking something impossible. The notion of elementary
aritmetical truth will always be simpler than the notion you need to
define the hypercomputer. Just Gödel's incompleteness theorem
justifies in an transparent way the separation between truth and
provability in such or such formal theory. The arithmetical hierachy
is the one I was describing with the sequence of alternation of
quantifiers starting from decidable formula. That hierarchy does
indeed described a sequence of "hypermachine" (because each level
posses a Sigma_i or Pi_i completeness notion, which generalize the
notion of universality for machine-with-oracle. I will have some
opportunity to describe notion even more powerful. But only (with
Church thesis) the Sigma_1 universality has an effective universal
counterpart, represented by any computer, or universal language
interpreter.
> Instead we'd have a purely formal definition about how to judge the
> truth-value of WFFs beyond those the Peano axioms can judge,
Remember that PA+"consistent PA" is uncomputably more powerful than
PA. And ZF set theory is much much more powerful than PA, ...
This is something I will have to explain, at least for AUDA, but in
all those discussions we have to distinguih the notion of
computability (which is universal and does not depend on the choice of
formalism), with the notion of provability which is formalism dependent.
And then we can generalize the notion of computability, and even of
provability.
Humans provability is generally considered as much larger than PA
arithmetic.
> albeit one that cannot actually be put into practice for arbitrary
> propositions without actually having such a hypercomputer (but for
> some specific propositions like the Godel statement for the Peano
> axioms, I think we can come up with an argument for why the
> hypercomputer should judge this statement 'true' as long as we
> believe the Peano axioms are consistent, so in this sense defining
> arithmetical truth in terms of such a hypercomputer is
> *conceptually* useful).
The whole incompleteness phenomena bears on all notion of
hypercomputations. I prefer to call "hypercomputers" Gods or angels,
and both humans and machines can accelerate their work by invoking
them. The notion of real numbers are based on such notions. It is an
open problem if we really needs those God to do mathematics, but
everyone agree they simplified life considerably, like infinities in
analysis, etc. Eventually such existence question is related to the
relation between first and third points of view.
>
>
>
> You can go even past finite-order oracle machines into oracle
> machines for higher ordinals too...
>
>
> >This leads to the hyperarithmetical hierarchy and/or analytical
> hierarchy, where you consider formula with variables for functions
> or sets. There are many non trivial theorems which relate those
> notions (and open problems, but I have not follow the recent
> developments). Imo, the best book on that subject is still the book
> by Rogers.
>
>
> Again, I'm only interested here in the type of propositions that
> would be judged WFFs in the context of the Peano axioms, and I think
> in this case the variables only refer to particular numbers, right?
> Or is it possible to write a WFF in this context where the variables
> refer to "functions or sets"?
Yes, that is second order logic. And the theories of set have been
invented for doing higher order logic in a pure first order way. In
recursion or computability theory this leads to the analytical
hierarchy. Naïve math is of infinite or indeterminate order.
>
> Like you I am an arithmetical realist but not necessarily a realist
> about arbitrary sets.
I can be, but by distinguish levels.
> I think it may be problematic to talk about sets that are so big
> that most of their numbers have no finite description, as must be
> true of any uncountable set. If there is no *rule* which maps
> countable ordinals to real numbers and which can be described in
> finite terms by a humanlike being, for example, then is it really
> meaningful to ask whether or not a completely incomprehensible
> mapping exists between these two sets? I'm not so sure, and thus I'm
> not sure whether I believe there is any "real truth" about the
> Continuum Hypothesis.
OK. It is a very difficult subject. I am a long way from having any
definite opinion. Even assuming comp.
> which means we should also have a notion of an omega_1^CK-order
> oracle machine.
>
>
> >You are quick here! There are more than one way to make this precise.
>
>
>
> More than one non-equivalent way to make it precise, so that a
> number computable by one version of an "omega_1^CK-order oracle
> machine" might not be computable by another version? Of course even
> with ordinary Turing machines, there are multiple ways to design the
> internal state-changing rules for the machine, such that different
> Turing machines might respond to the same input string
> differently...still if a given output is computable by one universal
> Turing machine it should be computable by any other, so they are all
> "equivalent" in that sense. If we define the "order" of oracle
> machines in the sense I discussed (so that the third-order oracle
> machine can decide whether the first- or second-order oracle
> machines will halt given any input string of the type that could be
> given to a Turing machine, and so forth), then even if there could
> be different input-output relations for an oracle machine of a given
> "order", would the set of outputs "computable" by differently-
> designed oracle machines of that particular order not be
> "equivalent" in a similar sense?
There are many hierarchies there, and many results which would be
difficult to describe in any short way. I hope I can give later more
information.
The important result is that the "order defined by oracle for the
halting problem, the totality problem, and similar can be associated
with the Pi-i and Sigma_i hierarchy of alternation of quantifiers?
Then all that -hierarchy can itself be relativized on any oracle. Like
you can define the Phi_i^A, and their domain W_i^A. The Phi_i^A are
the partial functions from N to N that you can compute with a
universal machine "in connection" of the oracle A.
The whole of recursion theory can be lifted in such "machines". But
their rôle can only be "technical" for a computationalist. Of course
they could be of interest fro some A-computationalist. But those have
not yet appear, except in the sense of taking our data as an oracle.
But this should be avoided, I would say by definition, in any
scientific enterprise, it would leads to a confusion between necessary
and contingent.
You should study books on unsolvability, like those by Shoenfield, or
Rogers, if those questions interest you.
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 Sun Jun 14 2009 - 16:17:04 PDT