From: marchal.domain.name.hidden
To: everything-list.domain.name.hidden
Subject: Re: The seven step-Mathematical preliminaries
Date: Thu, 11 Jun 2009 14:04:17 +0200
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_1ExAyP(x,y) Sigma_2AxEyP(x,y) Pi_2etc.
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.
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. You can go even past finite-order oracle machines into oracle machines for higher ordinals too...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.
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), which means we should also have a notion of an omega_1^CK-order oracle machine. Would there be finite propositions about arithmetic that even this fantastical device could not decide?
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?
Jesse
--~--~---------~--~----~------------~-------~--~----~
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 - 15:43:34 PDT