Stephen, Liz,
On 18 Jan 2014, at 00:02, LizR wrote:
On 18 January 2014 11:39, Stephen Paul King <[email protected]
> wrote:
Dear John,
I invite your comment on a statement and question: There is not
observable difference between "X is non-computable" and "there does
not exist sufficient resources to complete the computation of Y".
Are X and Y effectively the same thing, everything else being
equal? If there is a difference that makes a difference, what might
it be?
In other words, is anything non-computable because of some
theoretical reason, rather than "merely local geographical" ones
(which might cease to be restrictions if, say, our local even
horizon expands, or we construct wormholes to other universe) ?
Surely the halting problem?
Of more easily the totality problem. It is more complex than halting,
and thus more easily shown to be non computable.
Let me do it here, as I promise to Stephen. It is almost a direct
consequence of Church thesis.
I recall that a function (from N to N) is said TOTAL computable if you
can explain in a finite set of words, in one formal language, with a
decidable simple grammar, how to compute it on each (cf TOTAL) natural
numbers, in a finite time, and this to a sufficiently dumb person.
Church's thesis: there is a universal language L in which all TOTAL
functions can be described/coded, and my language "lambda calculus" is
such a language.
Theorem: Church's thesis entails that L describes more than just all
TOTAL functions.
Proof: suppose that L describes only the TOTAL functions. We can
lexicographically order all programs in L (due to the clear decidable
grammar) p0, p1, p2, p3, .... Let us call f_i the function computed by
p_i
Then we can define a function g such that g(n) = f_n(n) + 1. Indeed we
can even program it in L. (To compute it on n, generate the list up to
p_n and apply p_n on n, then add 1. As all f_n are total, this gives a
total function (everywhere defined on N).
So that function g as some program p_k, and thus compute some function
f_k belonging to the list (L is universal).
But then, let us apply g on its own code k, we have g(k) = f_k(k),
given that g = f_k.
But we have also that g(k) = f_k(k) + 1, by definition of g. So f_k(k)
= f_k(k) + 1.
And, by totality, f_k(k) is a number. So I can subtract it from both
side in the preceding equality, and we get
0 = 1. Contradiction.
So either L is not universal (and Church is wrong), or f_k(k) is not
defined, and f_k is not total.
Then if you look in "lambda calculus", you can empirically observe
that f_k(k) is indeed not defined: p_k does not stop on k. Making
Church thesis consistent.
So if Church thesis is true, and if some language L is truly
universal, the list of its programs p_i will go through all total
computable functions (by universality), but will also go through many
NON TOTAL functions.
And, the key point, you will not been able to use any program to
distinguish the code of the total function from the code of the non
total one.
Why? Because if that was the case, you would be able to filter out the
non total function from the list of all programs p_i, and you would
get a computable enumeration (list) of all, and only the total
functions, and the diagonal above would again conclude that 0 = 1.
So the attribute of a code "computing a total function" cannot be
computable. QED.
OK? (you have to read this with pencil and paper!)
This was a constructive proof, leading to a meaningful predicate
("TOTAL") being not computable.
Thi entails a strong form of incompleteness: no effective theory (with
checkable proofs) can ever decide if some arbitrary code is the code
of a total, or not, function.
(Note that a far easier, but non constructive and less informative,
proof is given directly by Cantor theorem. The computable functions
are codable, making them enumerable, but N^N, the set of all functions
from N to N is NOT enumerable by Cantor theorem.
So almost all functions from N to N are not computable.)
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 post to this group, send email to [email protected].
Visit this group at http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
http://iridia.ulb.ac.be/~marchal/
--
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 http://groups.google.com/group/everything-list.
For more options, visit https://groups.google.com/groups/opt_out.
