Hi Barry and Mirek, (and Brent, David, ....).
Thanks for telling,
New year is good for me. As you know I am a bit of a platonist so time
has no real meaning for me. I told you that this year I'm teaching
Church thesis at my Saturday Course on computer science for a large
(not necessarily mathematician) public, and I am much slow there than
here (we have not yet begin the bijection!).
I will take the time to make all things clear, even for those without
any knowledge in math, but of course it would help if they dare to ask
questions. The key post is certainly not perfect, and will evolve
thanks to you and my students.
In the meantime I will provide a little summary (which I have already
try to make, but it goes repeatedly in the trash because it is too
long).
I intent also to give some sample of "universal system". By a universal
system, I mean the whole complex of a universal machine, its formal
universal language, the set of its instructions, codes, etc.
Let me give you already an example or two.
The Shepherdson Sturgis coffee-bar formal definition of computability.
(A variant by Cutland).
Here is a job offer in an (infinite) coffee bar in Platonia.
(Infinite, just for making things a bit simpler.)
The basic instructions are the following 3 types + 1.
a. - Please add a coffee cup on table 17 (say)
b.- Please put on table 24 as many coffee cups than there are
coffee cups on table 42 (say)
c. - Please make sure there is no more coffee cups on table 56
The last instruction is a bit more difficult. To do the job you need
minimal ability to read a language in which the preceding instructions
can be described. Also, to economize paper (yes in Platonia Forest are
protected too!), the instruction
a. - Please add a coffee cup on table 17 (say) is written
S(17)
b.- Please put on table 24 as many coffee cups than there are
coffee cups on table 42 (say)
is written T(42, 24)
c. - Please make sure there is no more coffee cups on table 56
is written Z(56) (Z is for zero cup of coffee)
For the last instruction you have to know that a job is the given of an
ordered, even numbered instructions. For example, a typical Job is
1) Z(1)
2) S(1)
3) S(2)
Here the job consists in making sure there are no more coffee cups on
table one. Then to add a cup of coffe on table one, and then add a cup
of coffee on table 2.
Now here is the last instruction:
d. - if the number of coffee cups on table 14 (say) is equal to
the number of coffee cups on table 45 (say) then proceed from the
instruction 5 (say) described in your job. In case there are no
instruction numbered 5, stop (the job will be said to be completed); in
case the number of coffee cups on table 14 is not equal to the number
of coffee cups on table 45, then proceed from the next instruction. It
is written: J(14, 45, 5).
DEFINITION: A function f from N to N is said to be Shepherdson Sturgis
coffee bar computable, if there is a job (a list of numbered
instructions) such that when putting n cups of coffee on table one,
then, after the job is completed there is f(n) cups of coffee on table
one.
Similarly, a function h from NXN to N is said to be Shepherdson Sturgis
coffee bar computable if there is a job such that, after having put n
cups of coffee on table one and m cups of coffee on table two, then,
after the job is completed there is h(n,m) cups of coffee on table one.
I have to go, so I give some Exercise for the week-end (I provide
solution monday)
1) find a short job "crashing" the coffee bar computer. Such a job will
never be completed.
2) find a job which computes addition (which is of course a function
from NXN to N)
3) using the preceding job, find a job which computes multiplication.
4) is the following proposition plausible: a function from N to N is
intuitively computable if and only if it can be computed by some coffee
bar job.
5) describe informally the coffee-bar language, and, choosing an order
on its alphabet, write the first 7 jobs in the lexicographical order.
The alphabet contains all symbols needed in the jobs, including commas,
parentheses, etc. + some grammatical rules making clear that Z(23) is a
good instruction, but 23(Z) is not, ...
Bruno
Le 13-déc.-07, à 01:27, Barry Brent a écrit :
>
> Seems fine to me too.
>
> Barry
>
> On Dec 12, 2007, at 12:58 PM, Mirek Dobsicek wrote:
>
>>
>> Hi Bruno,
>>
>>> From what you told me, I think you have no problem with Cantor 's
>>> diagonal.
>>
>> Yep, no problem.
>>
>>> Are you ok with the key post, that is with the two supplementary uses
>>> of the diagonal in the enumerable context?
>>
>> 95% grasped, and for the rest I'm lacking time to do a
>> sufficient amount of scribes in order to get it completely. But
>> nothing
>> fundamental ...
>>
>> Now, I'm very busy with finishing my phd thesis (study and simulations
>> of a certain two-qubit procedure, a sort of benchmark).
>>
>> I guess, I'll be fine at the beginning of the New Year.
>>
>> Sincerely,
>> Mirek
>>
>>
>>>
>
> Dr. Barry Brent
> barrybrent.domain.name.hidden
> http://home.earthlink.net/~barryb0/
>
>
>
>
> >
>
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?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Fri Dec 14 2007 - 09:18:41 PST