> 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 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 Mon Jan 07 2008 - 10:52:07 PST