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 

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 
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 

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

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 
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 
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 
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 
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, 


You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 

Reply via email to