> 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 -~----------~----~----~----~------~----~------~--~---
