> 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


> 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

> 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

> 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

2) coffee-bar instructions are sufficient for constructing logical AND,
OR, NOT operations

3) I should be able to find a better reason, damn...

> 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

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.

Sincerely,
 Mirek

--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups 
"Everything List" group.
To post to this group, send email to [EMAIL PROTECTED]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at 
http://groups.google.com/group/everything-list?hl=en
-~----------~----~----~----~------~----~------~--~---

Reply via email to