On 11 Jun 2009, at 21:43, Jesse Mazer wrote:
> >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.
>
>
> Ah, that makes sense--I hadn't thought of combining multiple
> universal quantifiers in that way, but obviously you can do so and
> get a meaningful statement about arithmetic that for a mathematical
> realist should be either true or false.
Even for just an arithmetical realist. (All mathematicians are
arithmetical realist, much less are mathematical realist. I am not an
arithmetical realist).
Of course some "exotic" philosopher could pretend they are not
arithmetical realist, but this is near non sense for me.
>
> 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.
> 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.
> for example, an omega-order oracle machine can tell you whether any
> finite-order oracle machine halts, an omega-plus-one-order oracle
> machine can tell you whether any finite-order oracle machine halts
> *or* whether an omega-order oracle machine halts, and so forth. So I
> assume from what you're saying above that even an omega-order oracle
> machine would not be able to decide the truth value of every
> proposition about arithmetic just by checking cases...if that's
> right, what would the propositions it can't decide look like? It
> can't just follow the pattern you showed above of adding more
> universal quantifiers, since it has to be a proposition of finite
> length.
Indeed, but variable can represent infinite object, like in analysis.
From the point of view of computability, infinite set of natural
number, or functions from N to N, can play the role of the real numbers.
>
> I've also read that countable ordinals themselves can be classed as
> either "computable" or "noncomputable" (which makes sense since I'm
> pretty sure you can come up with a formalism where every possible
> countable ordinal is associated with a countable symbol-string,
> although the same ordinal might have multiple valid ways of
> expressing it as a symbol string since order doesn't matter in sets,
> so this doesn't help with the problem of whether the cardinality of
> the set of all distinct countable ordinals is the same as the
> cardinality of the set of all distinct real numbers, i.e. all
> distinct countable symbol-strings). So, there is a first countable-
> but-noncomputable ordinal, written as omega_1^CK (where _1 refers to
> a subscript and ^CK refers to a superscript),
Yes. And CK is for "Church and Kleene. You can see omega_1^CK as the
least non recursive ordinal. Omega_1 (aleph_1) is the least non
countable ordinal. Of course omega_1^CK is much smaller than Omega_1.
And with the continuum hypothesis Omega_1 is 2^aleph_0.
> 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.
> Would there be finite propositions about arithmetic that even this
> fantastical device could not decide?
This can depend of which "path" you will follow going through the
constructive ordinals, and yes some path define "fantastical device"
capable of answering all arithmetical questions. Obviously, this
correspond to anything but machines! But yes, with comp those objects
makes non sense form the third person point of view, but still are
needed to figure out the first person points of view.
>
>
> 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.
>
>
> What do you mean by "analytical devices" in this context? Something
> like a type of hypercomputer more powerful than any countable-
> ordinal-level hypercomputer?
I don't think so. But such "hypercomputer" will make use of those
countable but non recursive ordinal. With uncountable oracles
everything becomes "trivially" computable. You can code in some
arbitrary "real number" all solutions to any problem in math (not just
in arithmetic).
Analytical means that the variable can be real number (or arbitrary
sets), but the oracles remain countable, but not necessarily recursive
(or computable).
Very difficult question Jesse! Fortunately, we will not have to go
through the analytical hierarchy, except perhaps to follow those who
will succeed in solving the "measure problem", if that happens
someday ...
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 Fri Jun 12 2009 - 09:31:46 PDT