Le 15-juil.-06, à 02:56, Tom Caylor a écrit :

## Advertising

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