Hi Philip, Hi Bruce, and possible others,
If I remind well, you have defended the idea that mathematics is a language,
and that there is no mathematical reality others that convention of language.
In my opinion, this does not make sense, even without the Church-Turing thesis.
But I realise that with the Church-Thesis, it is easy to understand that the
mathematical reality kicks back in a way enforcing some amount of realism. It
helps also to understand that in computer science, there are many theorems
which are “machine independent” (to use the computer science terminology), and
this means that the results concerns all programming language. That gives
examples of general truth which are independent of the formalism and language
used to express them.
The reason is fundamental, and shows how much incompleteness by itself is an
example where the mathematical, even the arithmetical, reality kicks back:
quite a lot!
I very often present the reasoning which follows. Sometimes my motivation for
it is more limited, to “just” show that the Church-Turing thesis (CT) is …a
thesis, to oppose those who sometimes defend the idea that CT is only a
definition (of what is computable).
Indeed, incompleteness is a direct consequence of CT.
I need you to accept that not set S can have a subset SS with more element that
itself. SS included in S implies that the cardinality of SS is smaller or equal
than the cardinality of S. This is obvious, but with infinite set, we have to
be careful. I will not prove this, and refer you to cantor-Bernstein Theorem,
from which it follows “easily”.
So, in particular, a subset of an enumerable set cannot be a non enumerable
set. OK? I define a set S to be enumerable if it exists a bijection between S
and N (N = the set of natural numbers).
CT is the thesis that a function f from N to N is computable iff f is
computable by an expression in their language (claimed to be universal: they
both agree and have proven that their language are equivalent.
Theorem: CT entails Incompleteness
I need a lemma.
Lemma: The set of finite words build on a finite alphabet is enumerable.
Indeed, take a finite alphabet, like {a, b}, you can enumerate the set of all
finite words by enumerating them simply by their length, and generate
alphabetically the words which have the same length. On the alphabet {a, b},
you get in this way the bijection
0 ———————————— a
1 ———————————— b
2 ———————————— aa
3 ———————————— ab
4 ———————————— ba
5 ———————————— bb
6 ———————————— aaa
7 ———————————— aab
…
The same idea works for any finite set (alphabet), like a …z, aa, ab, … zz,
aaa, aab, ...
Imposing a syntax on the words, like in the alphabet {a, b, =}, would only
diminish the number of words, and an’t augment the cardinality of the set (of
all words on some finite alphabet). That ordering on finite alphabet is called
the lexicographical ordering.
By a (formal) language, I mean the given of an alphabet, and some easily
checkable grammar. An expression is a grammatically correct word.
Now it is easy to give an intuitive, informal definition of what is a
computable function defined on N and with values in N.
The idea is that a function from N to N is computable means that there is an
expression, finite thus and written in some language, explaining how to compute
its values in a finite time, with a finite result.
That makes the set of computable functions from N to N being enumerable.
Now, that looks eminently epistemological? Explaining to Who? How could we be
sure that the functions computable in French are the same than the function
computable by the English? They disagree already on the sign of 0.
Here the idea is that we can decompose the explanation on elementary steps on
which everyone agree that they are indeed quite simple.
The question is, is there a universal language which expressions exist to
compute all computable functions from N to N?
CT asserts yes, and provides precise mathematical candidates.
But even before betting on that answer, we can understand that IF such a
universal language exists, it will have to compute much more than the
computable functions from N to N. It will have to be able to compute also the
functions defined only on subsets of N, and undefined out of that subset. And
worse, the expressions denoting the computable function from N to N, will have
to be ordered in a necessarily non computable way among the expressions in that
universal language.
Imagine (to make a reduction ad absurdum) that L is a universal language
enumerating only the computable functions from N to N. We get a correspondence,
maybe with repetition of the computable functions from N to N, by enumerating
the grammatically correct expression.We get a computable bijection between N
and the computable functions from N to N.
Let us write f_n for the function from N to N computed by nth expression.
Now, the function g defined by g(n) = f_n(n) + 1 is computable, and is defined
on all N. So it is a computable function from N to N. It is computable because
it each f_n is computable, “+ 1” is computable, and, vy our hypothesis it get
all and only all computable functions from N to N.
But then, g has have itself an expression in that universal language, of
course. There there is a number k such that g = f_k. OK?
But then we get that g_k, applied to k has to give f_k(k), as g = f_k, and
f_k(k) + 1, by definition of g.
So f_k(k) = f_k(k) +1.
And f_k(k) has to be number, given that we were enumerating functions from N to
N. So we can subtract f_k(k) on both sides, and we get 0 = 1. CQFD.
If we keep our belief that a universal language exists, it has to compute other
objects, and insert the expressions of the computable functions in a non
computable way (if not you can filter out those other objects, and enumerate
again only (but all) computable functions.
Accepting that the universal language enumerates more than the functions from N
to N saves the situation, the proof above, made on the phi_i (the enumeration
of the mix of functions from N to N and functions from subset of N to N), shows
only that the corresponding function “g” is such that g(k) = phi_k(k) =
phi_k(k) + 1, and in this case it means that phi_k(k) is not defined, and g is
not a function from N to N, but from a subset of N to N. No contradiction, and
CT remains consistent.
This means that, with CT, and thus with the mathematical definition of
computable functions, obtained by CT, the set of computable functions,
although enumerable, is not recursively or computably enumerable. Like for
provability, you have the choice to stay in the “total” domains, with functions
everywhere defined, and extends them in the (constructive) transfinite, or you
can transcend it, but then the partial (defined only on subset) is mixed in a
non computable way, with the total functions, and you are in front of the
unknown: you get situation where you don’t know what the machine is computing.
That shows that any theory capable of talking about those universal languages
and their expressions are irremediably incomplete.
Gödel’s incompleteness mainly uses this showing the Turing universality of
elementary arithmetic, and indeed of the necessary partialness of the
arithmetical provability predicate. This means tat the realism implied by CT
applies to arithmetic. That is what Kleene has made explicit with its Kleene
predicate.
The truth about the behaviour of the expressions, that is the (halting or not)
computations is far larger than what can be proved in any effective theory.
Then, all this is true also for the machine with Oracles, and this makes
possible to study mathematically the degrees of unsolvability of the problem in
arithmetic, and in analysis (descriptive set theory).
There is a bit of more work to prove the unsolvability of the halting problem,
and indeed being the code of a total function is of a higher degree of
unsolvability than the halting problem. I can do that another day.
Gödel, with his own admission, missed CT. After accepting it, he called miracle
the closure of the formalism of computability for the diagonal procedure,
transforming the paradoxes into non stopping machine. The miracle is the
immunity of the notion of computation for the diagonal procedure. It is a bit
like a sort of God has to put those codes in a very complex way among the
digital machines. (In fact the set of such codes is PI_2 complete, equivalent
with qG).
With Indexical Digital Mechanism, (YD + CT), we have a simple ontological realm
(any model of any first order completely theory without induction axioms), and
we get an explanation of why we will still need an infinity of axioms to get
the internal phenomenologies, including the stable measurable sharable quanta
appearances, and the non sharable first person singular qualia experiences.
The digital mechanist thesis makes the dream argument rigorous, and
constructive, and testable, and rather well confirmed by contemporary physics,
up to now.
Strictly speaking invoking a god or a “material universe" at this stage is a
bit premature. With mechanism, this would be like invoking a precise universal
number with a precise oracle, and is at the antipode, needless to say, of the
original “everything” philosophy of this list (supposedly).
Anyone can ask precision. Even what is a function. The beauty of this is that
you dot need any sophisticated mathematics: only finite numbers and words, and
elementary succession of simple action/relation.
Bruno
--
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 view this discussion on the web visit
https://groups.google.com/d/msgid/everything-list/32EBA174-B326-423B-91B8-63AC14348218%40ulb.ac.be.
