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