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 already send to this list the code
of a GEN2 in LISP.
You can prove nothing with it. Like if an inhabitant of the Knight
Knave Island tell you "I am a Knight" It could be true (Knight always
tell the truth) or a lie (Knaves always lie).
*My* function G is defined by G(n) = GEN2(n) +1.
And given that we have already program GEN2, it is a child play to
modify the program computing your G into mine: just add the instruction
"+ 1" at the right place.
Now, in case that G would be a total function, we would be in a
situation analog with what happens if you meet a inhabitant of the
Knight Knave Island saying "I am a Knave", a total impossibility (if a
knave says it it would tell the truth which a knave never does, and a
Knight will never say the falsity "I am a knave". It is the "+ 1" which
force the G function to be wrong in all case you give her its own
indice, as we have seen.
> But if G = Fk, then when we go to explicitly write the
> code for G, when we get to "generate the code for Fk" what to we write?
GEN generates all the codes. Like if I count 0, 1, 2, 3, .... without
ever stopping (in platonia) soon or later (actually later!) I will get
some of my correct Godel number describing me at the right level of
description. I will not be aware of that, but this is not the point.
GEN generates algorithmically, mechanically, "fortranically" all the
fortran codes. If you doubt this can be done, the best is that you
write the code for yourself.
> Fk *is* G. So we start generating G from the beginning until we again
> get to the part "generate the code for Fk" and then we do this forever.
>
> It's sort of like at dinner when I ask my son or daughter what they did
> today, and they tell me everything they did starting with "I woke up
> and made my bed...", and jokingly they finally say, "...and then sat
> down for dinner and told you, 'I woke up and made my bed...' ..." But
> of course they finally stop and laugh, instead of going forever.
Something similar happens with the universal dovetailing. But here we
use just the program generating part of the dovetailing. Your G as
mine, applied to n, does compute directly, without dovetailing the
value Fn(n) or Fn(n)+1 (cf Fn is the function computed by the program
Pn).
>
> This is where I'm stumped. You say that we escape the diagonalization
> and the program runs forever (because 0 is not equal to 1). I'm trying
> to get a firm handle on what is actually going on here.
You are right to do so. Understanding the (effective, programmable)
diagonalization of the Fi, is needed to proceed. It shows that IF
Church thesis is correct so that the Fi contains all the total
computable functions (that is the Pi contains all the codes of the
total computable functions) THEN the code of the total function is
necessarily HIDDEN in the Fi. No algorithmic procedure capable of
distinuishing the Pi computing total comp. function from the Pi
computing the proper partial one will ever exist. As I shown this shows
quickly both insolubility and incompleteness.
> Is there some
> intuitive definition that is causing an ambiguity, just like the
> definition of a function itself, as in my previous post?
I don't think there is anything conceptually ambiguous once you accept
CT. What has been proved to be necessarily mathematically ambiguous is
the notion of total computable function; in the sense that we have
prove that NO algorithm can test in general the totality or proper
partiality of the function computed by some code.
This is gives us two path in the conquest of the "controllable world".
Either from inside by augmenting in the constructive transfinite RE
*subset* of the set of codes for total functions. This is mainly the
path toward the first person plenitude; or by accepting the jump toward
the partial functions and learning to live together with a partially
non controllable reality. It is akin to the third person jump of act of
faith, but it is also the openness toward the others (which you cannot
control).
Tell me if you are convince that "your" and "my" G are programmable.
You would be kind to tell me if you understand my preceding posts after
getting that G is programmable. (I thought you already get that GEN was
programmable). You should understand that I have proved rigorously
(thanks to CT) the incompleteness of computer science. To prove the
incompleteness of arithmetic/number theory from that consists only in
showing that enough of computer science can be translated in number
theory to inherit essential incompleteness. One path is Godel's
arithmetization, another one, quite beautiful, is the study of the
Diophantine equations, the work of Matiyasevich(*) ... (RE set can be
characterized by Diophantine sets of numbers. Diophantus is a
contemporary to Plotinus, about 200-300 after JC).
This is needed to understand how the many computational histories are
implemented in all possible sort of ways in the realm of numbers, and
later how they interfere when seen from inside, and how from inside
(from 1 povs) all plotinus hypostases get arithmetical interpretations,
including the one describing "matter", which we can then be compared to
the empirical quantum, to test the comp hypothesis. OK?
Bruno
(*) Yuri V. Matiyasevich (foreword by Martin Davis), Third printing
1996, Hilbert's Tenth Problem, The MIT Press (1993 Russian Edition).
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
-~----------~----~----~----~------~----~------~--~---
Received on Sat Jul 15 2006 - 09:50:02 PDT