Le 07-janv.-08, à 16:51, Mirek Dobsicek a écrit :
>
> Bruno wrote:
>> 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.
>
> BEGIN
> 1: Z(1)
> 2: Z(2)
> 3: J(1,2,3) # true condition, loop
> END
Excellent. Supposing that ":" has been included in the alphabet. Good
idea: it is more readable. You have also add commentaries, beginning by
"#". This is of course not part of the formal job/program. Also, note
that the original Cutland-Shepherdson Sturgis programs are not
self-delimiting (no BEGIN nor END, but I use self-delimiting program
most often, so ok).
Here is simpler solution:
BEGIN
1: J(1,1,1) # this will work independently of the number of coffee
cups already on the table!
END
>
>
>> 2) find a job which computes addition (which is of course a function
>> from NXN to N)
>
> BEGIN
> 1: Z(3) # clean temp tables
> 2: Z(4)
> 3: J(2,3,8) # are we done? get out of the loop
> 4: S(1)
> 5: S(3)
> 6: S(4)
> 7: J(3,4,3) # always true condition, continue with adding
> 8:
> END
Very good. You could have make a simpler one too, just adding one cup
of coffee on table 1 and table 3 and stopping when table 2 and table 3
have the same number, but this is detail.
Note that the 8th instruction is not needed and should be suppressed.
Programs ends when they does not find the next instruction. "8:" is a
bit ambiguous.
>
>> 3) using the preceding job, find a job which computes multiplication.
>
> BEGIN
> 1: Z(5) # clean temp tables
> 2: Z(6)
> 3: T(1,5) # copy 1 -> 5
> 4: J(5,6,14) # are we done? get out of the multipl. loop
> 5: S(6)
> 6: Z(3) # adding loop start
> 7: Z(4)
> 8: J(2,3,13)
> 9: S(7)
> 10: S(3)
> 11: S(4)
> 12: J(3,4,8) # adding loop end
> 13: J(3,4,4) # always true condition, continue with multipl. loop
> 14: Z(1)
> 15: T(7,1) # copy 7 -> 1, table one contains the final result
> END
Perfect. The others should at least see the addition program above used
as a "subroutine", here.
>
>> 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.
>
> yes
> 1) instructions of the coffee-bar language coincide with important
> instructions of nowadays central processing units in computers
OK. But that is not an argument. The subset with the instructions Z,
S, T also, but is not universal. But I see your point: the main
fundamental instructions of central processing units belongs to the
coffee-bar computer.
>
> 2) coffee-bar instructions are sufficient for constructing logical AND,
> OR, NOT operations
AND and NOT are already universal indeed, if you add a delay
instruction (enginners does not say this explictly because the
"natural-concrete" AND introduces automatically a delay.
And also, you need the "duplicate" instruction, (a bifurcating
electrical wire) which engineers mention only since ... quantum
computing exists. This is because a bifurcating wire seems a so obvious
"instructions" that we forget to mention it, but in quantum computing
you just cannot duplicate arbitrary information ....
But OK, good idea.
>
> 3) I should be able to find a better reason, damn...
It is not obvious. To be sure it is universal, the better way would be
to show you can implement an already known universal system, or to
verify explicitly the closure for the diagonal + the emulability of
elementary functions, etc.
>
>> 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, ...
>
> Program ::= BEGIN commands END
> commands ::= line-no instruction comment next
> line-no ::= num:
> instruction ::= Z(num) | S(num) | T(num,num) | J(num,num,num)
> comment ::= # text `new-line` | `new-line`
> next ::= commands | END
> num ::= [0,1,2,3,...]
> text ::= [ascii text without the `new-line` character]
>
>
> First 7 jobs
>
> 1)
> BEGIN
> 0: J(0,0,0)
> END
Hmmm.... First I strongly suggest no putting the commentaries in the
program (# ...). You just make your life harder.
Second, if you accept, like above a empty instruction (like the 8: in
your addition program above, you have to agree that
BEGIN
0:
END
is shorter, no? But I disallowed it.
But then why is not the following program
BEGIN
0: S(0)
END
shorter?
And third, do you know a coffee-bar with a table numbered by 0? The
same for the numbering of the instructions in the job. You have
yourself begun the numbering of the instructions with 1? (a total
detail, sure).
>
> 2)
> BEGIN
> 0: J(0,0,1)
> END
>
> 3)
> BEGIN
> 0: J(0,1,0)
> END
>
> 4)
> BEGIN
> 0: J(0,1,1)
> END
>
> 5)
> BEGIN
> 0: J(1,0,0)
> END
>
> 6)
> BEGIN
> 0: J(1,0,1)
> END
>
> 7)
> BEGIN
> 0: J(1,1,0)
> END
>
> Assuming empty tables, programs 1,3,5,7 never reach END.
OK. Very good. I hope others understand what you have done. Perhaps
someone can correct the last exercise, or perhaps you have a reason to
consider J(1,1,1) little than Z(1), which I have not seen?
I give two new exercises:
1) the alphabet of the coffee-bar language (accepting your ":"
improvement) is
{:, (, ), J, S, T, Z, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9} (we write the
number in decimal).
Now a program, like
BEGIN
1: S(1)
END
is the same as BEGIN1:S(1)END (less readable, but it is the same
program: we are not in PYTHON where the carriage return is in the
alphabet!).
But the expression BEGIN1:S(1)END denotes a number in base 17. All
right?
The question is: does a program U exists which is such that if you put
n, written in base 17, output nothing on table 1 in case the number is
not a program, and output the result of the running of that program in
the other case. Would you say that such a U program is universal?
2) Here is another universal system.
Alphabet = { ), (, S, K}. The alphabet has only four elements.
Programs/jobs in this system are easy to define inductively:
K is a program
S is a program
if X and Y are programs, then (XY) is a program.
Nothing else is a program.
So for example the first programs are K, S, (KK) (KS) (SK) (SS) (K(KK))
(K(KS)) (K(SK)) (K(SS)) ...
the operational interpretative rule (the dynamic if you want) is given
by the following reduction rule
replace any occurence of ((Kx)y)) by x
replace any occurence of (((Sx)y)z) by ((xz)(yz)); x y z being
arbitrary programs.
It is easier to read those expressions if you eliminate all left
parenthesis: this gives for the dynamical rule:
Kxy = x
Sxyz = xz(yz)
the question are the same than the one for the coffee-bar. In
particular could you write a program which crash the system?
Hint: search for a program I such that Ix = x. Search a program M such
that Mx = xx.
Raahhhh ... Sorry but I am interrupted. I come back on this later,
Best,
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?hl=en
-~----------~----~----~----~------~----~------~--~---
Received on Wed Jan 09 2008 - 10:53:41 PST