>>> 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?
Well :-) my lexicographical ordering abilities have shown a weak point. > 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? Yes, it is clear. > 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? Yes. We call such a program an interpreter. And the existence of a program called 'interpreter' is a consequence of the fact that a machine capable of executing a universal language L, must be descriable itself by L. What happens when we feed U with its own code? Doing something, doing something and .. hanging ... waiting for an input. Best, 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 -~----------~----~----~----~------~----~------~--~---