Title: SUMMARY (was: OM = SIGMA_1)
I send to David Nyman (the 06 Nov 2007) a little planning:
1) Cantor's diagonal
2) Does the universal digital machine exist?
3) Lobian machines, who and what are they?
4) The 1-person and the 3- machine.
5) Lobian machines' theology
6) Lobian machines' physics
7) Lobian machines' ethics
Let me summarize what has been done and what remains to be done.
1) Cantor's diagonal
I tend to consider that the point "1)" is finished. Cantor's argument
is that if there is a bijection between natural numbers, that is: 0, 1,
2, 3, 4, ..., and sequences of numbers, that is a bijection like
0 ----------- 45, 7, 8976, 4, 32, ...
1 ----------- 0, 0, 67, 78, 0, ...
2 ----------- 27, 1, 24, 24, 23, ...
3 ----------- 1, 1, 1, 345, 7, ...
...
then the "antidiagonal" sequence 46, 1, 25, 346, ... cannot be in the
list, because by construction it differs from each sequence in the
list. See below how to make explicit the contradiction.
The reasoning does not depend on the particular sequences exhibited,
and it shows that no enumerable set of sequences can be put in 1-1
correspondence with the natural numbers. The conclusion is that the set
of all sequences of natural numbers is innumerable (not enumerable, not
countable, uncountable, etc. Important concept have many synonym in
math).
Let me recall the same proof, but with usual mathematical notation.
A sequence of numbers, like f_0 =
56, 7897876, 67, 89, 1, 1, 45, ...
is really "just" a function from N to N:
f_0(0), f_0(1) f_0(2), f_0(3), f_0(4), ...
with here: f_0(0) = 56, f_0(1) = 7897876, f_0(2) = 67, f_0(3) = 89,
f_0(4) = 1, etc.
So the bijection above becomes:
0 ----------- f_0 = f_0(0), f_0(1) f_0(2), f_0(3), f_0(4), ...
1 ----------- f_1 = f_1(0), f_1(1) f_1(2), f_1(3), f_1(4), ...
2 ----------- f_2 = f_2(0), f_2(1) f_2(2), f_2(3), f_2(4), ...
3 ----------- f_3 = f_3(0), f_3(1) f_3(2), f_3(3), f_4(4), ...
...
You can see that the diagonal sequence can be described by:
f_0(0), f_1(1), f_2(2), .... f_n(n), ...
Then the "antidiagonal" sequence (function) g is given by
f_0(0)+1, f_1(1)+1, f_2(2)+1, .... f_n(n)+1, ...
That is: g(n) = f_n(n)+1 (definition of g)
Now we can make the contradiction explicit. Suppose that g is in the
list f_i. Then it exists a number k such that g = f_k. This means of
course that for all numbers n we have g(n) = f_k(n). In particular g(k)
= f_k(k). But by the definition of g: g applied on k
= g(k) = f_k(k)+1. Thus (by Leibniz identity rule):
f_k(k) = f_k(k)+1
Now, all f_i are functions from N to N, so they are defined on all
natural numbers, so f_k(k) is a number. We have seen in high school
that identical numbers can be subtract on both sides of an equation
leading to
0 = 1. (contradiction). Thus the f_i cannot enumerate all functions
from N to N. We say:
N^N is innumerable.
This was point "1)". Hope it is ok for every one. Please be sure you
get the point before proceeding.
2) Does the universal digital machine exist?
I recall the informal notion of what is an (intuitively) computable
function (from N to N). Def: A function f from N to N is computable if
we can describe in some formal language L, in a finite way, how to
compute, in a finite time, its value f(n) on each natural number n.
Def. I will call "code of f" such a description of how to compute f.
Def. A language L is said universal if all computable functions can be
described in the language.
Def. A machine is universal if she understands a universal language,
(and thus can indeed compute all computable functions from N to N, at
least in Platonia, where "Platonia" is defined by a place where you can
always ask and get more time and more space/memory: we don't put
deadline to the (universal) machine.
Church thesis is the statement that a universal language (and machine)
exists, and indeed that in particular lambda-calculus provides such a
universal language.
Church's thesis is not obvious. Indeed, when Church "defined" the
computable functions by those capable of being computed by a
lambda-expression (a symbolic expression or code written in the
lambda-calculus), Stephen Cole Kleene thought at first that a reasoning
similar to Cantor's proof of the non enumerability of N^N (see above)
could be made against Church's pretension.
Kleene's reasoning is the following, and works for any pretension that
there is a universal language (so we have not to even define what
lambda-calculus). Indeed, suppose that there is a universal machine and
thus a universal language in which all computable functions from N to N
can be given a code. Now the set of codes in the language L is
enumerable, being a subset of all possible expression written in the
language (which we have seen to be enumerable). Thus there is an
enumeration of all computable functions from N to N
f_1, f_2, f_3, f_4, f_5, f_6, f_7, f_8, f_9, ...
but then the "antidiagonal" function g defined by
g(n) = f_n(n) + 1
is computable, given that each f_n is computable, and that "+1" is a
computable operation. But g cannot be in the list, for the same reason
as above.
Now this cannot be a proof that the set of computable functions is not
enumerable, given that the set of codes is obviously enumerable. So
this looks like a proof by absurdo that there is no universal language,
and thus no universal machine.
The proof, nevertheless is wrong. It did presuppose that the universal
language compute all functions from N to N and only that
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! Indeed to substract f_(k)(k) on both
side of f_(k)(k) = f_(k)(k) + 1, f_k(k) has to be a number!!!!!!!
If f_k(k) is undefined (for example the interpretation by the universal
machine of the code makes the machine non stopping) then the argument
just doesn't go through!!!!
So the possibility that there is a universal language remains intact.
But now we know that the codes written in the possible universal
language could correspond to object which are NOT function from N to N,
but from some subset of N to N. Such "function" are called strictly
partial function: they are not defined on each natural number. Such
function can make the computer crashing (looping, running forever, non
stopping, etc.). So you have to accept the universal machine can crash
if you want her to be able to be universal. As I said: you cannot have
both security and universality. Later security will play a role for the
notion of first person, and universality will play a role for the
notion of third person.
Experimentally, this is what happens for lambda-calculus, FORTRAN,
JAVA, C++, Lisp, SK-combinators, game-of-life, etc. With those language
each corresponding g functions, will indeed crash the corresponding
universal machine (codes, expressions) when applied on their own code.
All known universal language have been shown equivalent: they define
always exactly the same class of computable functions.
From this you can infer immediately unsolvability and incompleteness of
any effective theory about machines (and numbers). Indeed if L is
universal, then you can enumerate the codes (and thus the corresponding
partial functions) written in L:
f_1, f_2, f_3, f_4, f_5, f_6, f_7, f_8, f_9, ...
But here the f_i denotes partial functions. That is a mixture of
strictly partial function and of total functions (partial function
where the domain-definition subset is N itself and thus total = defined
on all n, or put in another way they belongs to N^N.
Absolute unsolvability result:
There is no machine capable of deciding when, given a description of a
code in L, if that code is for a strictly partial functions or a total
partial function.
Proof. If such a code exists then you can used it to extract
mechanically from the enumeration
f_1, f_2, f_3, f_4, f_5, f_6, f_7, f_8, f_9, ...
a "sub-enumeration" of the total partial functions. But then you obtain
an enumeration of all total computable function and only
those!!!!!!!!!!!!
But this leads to a (always the same) contradiction (see above). QED.
(Relative) Incompleteness result.
There is no correct theories about machines in which all statements can
be proved.
Proof: if there was such a theory, you would be able to use it to
construct a machine capable of deciding totality/strict-partiality of
codes in L, contradicting the absolute unsolvability result. QED.
Note in particular that this means that for *any* correct theory T
there will be a particular true statement with the shape "the ith
expression in language L does code a total partial function" which is
undecidable in that theory. This explains why incompleteness is
relative, because in the theory T', which is T'+ (as new axioms) the
preceding true statement, obviously the statement becomes provable in
one line (by a proof saying "see the axiom". There is no equivalent of
Church's thesis for provability!
So you see that the first incompleteness theorem of Gödel is a simple
consequence of Church thesis. Incompleteness is proved by a direct
Cantor diagonalization done in the realm of computable partial
functions.
A question: what if we want, for some reason, be sure the universal
computer will not crash. After all we could ask for security. I will
not answer that question now, but thinking on this question will lead
to a notion of first person, and will give a notion of
sub-universality. Sub-universality is somehow the nearer you can go
near universality without loosing security.
More remains to be said, here of course. In particular, both in this
list and in a course I'm giving at ULB(*) I have begun to provide
example of universal language. It seems to help a lot some students.
- Cutland-Shepherdson-Sturgis coffee-bar language
- SK-combinators
- Diophantine Polynomials
- Robinsonian (and Lobian) Machine
- LISP
Let me summarize roughly the other points:
3) Lobian machines, who and what are they?
Here I have to explain the fundamental nuances between computability
and provability. We have already seen, just above, a very big
difference. For computability we have a "Church's thesis" and thus a
notion of universality, but we have none for provability. Having a
theory, we can always build a more powerful theory. No theories can be
provability-universal.
Now, nothing prevent *some* theory of being computability-universal,
and indeed we can build such a theory from any formal logical
specification of a universal language.
Such specifications will give our "absolute ontic TOE", and defines
the absolute measure on the Observer Moments from which we will derive
the physical laws (just to test such theories with the empirical
facts).
But the physics will not belong to the "absolute ontic TOE". Physics
will appears to belong to the "categorie de l'entendement"' would say
Kant, I mean physics appears as a particular view by internal observers
appearing in the "absolute ontic TOE".
We thus need an observer notion (if only to get the "Observer Moments),
and, as most of you already know, the observer will be the Lobian
Machine. A lobian machine will be a universal machine knowing (in some
weak sense) that she is universal. Such a machine will known to be
incomplete and will (a bit like Hal Ruhl try to say currently to
George) begin to build an (infinite path) toward completion. Much more
on this later.
BTW, Torkel Fraenkel's other book, on inexhaustibility, is a good
introduction for those autonomous progressions (as they are called in
the literature), but we will need only the fact that some modal logics
(the hypostases) remains invariant in those progressions for making the
comp-physics , and all hypostatses, stable and recoverable. More later
...
4) The 1-person and the 3- machine.
They are not the same, and they will fight against each other
"forever". In case you worry: they can make progress so that such fight
is less and less painful, or more and more civilized, that is by
discussing around a table instead than with bombs and bloody war, but
the tension between those two different view is not eliminable. Never,
unless comp is false.
5) Lobian machines' theology
The 1-person and the 3-person (3-machine) are just two arithmetical
interpretation of the Plotinian hypostases. Those who have followed
older posts, or have read my Plotinus paper, knows that there is 8
hypostases. Later we will see that some of those hypostases (=
points-of-view) will still be multiplied, indeed I expect some of them
to lead to some graded algebra describing some quantum computer, ...
For each machine, its arithmetical hypostases defines its theology.
Propositional (self) "theology" is given primarily by the modal logic
G*.
Propositional (self) "science" is given primarily by the modal logic G.
Pure propositional theology is given by G* minus G.
6) Lobian machines' physics
Just particular hypostases corresponding intuitively to the way matter
has to emerge as explained in the universal dovetailer argument.
7) Lobian machines' ethics
Not so difficult, assuming comp. I will indeed only consider the ethics
of the computationalist Lobian machine. One key is that the TRUTH of
"yes doctor" entails the RIGHT of saying NO to the doctor.
Computationalism *is* a religion somehow, and it can explain why it has
to be a "religion", and why it just cannot be used coercively on
people.
Alas, some NON-comp people could not tolerate the comp-people, and
this will give rise to future conflicts, ...
Then computationalism is not (at all) an ethical panacea, and I will
say some word of the type of conflicts occuring (in Platonia) between a
large variety of comp-people.
OK, I send this before putting it in the trash ... I expect to correct
and complete this post slowly but surely, and your remarks could help,
thanks.
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 Jan 18 2008 - 11:04:17 PST