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