- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Bruno Marchal <marchal.domain.name.hidden>

Date: Fri, 14 Dec 2007 15:18:04 +0100

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

Date: Fri, 14 Dec 2007 15:18:04 +0100

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 :

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

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