Le 13-juin-06, à 03:04, George Levy a écrit :
>
> Bruno Marchal wrote:
>
>> Proceeding that way you will run into trouble. But it is very easy to
>> find the k.
>> Let us be specific and let us imagine you have already written in
>> Fortran a generator of all programs of the one-variable partial
>> computable functions: F1 F2 F3 F4 F5 F6 F7 ...
>> The list of programs is P1 P2 P3 P4 P5 P6 ... Each Pi(n) computes
>> Fi(n)
>>
>> Now program G in "Fortran". It is something like that:
>>
>> Begin G
>> Read X
>> Call the generator of program up to X, giving PX
>> Apply PX on X, and put the result in register 439
>> Add 1 to the content of register 439
>> Output the content of register 439
>> End
>>
>> Now, look at your list of programs Pi until you find it, and look at
>> his number code (where n is the number code of Pn by definition).
>> Finding your program in your list of programs should be easy given
>> that
>> the list P1 P2 P3 ... is ordered lexicographicaly (by length, and by
>> alphabetical order for those of same length). So you can find it
>> easily. Is number code is the number k. If you run G on k, your
>> fortran
>> interpreter will run for ever (and your fortran compiler will generate
>> a code which run for ever). Speaking just a little bit loosely.
>>
>>
>>
> Let's be more specific.
> Begin G
> Read X
> Call generator of program which produces P1, P2, P3..in sequence.
> Select
> Program PX.
> Compute the value PX(X).
> Save the value into register 439
> Add 1 to content of register 439. Call this value Y
OK. I guess you agree this program is equivalent to mine. Now this a
fortran program (I mean when correctly written in Fortran of course).
Thus it is equal (syntactically) with some program Pk (given that the
Pi lists all fortran programs). But then we have *already* k. It is the
indice k of Pk = "BEGIN G READ X ..." written above. We don't even need
to ever run G, because to find its code (and thus its number code) we
need only to *write* the program. To find k we need only to find the
piece of code Pk in our list P1 P2 ...
So I don't see the point of your scanning device.
Having said this ....
>
> Now look at the list of all programs P1(1), P2(2)....
I guess you mean the 0-variable programs obtained by fixing the
argument (like in Jesse second key remark of last week).
> The scanning
> program could be:
>
> i = 1 (initiate counter i to 1)
> Start Loop
> If Pi(i) = Y then k=i; Exit
> Else i=i+1
> End if
> End Loop
>
> My point is that the loop will never end and you will never find k.
I think you are right. But this shows only that this way of finding k
will not work. See above for a method which works. Tell me if you see
it works. It works because the program above is in the list Pi, so it
has a number code k. We don't need a second scanning program to find
it. The code of G is enough, we just need to be patient to find it in
the list of the programs Pi, and given that the Pi are
lexicographically ordered, we can do it for sure. Of course we can
write a program for doing that, that program is just the reciprocal of
the computable bijection between the N and the set of codes of
the partial computable functions.
I recall that set of the computable partial functions includes the set
of the strictly partial and the set of total computable functions. I
will make a summary of definitions and of the propositions we have
already proved.
> If
> you did find k then Pk(k) = P(k)+1 which is impossible.
Not at all. The Pk are the programs of the partial computable functions
Fk (not the total one fk). I can find k by localizing the program above
(or any equivalent) in the list Pi.
> However, I don't see any problem in using P(x) for computing G(x) for
> any x
Well, even your own argument shows that G(k) is undefined. Here your
remark would be true with the "listing" of the total computable
fonction. In that case G is not computable because we have shown by
diagonalization that the "listing" of fi is not programmable.
I know you leave us for 10 days, and your last line makes me not so
sure you completely grasped the difference between the fi and the Fi.
(apology for those june-exam like remark: but some minimal amount of
technical matter needs to get the real thing).
All this is needed to proceed, so I hope we will arrive at a common
understanding. G G*, and thus all "plotinian hypostases" (including the
physical appearances) will appear when you will be easy not only with
the current diagonalizations, but when you will see that a machine
canhandle them too and reason about. them also, so that she is able to
study its own limitations. In Smullyan's FU, this is reflect in the two
stages:
fact 1 + fact 2 versus fact I + fact II, where "true" has been replaced
by "established".
UDA shows that the physical appearances emerges from those limitations,
and to extract physics (and then the whole larger theology) we have to
study what machines can explicitly derive from its own limitations.
Normally everyone who has followed the current thread should be able to
do the similar diagonalisation exercise which I have already propose in
this list in 2001:
Diagonalisation 1
http://www.mail-archive.com/everything-list.domain.name.hidden/msg01561.html
And the answer was:
Diagonalisation 1 answers
http://www.mail-archive.com/everything-list.domain.name.hidden/msg01585.html
Those posts were supposed to be followed by a "Diagonalization 2" post,
but I need evidence that people have no problem with those form of
diagonalization. The diagonalization 2 would have corresponds to the
fact I + fact II (where diagonalization 1) corresponds to the fact 1 +
fact 2.
... and now we are progressing apparently. That diagonalization II post
appears in the horizon now.
Hope you, George and others, have some fun too, don't hesitate to make
any remark or question ...
There is no stupid questions.
(Alas there are stupid answers ;)
Bruno
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 Tue Jun 13 2006 - 10:10:30 PDT