Re: coffee-bar machine excerices
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
Re: coffee-bar machine excerices
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
