Re: Diagonalization (solution-sequel)
Warning, I progressed in my thinking as I responded below, so please
read the whole post before taking time to respond/correct my earlier
paragraphs.
Bruno Marchal wrote:
Le 15-juil.-06, à 02:56, Tom Caylor a écrit :
...
You've written a sort of intuitive code for G above, where you say
generate.
Yes. With Church thesis fortran *is* universal.
Fortran, like Java, Python, Lisp, Diophantine equations, rational
unitary matrices or other rich recursively presented groups, etc...
Chose your favorite one, once and for all. To fiw the idea I take
fortran, and old and venerable programming language.
Those language are grammatically well defined.
So you *can* write a well defined precise (I would even say concrete)
program fortran capable of generating all fortran programs computing
function of one variable. It is enough to write a program which
generate successively all strings of length n, and which filter out
those strings which are not fortran one variable programs.
I gave an intuitive code just for not alarming people with piece of
code, but it should be clear that anyone knowing at least one
programming language, and knowing the notion of alphabetic order on a
finite set of symbols (like the keyboard buttons of a computer) should
be able to write, in that programming language, a program generating
(just generating) successively all the (one variable) programs in that
language. Then by coding finite inputs by natural numbers, you can
think of those programs as computing functions from N to N, or from
subset of N to N.
OK. I'm OK with this if it is just generating the programs. I see
where I was getting wrapped around the self-referential axle by trying
to make the generation program self-aware. But GEN just generates all
programs, so when it gets to itself it just generates the code and
then goes on to generating the next program, totally oblivious to the
fact that it just generated itself.
If you agree with this, you agree with the fact that there is a
program, let us call it GEN, in fortran which generates the sequence of
codes P1 P2 P3 P4 P5 P6 ... Now the partial computable functions are
those functions computed by those programs, and I wrote the sequence of
those functions Fi. That is F1 F2 F3 F4 F5 F6 F7 F8 ...
So GEN, as you said, could be implemented as a program that generates
all possible character sequences and filters out the valid fortran
programs. Perhaps it would do that by running each character sequence
through a fortran compiler (which would be included as part of GEN) and
sees which ones don't end up with a fatal compilation error. I will
call this GENfilter, for reasons below.
begin GENfilter
do for i = 1 to infinity
generate character sequence i
run character sequence i through a fortran compiler
if the result is valid
output character sequence i
else
i = i + 1
end if
end do
end GENfilter
Note that GEN is not in the list {P1 P2 P3 P4 P5 P6 ...} for the non
interesting contingent fact that GEN is a 0 variable program.
But GEN2, defined by GEN2(n) = the code of the nth program in the list,
belongs to the list, given that GEN2 is a one variable program. So
GEN2(1) = P1, GEN2(2) = P2, GEN2(3) = P3, etc.
So if you had all of the programs GEN2(n) for n = 1 to infinity, could
you implement a GEN equivalent to GENfilter, which I will call GENcall
in the following manner?
begin GENcall
do for n = 1 to infinity
call GEN2(n) and output its output (i.e. Pn)
end do
end GENcall
And now, giving that GEN2 is in the list, there is a number k such that
GEN2 = Pk. Nothing magic here. True: GEN2(k) = Pk. Nothing paradoxical
here. GEN2 compute a total function, that is GEN2 on any n gives the
nth programs, and (diagonlaization), on its own indice k it gives its
own code Pk.
OK. Now I agree there's nothing magical about the generation part.
Now *your* G is just defined by G(n) = GEN2(n).
But doesn't G output the range of one of the set of *all* partial
recursive functions, whereas GEN2 outputs the code of a *fortran*
program? So shouldn't it be the following, where execute() actually
executes the fortran program generated by GEN2(n)?
G(n) = execute(GEN2(n))
It will use most
probably GEN as subroutine. I have already send to this list the code
of a GEN2 in LISP.
I guess I was assuming that G would be implemented as the following,
similar to the method of GENcall, but as a one-variable program. My G
would be
begin G(n)
call GEN2(n) and store its output in Pn
execute(Pn) and output its output
end G
Perhaps this is where I am going astray. I wondered why you kept
saying, in order to compute G(k), you have to generate *all* of the
programs for G(1) to G(k) (and then execute G(k)) , whereas if G is
defined as above, you would just call G with input k. I guess in order
to have the code for GEN2(k) available to call, you would have to first
run GENfilter to find out which valid fortran
Re: Diagonalization (solution-sequel)
Tom Caylor wrote: ... Actually, it seems we could do this by writing GEN2 to use GEN's filter method as follows: begin GEN2(n) i = 1 do until i = n generate character sequence i run character sequence i through a fortran compiler if the result is valid output character sequence i else i = i + 1 end if end do end GEN2 Oops, actually it needs to do the following: begin GEN2(n) i = 1 j = 0 do until j = n generate character sequence i run character sequence i through a fortran compiler if the result is valid output character sequence i j = j + 1 end if i = i + 1 end do end GEN2 Tom --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: Diagonalization (solution-sequel)
Le 15-juil.-06, à 02:56, Tom Caylor a écrit :
Bruno Marchal wrote:
Hi Tom,
I will comment your (important imo) first and last paragraph, for
avoiding making the post too much long and technical.
Le 14-juil.-06, à 12:30, Tom Caylor a écrit :
But with Church's Thesis how could it be machine or language
dependent?
Another way of arguing without the + 1 is this: Define G(n) =
Fn(n)
for all n. If G is in the list of Fi's, then G=Fk for some fixed k.
So Fk(n) = Fn(n) for all n. Now if all you're thinking of is a
matrix
of numbers Fx(y) (a lookup table if you will) with rows numbered by
x,
and columns numbered by y, then this doesn't seem problematic (unless
you introduce the + 1). But such a lookup table is infinite and
therefore is not allowed as the code of a computable function. You
need code for the functions Fi. Specifically, you need code for the
function Fk (=G). What does this code look like, even in a universal
sense? Well Fk(n) = G(n) = Fn(n) for all n, so Fk would have to have
some code to compute Fk(1)=F1(1), Fk(2)=F2(2), Fk(3)=F3(3),
...Fk(k)=?,
...
How does Fk *ever* know what to compute for Fk(k)? This is actually
rather funny to me. It's like me being my own grandpa. It seems
that
there already is a case of G(n) not being defined for n=k, even
without
the + 1.
Remember that the Fi are the partial computable function. You can
generate the set of codes, written in some universal language, of all
those functions. To fix the idea I choose often the universal language
fortran, but choose any of your favorite one.
Let us then define, like you propose, the diagonal function G by G(n)
=
Fn(n).
Now the Fn are fortran generable, and they are partially computable.
So
it is easy to write a program computing G:
Begin
read x;
generate (by using the lexicographic order) the code of the Fi up to
the code of Fx;
ouput the result of applying the xth program on x; (or
equivalently compute Fx(x), or just call
the universal function u(x,x) if you recall it).
End
-
Now this is a finite fortran program. So it belongs to the list of
codes of the program Fi, and you can find that code, so you can find
the indice k of the function Fk = G through the explicit program
above.
So, now, you can apply G on k, giving G(k) = Fk(k).
This does not give any information (unlike with G(x) = Fx(x) + 1 where
you get a proof that this G is undefined on its own code). Your G
(where G(x) = Fx(x) could be, or not, defined on its own code).
You've written a sort of intuitive code for G above, where you say
generate.
Yes. With Church thesis fortran *is* universal.
Fortran, like Java, Python, Lisp, Diophantine equations, rational
unitary matrices or other rich recursively presented groups, etc...
Chose your favorite one, once and for all. To fiw the idea I take
fortran, and old and venerable programming language.
Those language are grammatically well defined.
So you *can* write a well defined precise (I would even say concrete)
program fortran capable of generating all fortran programs computing
function of one variable. It is enough to write a program which
generate successively all strings of length n, and which filter out
those strings which are not fortran one variable programs.
I gave an intuitive code just for not alarming people with piece of
code, but it should be clear that anyone knowing at least one
programming language, and knowing the notion of alphabetic order on a
finite set of symbols (like the keyboard buttons of a computer) should
be able to write, in that programming language, a program generating
(just generating) successively all the (one variable) programs in that
language. Then by coding finite inputs by natural numbers, you can
think of those programs as computing functions from N to N, or from
subset of N to N.
If you agree with this, you agree with the fact that there is a
program, let us call it GEN, in fortran which generates the sequence of
codes P1 P2 P3 P4 P5 P6 ... Now the partial computable functions are
those functions computed by those programs, and I wrote the sequence of
those functions Fi. That is F1 F2 F3 F4 F5 F6 F7 F8 ...
Note that GEN is not in the list {P1 P2 P3 P4 P5 P6 ...} for the non
interesting contingent fact that GEN is a 0 variable program.
But GEN2, defined by GEN2(n) = the code of the nth program in the list,
belongs to the list, given that GEN2 is a one variable program. So
GEN2(1) = P1, GEN2(2) = P2, GEN2(3) = P3, etc.
And now, giving that GEN2 is in the list, there is a number k such that
GEN2 = Pk. Nothing magic here. True: GEN2(k) = Pk. Nothing paradoxical
here. GEN2 compute a total function, that is GEN2 on any n gives the
nth programs, and (diagonlaization), on its own indice k it gives its
own code Pk.
Now *your* G is just defined by G(n) = GEN2(n). It will use most
probably GEN as subroutine. I have
Re: Diagonalization (solution-sequel)
Bruno Marchal wrote:
Le 10-juil.-06, à 21:55, Tom Caylor a écrit :
With Church thesis, Fortran is a Universal Language, and a fortran
interpreter is a Universal Machine, where Universal means it
computes
(at least) all computable functions. Fortran programs are recursively
(computably, mechanically, effectively) enumerable, so
G = Fn(n) + 1
is programmable, notably in fortran. So there is fortran code for G
and
it exists in the enumeration
of all fortran programs. So there is a number k such that G = Fk. So
G(k) = Fk(k) = Fk(k) + 1. So Fk(k) cannot be defined and it makes the
Universal Machine run for ever (crash). So, the notorious other
beasts are the *partial* recursive function. They are functions from
*subset* of N, called domain, in N.
OK. I noticed that you can get the Universal Machine (UM) to run for
ever even without the + 1. If I think of the program for G as a big
case statement with cases 1, 2, 3, to infinity, then the case for k
will contain the code for, or better yet a call to (hence the name
recursive?), Fk(k), but if we state by defining even G = Fn(n) (even
without the + 1) then this is equivalent to calling G(k)... But then
when we call G(k) we end up back in the k case again, calling G(k)
again,... forever.
I'm not sure. I'm afraid your argument could be machine or language
dependent.
But with Church's Thesis how could it be machine or language dependent?
Another way of arguing without the + 1 is this: Define G(n) = Fn(n)
for all n. If G is in the list of Fi's, then G=Fk for some fixed k.
So Fk(n) = Fn(n) for all n. Now if all you're thinking of is a matrix
of numbers Fx(y) (a lookup table if you will) with rows numbered by x,
and columns numbered by y, then this doesn't seem problematic (unless
you introduce the + 1). But such a lookup table is infinite and
therefore is not allowed as the code of a computable function. You
need code for the functions Fi. Specifically, you need code for the
function Fk (=G). What does this code look like, even in a universal
sense? Well Fk(n) = G(n) = Fn(n) for all n, so Fk would have to have
some code to compute Fk(1)=F1(1), Fk(2)=F2(2), Fk(3)=F3(3), ...Fk(k)=?,
...
How does Fk *ever* know what to compute for Fk(k)? This is actually
rather funny to me. It's like me being my own grandpa. It seems that
there already is a case of G(n) not being defined for n=k, even without
the + 1.
The key point now, is that the recursively enumerable sequence Fi
give us a sort of coordinate system for reasoning about programs. To
fix some Universal machine or language is the equivalent of fixing
some
reference frame in geometry. And then we can reason in a way which
does
not depend on which Universal Machine has been chosen.
Now Fi denotes just the partial function programmed by the ith fortran
program. So Fi has a domain. It is written Wi. That is: Wi = domain of
Fi.
Exercises:
1) show that
A) all the Wi are recursively enumerable (mechanically generable = in
the range of a total computable function, or empty).
B) all the recursively enumerable sets are among the Wi
I don't have time to word together arguments for all of these, but I
drew pictures. Let's see. Each Wi is a subset of N, so it is easy to
see how each Wi could be in (a subset of) the range (output) of a
function from N to N, so A follows.
You are too much quick here. The set R of codes of total computable
functions is also a subset of N, but this does not entail R is the
range of a total computable function. The diag2 and diag3 already
showed that R cannot be such a range. Oops, I realize I should not have
said in the range of some Fi but the range of some Fi (my fault).
OK. For 1A I'm not sure whether you mean {the whole set of Wi's} is
RE, or each and every {Wi, for a given i} is RE. I think you mean
the first one. I think that we have to use the fact that the set of
Fi's is RE (=the range of a total computable function). However, I
can't see how that would make the set of domains Wi for all i, RE. I
was thinking along the lines of a composition of two total computable
functions would be a total computable function, but it seems that the
Fi's and Wi's apples and oranges, since the Fi's are the (code of?)
functions, and the Wi's are the domains of the Fi's.
Each RE set is a subset of N. But it is not just any subset of N, is
it? Likewise the set of all Wi's cannot be the set of *all* subsets of
N, can it? This would be not enumerable.
Right.
This was trying to address 1B. I have a feeling that all the RE sets
being among the Wi has something to do with the Church Thesis
statement (below) about all partial computable functions being among
the Fi.
2) Conclude that the following version of Church thesis are
equivalent:
A set is intuitively (effectively, mechanically) generable iff it is
recursively enumerable (RE)
This one seems
Re: Diagonalization (solution-sequel)
Le 10-juil.-06, à 21:55, Tom Caylor a écrit : Bruno Marchal wrote: Hi Tom, hi George, I recall the 4 diag problems, and the three solutions already provided. Below, I give the solution of the fourth, and new exercises. Read this with paper and pencil, or don't read it. If you understand, try to explain to someone else (the best test). I went through the 4th one now. I didn't explain it to someone else, but I drew diagrams and tried to construct a mathematical argument for some of the exercises, treating myself as a 3rd person. ;) I'm not finished, and I don't know when I'll get time to really do the rest (Exercise 2). But I can intuitively see the equivalences. And... according to Exercise 2 and the Church Thesis, intuitively is enough! ;) Yes. (About the time take it easy, I can be very slow myself). With Church thesis, Fortran is a Universal Language, and a fortran interpreter is a Universal Machine, where Universal means it computes (at least) all computable functions. Fortran programs are recursively (computably, mechanically, effectively) enumerable, so G = Fn(n) + 1 is programmable, notably in fortran. So there is fortran code for G and it exists in the enumeration of all fortran programs. So there is a number k such that G = Fk. So G(k) = Fk(k) = Fk(k) + 1. So Fk(k) cannot be defined and it makes the Universal Machine run for ever (crash). So, the notorious other beasts are the *partial* recursive function. They are functions from *subset* of N, called domain, in N. OK. I noticed that you can get the Universal Machine (UM) to run for ever even without the + 1. If I think of the program for G as a big case statement with cases 1, 2, 3, to infinity, then the case for k will contain the code for, or better yet a call to (hence the name recursive?), Fk(k), but if we state by defining even G = Fn(n) (even without the + 1) then this is equivalent to calling G(k)... But then when we call G(k) we end up back in the k case again, calling G(k) again,... forever. I'm not sure. I'm afraid your argument could be machine or language dependent. This will happen even if we add the + 1. Personally I like this argument (running forever) better than the 0 = 1 argument that somehow concludes that the UM will crash. A UM crashing to me brings up pictures of physical machines that recognize an unallowed operation, and then stop themselves. Well, until now I identify crashing with running forever. If a UM recognizes an unallowed operation and then stops, I would say bravo to the UM for not having crashed. Note that the fourth diagonalization is really constructive: for any precise specification of any UNIVERSAL machine, you can write a program making that UM crashing (running forever). Note that a total function is a particular case of partial function where the domain subset is N itself. A partial function which is not total will be called a proper partial function. Two direct consequences: 1) insolubility: there is no fortran program capable of distinguishing a code of a total function from a code of a proper partial function. Proof: indeed if such a program exists, we could, from a recursive enumeration of (the code) of the Fi, filter out the code of the proper partial function, and extract a recursive enumeration of the total functions, contradicting each of the two preceding diagonalizations. 2) incompleteness: first a definition: an axiomatizable theory (about numbers, programs) is a generator of true propositions about numbers and programs. A theory is said to be complete if it generate all true propositions about numbers and programs. We have a theorem: there is no complete theory. Indeed, if we did have a complete theory about programs we could prove for each i if Fi is total or proper partial, and we would be able to use this to build a fortran program capable of distinguishing a code of a total function from a code of a proper partial function; and thus contradicting 1) just above. This makes sense. You comment on the Existence thread about why Aristotle choose the substance solution could relate to this. He did struggle with mysteries that come out of self-reference and incompleteness, and perhaps the primacy of substance was his solution. I've read that he discovered the similarity between deduction (propositions to propositions) and inference (true propositions to true propositions), and perhaps substance was his way of attempting to define truth. Perhaps. It is not entirely obvious, because, notably, the greek use the term substance in a different sense than us (in this list). Substance in Aristotle (and the greeks, i.e. Plotinus) refers to primitive. Many late pythagoreans would say that numbers are the primitive substance. So yes, Aristotle, like 1Z (!), seems to have borrow to common sense the idea that what we see is composed by elementary things (continuous and not
Re: Diagonalization (solution-sequel)
Tom Caylor wrote: OK. I noticed that you can get the Universal Machine (UM) to run for ever even without the + 1. If I think of the program for G as a big case statement with cases 1, 2, 3, to infinity, then the case for k will contain the code for, or better yet a call to (hence the name recursive?), Fk(k), but if we state by defining even G = Fn(n) (even without the + 1) then this is equivalent to calling G(k)... But then when we call G(k) we end up back in the k case again, calling G(k) again,... forever. This will happen even if we add the + 1. Personally I like this argument (running forever) better than the 0 = 1 argument that somehow concludes that the UM will crash. A UM crashing to me brings up pictures of physical machines that recognize an unallowed operation, and then stop themselves. And on the surface, it seems that the running forever because of self-reference argument is better because you don't need the + 1. It seems that it isn't the + 1 that makes the UM run forever, and conversely the UM runs forever even without the contradiction of 0 = 1. Tom --~--~-~--~~~---~--~~ 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@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/everything-list -~--~~~~--~~--~--~---
Re: Diagonalization (solution-sequel)
Hi Tom, hi George,
I recall the 4 diag problems, and the three solutions already provided.
Below, I give the solution of the fourth, and new exercises. Read this
with paper and pencil, or don't read it. If you understand, try to
explain to someone else (the best test).
Le 04-juil.-06, à 17:01, Bruno Marchal a écrit :
Hi Tom, Hi George,
I recall the (four) diagonalization problems. I show each time the
diagonal functions, which I will always call g, except for the Fi where
I call it G. In each case the existence of that g proves something
different. I have change r1, r2, r3 ... into R1 R2 R3 ... because rn
looks to much like m in many fonts.
[Apart for Norman and the non-mathematician: please keep this posts,
I will send preliminary posts for you to read before]
Le 22-juin-06, à 17:03, I wrote:
The question is: what does diagonalization prove on those
following list of functions:
0) R1 R2 R3 R4 R5 R6 R7 R8 ...
This is an arbitrary list of functions from N to N (not necessarily
computable one);
g(n) = Rn(n) + 1
All Rn are well defined function from N to N, so all Rn(n) + 1 are well
defined number, and so g is a function from N to N. But g cannot be in
the given (arbitrary) list, and this show that the set of functions
from N to N is not enumerable.
Proof by contradiction.
Indeed, if this was the case, there would be a (precise) number k such
that g = Rk. I will say that k is the index of Rk = g. Let us apply g
on its own index k. In that case g(k) = Rk(k) + 1 = Rk(k). Again Rk(k)
is a precise number, so, by subtraction in the last equality: 1 = 0. So
g does not belong to the list R1 R2 R3 R4 R5 R6 R7 ... Now that list
was arbitrary, so this proved that ALL sequences of functions from N to
N will miss its corresponding g, that is will miss a function from N
to N.
This is the celebrate proof by Cantor of the non enumerability of the
functions from N to N.
Exercise: show that the functions from N to {0,1} are not enumerable,
by a similar proof. Hint: find the appropriate slight change in the
definition of g.
1) h0 h1 h2 h3 h4 h5 h6 ...
This is a list of total computable functions from N to N that we can
generate mechanically (I mean we can generate their codes). It means
that we can generate the codes of each hi, written in some language,
and that, for some reason, we are sure that each hi is total
computable. Examples: Caylor last funny enumeration; all the
(transfinite collection of) sequences of growing functions we have
defined in this thread (since Smullyan Smullyan ...);
g(n) = hn(n) + 1
All hn are well defined function from N to N, and now we are told they
are also computable. And then we are also told that we can generate
mechanically their codes, for example: C1 C2 C3 C4 ... where each Ci
computes the functions hi. (Meaning the program/codes Ci with input n
will gives the result hi(n). In particular all hn(m) can be computed.
Well, this means in particular that I can compute hn(n). Just apply Cn
on n. So obviously, for any n, I can compute hn(n)+1. Just generate the
Ci up to Cn, apply it to n and add one. But this is g(n), and so g is a
computable function from N to N.
But now g cannot belong to the list h1 h2 h3 The hi does not
exhaust the computable functions.
Proof by contradiction.
Indeed if g belongs to that list, then it exists a precise number k
such that g = hk. G would have a program Ck. Let us apply g on its
index k. g(k) = hk(k) = hk(k)+1. Now hk(k) is the result of appying the
program Ck, which computes a total, well defined function, so it is a
number which I can subtract on each side of the last inequality giving
0 = 1.
This show that all mechanically generable set of total computable
functions will miss a total computable functions.
Obviously, the set of total computable function *is* enumerable. We
have just proved that this set cannot be mechanically enumerable.
Logicians says such sets are not recursively enumerable; they write
that they are not RE.
Actually we have show more: such set are constructively not recursively
enumerable. This is because the diagonalization is effective. Given any
attempt to enumerate a set of total computable functions can lead
mechanically to the counterexample. Such sets are called productive.
We have met already three examples of such sets: the set of (code of)
total functions, the set of formal arithmetical truth, the set of all
computable growing functions, etc.
Any RE set approximating such a set can be extended into the
constructive transfinite (reread perhaps the posts on the growing
functions).
2) f0 f1 f2 f3 f4 f5 f6 f7 ...
This is an arbitrary list of *all* total computable functions;
Given that the set of the (code) of the total function is enumerable
(although not *recursively* enumarable), we can use the bijection
between that set and the set of natural numbers to give to such
function the indices 0, 1, 2, 3, ...
Re: Diagonalization (solution)
Le 07-juil.-06, à 07:23, Tom Caylor a écrit :
Exercise: show that the functions from N to {0,1} are not enumerable,
by a similar proof. Hint: find the appropriate slight change in the
definition of g.
Change g to
g(n) = (Rn(n) + 1) mod 2
OK. other solution, change g to
g(n) = 1 - Rn(n)
One way to think about this is to concatenate the output of each Ri and
put a decimal point (actually binary point) in front of it to make a
number between 0 and 1, expressed in binary. Each Ri is arbitrary,
say,
output of R1 = 0.101...
output of R2 = 0.010...
output of R3 = 0.100...
...
OK. Just be careful: 0.0111... and
0.100... are equal. Find the precise correspondence!
but each R1 is infinitely long, since the domain of each Ri is the
natural numbers N (i.e. each Ri is total). If the domain wasn't all
of N, then the diagonalization wouldn't work. Right?
The diagonalization always work, but it will prove something different.
The fourth case will illustrate that.
So
g(1) = (R1(1) + 1) mod 2 = 0
g(2) = (R2(2) + 1) mod 2 = 0
g(3) = (R3(3) + 1) mod 2 = 1
...
and so concatenating these together into a binary number from 0 to 1
gives
output of g = 0.001...
which is different from any of the Ri's. So here we see Cantor's
original diagonal proof of the uncountability of the real numbers
played out in binary.
Indeed.
I have to repeat though that I have misgivings about using infinite
diagonalization to try to conclude things about real-live reality
(physics, mind/body problem).
Remember that I *assume* comp. Like George Levy says: I assume that
there is a level of description of me such that my personal
experience (consciousness) is invariant for digital substitutions made
at that level. And I assume Church thesis, and AR (Number Realism).
We indeed are using the law of the
excluded middle with an infinite sequence.
Er...
We are saying that since g
cannot be any particular one of the Ri's, then g is not in the whole
infinite list. I know that this particular diagonalization is not one
that is used in your argument,
Nice. Indeed. It is a key point.
Actually, with Loewenheim Skolem, Cantor's diagonalization can be shown
to be relative. The notion of non enumerability is relative to a
theory). I guess you hear about Skolem Paradox?
but I think that the same fault is in
the other diagonalizations.
It is up to you to show this, but Church thesis is exactly what makes
the notion of non recursive enumerability absolute.
Godel didn't want to believe in it, but after reading Turing, he called
it an epistemological miracle.
I think it is the comp possibility of nothing least that a
(neo)platonist negative theology, somehow.
Not that this can't be used to argue about
imaginary mathematical play things like the set of real numbers, or
the other creatures that come out of the following diagonalizations,
but how can we say that these things have anything to do with reality?
Some of those diagonalization shows that computer are always
crashable, a fact which can be of some interest for militaries ...
More seriously, it is normal that once we assume comp, computer
science, especially the fundamental one, can say something about us
(in some large sense of us).
Even more especially after the UDA reasoning shows that physics emerges
from 1-comp indeterminacy.
Remember I was just trying to make more concrete Smullyan's heart of
the matter. The key is Church thesis, and then incompleteness, and then
provable (by the machine) incompleteness.
I will show how to translate the 1-indeterminacy in term of
incompleteness through variant of the self-reference modal logic G and
G*.
I know you'll probably say that it's testable, but I have yet to see
it. Diagonalization is not testing. Diagonalization just produces
negative results. Something doesn't exist. How can we test that?
We can't. But I never need to do that. It is only the physical theory
extracted from the comp hyp which can be tested.
How? Well if the comp-physics predict that an electron weight one ton,
we could have to revised comp, ok?
In this post, you don't say that the functions are effectively
computable, just computable. Is effectiveness implied?
Yes. Even without Church thesis all the following term are equivalent:
Turing computable
Post computable
Java computable
Rational unitary matrices computable,
etc.
With Church thesis, they are all equivalent with:
Intuitively computable
effectively computable
In some (intensional) context effectivity could mean more, but to talk
about that now would be confusing. Could say more after the fourth
diagonalization solution. Not today.
I thought
that computable meant just codable as an algorithm, you can program it,
and effective means it also takes a finite amount of time to produce
its output.
No. If there is an output, you always get it in finite time. Could be
long
Re: Diagonalization (solution)
Bruno Marchal wrote:
Hi Tom, Hi George,
I recall the (four) diagonalization problems. I show each time the
diagonal functions, which I will always call g, except for the Fi where
I call it G. In each case the existence of that g proves something
different. I have change r1, r2, r3 ... into R1 R2 R3 ... because rn
looks to much like m in many fonts.
[Apart for Norman and the non-mathematician: please keep this posts,
I will send preliminary posts for you to read before]
Le 22-juin-06, à 17:03, I wrote:
The question is: what does diagonalization prove on those
following list of functions:
0) R1 R2 R3 R4 R5 R6 R7 R8 ...
This is an arbitrary list of functions from N to N (not necessarily
computable one);
g(n) = Rn(n) + 1
All Rn are well defined function from N to N, so all Rn(n) + 1 are well
defined number, and so g is a function from N to N. But g cannot be in
the given (arbitrary) list, and this show that the set of functions
from N to N is not enumerable.
Proof by contradiction.
Indeed, if this was the case, there would be a (precise) number k such
that g = Rk. I will say that k is the index of Rk = g. Let us apply g
on its own index k. In that case g(k) = Rk(k) + 1 = Rk(k). Again Rk(k)
is a precise number, so, by subtraction in the last equality: 1 = 0. So
g does not belong to the list R1 R2 R3 R4 R5 R6 R7 ... Now that list
was arbitrary, so this proved that ALL sequences of functions from N to
N will miss its corresponding g, that is will miss a function from N
to N.
This is the celebrate proof by Cantor of the non enumerability of the
functions from N to N.
Exercise: show that the functions from N to {0,1} are not enumerable,
by a similar proof. Hint: find the appropriate slight change in the
definition of g.
Change g to
g(n) = (Rn(n) + 1) mod 2
One way to think about this is to concatenate the output of each Ri and
put a decimal point (actually binary point) in front of it to make a
number between 0 and 1, expressed in binary. Each Ri is arbitrary,
say,
output of R1 = 0.101...
output of R2 = 0.010...
output of R3 = 0.100...
...
but each R1 is infinitely long, since the domain of each Ri is the
natural numbers N (i.e. each Ri is total). If the domain wasn't all
of N, then the diagonalization wouldn't work. Right?
So
g(1) = (R1(1) + 1) mod 2 = 0
g(2) = (R2(2) + 1) mod 2 = 0
g(3) = (R3(3) + 1) mod 2 = 1
...
and so concatenating these together into a binary number from 0 to 1
gives
output of g = 0.001...
which is different from any of the Ri's. So here we see Cantor's
original diagonal proof of the uncountability of the real numbers
played out in binary.
I have to repeat though that I have misgivings about using infinite
diagonalization to try to conclude things about real-live reality
(physics, mind/body problem). We indeed are using the law of the
excluded middle with an infinite sequence. We are saying that since g
cannot be any particular one of the Ri's, then g is not in the whole
infinite list. I know that this particular diagonalization is not one
that is used in your argument, but I think that the same fault is in
the other diagonalizations. Not that this can't be used to argue about
imaginary mathematical play things like the set of real numbers, or
the other creatures that come out of the following diagonalizations,
but how can we say that these things have anything to do with reality?
I know you'll probably say that it's testable, but I have yet to see
it. Diagonalization is not testing. Diagonalization just produces
negative results. Something doesn't exist. How can we test that?
1) h0 h1 h2 h3 h4 h5 h6 ...
This is a list of total computable functions from N to N that we can
generate mechanically (I mean we can generate their codes). It means
that we can generate the codes of each hi, written in some language,
and that, for some reason, we are sure that each hi is total
computable. Examples: Caylor last funny enumeration; all the
(transfinite collection of) sequences of growing functions we have
defined in this thread (since Smullyan Smullyan ...);
g(n) = hn(n) + 1
All hn are well defined function from N to N, and now we are told they
are also computable. And then we are also told that we can generate
mechanically their codes, for example: C1 C2 C3 C4 ... where each Ci
computes the functions hi. (Meaning the program/codes Ci with input n
will gives the result hi(n). In particular all hn(m) can be computed.
Well, this means in particular that I can compute hn(n). Just apply Cn
on n. So obviously, for any n, I can compute hn(n)+1. Just generate the
Ci up to Cn, apply it to n and add one. But this is g(n), and so g is a
computable function from N to N.
But now g cannot belong to the list h1 h2 h3 The hi does not
exhaust the computable functions.
Proof by contradiction.
Indeed if g belongs to that list, then it exists a precise number k
such that g = hk. G would have a program
Diagonalization (solution)
Hi Tom, Hi George,
I recall the (four) diagonalization problems. I show each time the
diagonal functions, which I will always call g, except for the Fi where
I call it G. In each case the existence of that g proves something
different. I have change r1, r2, r3 ... into R1 R2 R3 ... because rn
looks to much like m in many fonts.
[Apart for Norman and the non-mathematician: please keep this posts,
I will send preliminary posts for you to read before]
Le 22-juin-06, à 17:03, I wrote:
The question is: what does diagonalization prove on those
following list of functions:
0) R1 R2 R3 R4 R5 R6 R7 R8 ...
This is an arbitrary list of functions from N to N (not necessarily
computable one);
g(n) = Rn(n) + 1
All Rn are well defined function from N to N, so all Rn(n) + 1 are well
defined number, and so g is a function from N to N. But g cannot be in
the given (arbitrary) list, and this show that the set of functions
from N to N is not enumerable.
Proof by contradiction.
Indeed, if this was the case, there would be a (precise) number k such
that g = Rk. I will say that k is the index of Rk = g. Let us apply g
on its own index k. In that case g(k) = Rk(k) + 1 = Rk(k). Again Rk(k)
is a precise number, so, by subtraction in the last equality: 1 = 0. So
g does not belong to the list R1 R2 R3 R4 R5 R6 R7 ... Now that list
was arbitrary, so this proved that ALL sequences of functions from N to
N will miss its corresponding g, that is will miss a function from N
to N.
This is the celebrate proof by Cantor of the non enumerability of the
functions from N to N.
Exercise: show that the functions from N to {0,1} are not enumerable,
by a similar proof. Hint: find the appropriate slight change in the
definition of g.
1) h0 h1 h2 h3 h4 h5 h6 ...
This is a list of total computable functions from N to N that we can
generate mechanically (I mean we can generate their codes). It means
that we can generate the codes of each hi, written in some language,
and that, for some reason, we are sure that each hi is total
computable. Examples: Caylor last funny enumeration; all the
(transfinite collection of) sequences of growing functions we have
defined in this thread (since Smullyan Smullyan ...);
g(n) = hn(n) + 1
All hn are well defined function from N to N, and now we are told they
are also computable. And then we are also told that we can generate
mechanically their codes, for example: C1 C2 C3 C4 ... where each Ci
computes the functions hi. (Meaning the program/codes Ci with input n
will gives the result hi(n). In particular all hn(m) can be computed.
Well, this means in particular that I can compute hn(n). Just apply Cn
on n. So obviously, for any n, I can compute hn(n)+1. Just generate the
Ci up to Cn, apply it to n and add one. But this is g(n), and so g is a
computable function from N to N.
But now g cannot belong to the list h1 h2 h3 The hi does not
exhaust the computable functions.
Proof by contradiction.
Indeed if g belongs to that list, then it exists a precise number k
such that g = hk. G would have a program Ck. Let us apply g on its
index k. g(k) = hk(k) = hk(k)+1. Now hk(k) is the result of appying the
program Ck, which computes a total, well defined function, so it is a
number which I can subtract on each side of the last inequality giving
0 = 1.
This show that all mechanically generable set of total computable
functions will miss a total computable functions.
Obviously, the set of total computable function *is* enumerable. We
have just proved that this set cannot be mechanically enumerable.
Logicians says such sets are not recursively enumerable; they write
that they are not RE.
Actually we have show more: such set are constructively not recursively
enumerable. This is because the diagonalization is effective. Given any
attempt to enumerate a set of total computable functions can lead
mechanically to the counterexample. Such sets are called productive.
We have met already three examples of such sets: the set of (code of)
total functions, the set of formal arithmetical truth, the set of all
computable growing functions, etc.
Any RE set approximating such a set can be extended into the
constructive transfinite (reread perhaps the posts on the growing
functions).
2) f0 f1 f2 f3 f4 f5 f6 f7 ...
This is an arbitrary list of *all* total computable functions;
Given that the set of the (code) of the total function is enumerable
(although not *recursively* enumarable), we can use the bijection
between that set and the set of natural numbers to give to such
function the indices 0, 1, 2, 3, ... getting f0, f1, f2, f3, f4,
The preceding reasoning has already shown that such a bijection cannot
be computable, indeed it would make the set of total functions
recursively enumerable. But you can got the contradiction by direct
construction of g, and it is instructive to do so:
g(n) = fn(n) + 1
Does that g belongs to the list of the fi ? Put
