>>> 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 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 Wed Jan 30 2008 - 07:43:02 PST