Re: Smullyan Shmullyan, give me a real example

From: Bruno Marchal <marchal.domain.name.hidden>
Date: Wed, 24 May 2006 11:00:27 +0200

Hi Russell,

You wrote (24 may):

>
> On Tue, May 23, 2006 at 12:25:35PM +0200, Bruno Marchal wrote:
>>
>>
>> In a sense, you are obviously right. That is why I said "some"
>> knowledge of comp science or even just in math will make the existence
>> of the UD, and of the Universal Machine astonishing. Precisely it is
>> the knowledge of diagonalization. Godel will miss the universal
>> machine
>> and Church thesis, and will describe those things as a sort of
>> miracle.
>> More later. I will comment again with much more detail the rest of
>> your post much later. If I comment it here now I will introduce
>> confusion. It is preferable people get much more familiarity with the
>> effective and not effective daigonalisations procedures before, I
>> think.
>>
>
> I guess by this you mean that whilst it is impossible enumerate all
> descriptions (the books in the infinite version of the Library of
> Babel such as I take as my starting point), nor all true mathematical
> facts, or even all programs (not sure on this one, obviously one can
> enumerate all halting programs), it is however possible to execute all
> possible programs. Yes, put that way, I suppose it is astonishing.


You put your finger on the difficulty. If we can enumerate all halting
programs then we can diagonalize it and extract an halting program not
belonging to the list.

Actually when you say in your preceding post (21 May):




> That one can dovetail on all possible programs must be pretty obvious
> once one realises that these can be enumerated.



You are pointing on the main difficulty. Once we can enumerate a list
of functions from N to N, then we can diagonalize that list, and by
this we can show the list being not complete.

Now, it is not so hard for a computer programmer to single out a
"solution" to this difficulty, but without a good understanding of
diagonalization, it is easy to miss what is going on, and to miss in
this way the tremendous impact of Church thesis. I will show that
Church thesis will literally rehabilitate Pythagorus doctrine: "all is
number", despite irrational or transcendent numbers.

Let me proceed further with the others because we are far ahead in the
thread,

Best regards,

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 Wed May 24 2006 - 05:01:46 PDT

This archive was generated by hypermail 2.3.0 : Fri Feb 16 2018 - 13:20:11 PST