> On 19 Dec 2018, at 00:43, Jason Resch <[email protected]> wrote:
>
>
>
> On Tue, Dec 18, 2018 at 6:00 AM Bruno Marchal <[email protected]
> <mailto:[email protected]>> wrote:
>
>
> That will give all computations, including the one responsible for you
> consciousness state here and now. But that is only a tiny part of the
> explanation, as physics as o be retrieved from the first person indeterminacy
> on all computations going through your state in the universal dovetailing
> (aka the sigma_2 arithmetical true sentences).
>
>
>
> Hi Bruno,
>
> Could you tell me (or point me to a definition of) what "sigma_2"
> arithmetical true sentences are? What is their relation to sigma_1 sentences?
A proposition, or sentence, in the language of arithmetic (Logic + {0, s, +,
*}) is any proposition provably (in PA, say) equivalent to a formula with shape:
ExP(x, y)
with P decidable (recursive, sigma_0). That corresponds to the partial
computable functions, or to the recursively enumerable set.
If “P” is complex enough, such a proposition is sigma_1 complete, and it means
that all problems with shape sigma_1 can be reduced to a solution of ExP(x, y),
with that P.
A sigma_1 complete set is Turing-complete or Turing-universal. It is basically
equivalent to a universal Turing machine. Exemple: the set of theorem of RA,
PA, ZF, ….
Now, the negation of a sigma_1 proposition is pi_1, and can always be put in
the shape:
AxP(x, y)
Indeed: ~ExP(x, y) is equivalent with Ax~P(x, y). And P is recursive, so ~P is
recursive too. That correspond to the first unsolvability class (the halting
problem is pi_1, like Riemann hypothesis, Fermat theorem, etc.). Their negation
is partial computable (sigma_1)
Similarly, sigma_2 is a proposition with shape:
ExAy P(x, y, z)
P is still supposed to be sigma_0. A sigma_2 proposition is more unsolvable
that a pi_1 proposition. Here too, a sigma_2 proposition can be sigma_2
complete (and all sigma_1 proposition va-can be reduced to it).
Again, the negation of a sigma_2 proposition is a pi_2 sentences, And they are
more complex than the sigma_2 sentences.
As you guess, a sigma_n proposition is ExP(x, …) with P being pi_n
And a pi_n proposition is AxP(x, …) with P being sigma_n.
In arithmetic, a sequence of quantifiers of the same kind (E or A) can be
contracted into one quantifier by using some bijection between N and NxNx … xN,
like ExEyP(x, y) = EzP(left(z), right(z)).
By taking the union of all sigma_i and pi_i sentences, you get the Arithmetical
Truth, the set of all true proposition whose complexity defies imagination,
except that the Arithmetical Hierarchy (the sigma_i/pi_i hierarchy) can be
extended in second order logic, where we allow variable for sets and/or
functions), and that gives a similar analytical hierarchy. It behaves less
well than the arithmetical hierarchy, and does not concern much Mechanism (it
can play a role in the machine’s phenomenology though).
Exemple: take any universal machinery phi_i (ask me if you need more on this),
and its corresponding w_i, that is, w_i is the domain of phi_i. The w_i can be
shown to enumerate also the range of total (or partial non empty) computable
functions, and are called “recursively enumerable set”, or”mechanically, or
computably, enumerable set.
Typical exemples are
K = {x such that phi_x(x) converge} = {x such that x belongs to w_x }. K is
sigma_1 complete (!).
K_1 = {x such that W_x is not empty}. K_1 can be shown to be sigma_1 complete
too.
FIN = {x such that w_x is finite}. FIN can be shown to be sigma_2 complete.
INF = (x such that w_x is not finite} INF is pi_2 complete. Like
TOT = {x such that phi_x is total} = {x such that w_x is N}. TOT is pi_2
complete
CON = {x such that phI_x is a constant total function}. CON is pi_2 complete
qG = {x such that x is the Gödel number of a theorem of quantified
self-reference logic}, again, that is a pi_2 complete set. (qG* is vastly more
complex, it is pi_1 complete in the oracle of the Arithmetical truth!}
The following
COF = {x such that W_x is cofinite}
REC = {x such that W_x is recursive}
EXT = {x such that phi_x is extendible to a total computable function}
Are all sigma_3 complete.
Those sets are called index sets, that is that if x belongs to such a set, it
will contain all y such that phi_y = phi_x.
A typical exemple is
FACTORIAL = {x such that phI_x = the factorial function}.
FACTORIAL will contain all programs (or their Gödel number) which computes the
factorial function.
The complexity of any index set can be shown to be always above or equal to the
complexity of K, unless they are equal to { }, or to N. This means that
FACTORIAL is not a computable or recursive set, and that means that there is no
mechanical procedure to see if an arbitrary program computes factorial or not.
The predicate or attribute “being a machine computing the factorial function”
is not decidable. That seems impressive, but is rather normal, as you can
imagine with a program running absurdly complex subroutine, like searching a
proof of the Syracuse conjecture in ZF + KAPPA, and if it finds it output n x
(n-1) + … *1. If being a code for factorial was decidable, we could decide
complex conjecture automatically in ZF.
Hope this helps a bit. It is part of recursion theory, aka computability theory
(although it should have been called theory of non computability and
unsollvability. All the interest in having a precise definition of computation
is that it gives us a mean to study the degree of unsolbability, and the
structure of the universal machine intrinsic ignorance with respect to the
arithmetical truth, and beyond. (It is already “theology” in disguise).
OK? Feel free to ask question.
Bruno
>
> Jason
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "Everything List" group.
> To unsubscribe from this group and stop receiving emails from it, send an
> email to [email protected]
> <mailto:[email protected]>.
> To post to this group, send email to [email protected]
> <mailto:[email protected]>.
> Visit this group at https://groups.google.com/group/everything-list
> <https://groups.google.com/group/everything-list>.
> For more options, visit https://groups.google.com/d/optout
> <https://groups.google.com/d/optout>.
--
You received this message because you are subscribed to the Google Groups
"Everything List" group.
To unsubscribe from this group and stop receiving emails from it, send an email
to [email protected].
To post to this group, send email to [email protected].
Visit this group at https://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/d/optout.
