/Users/billy/gits/moc-2021/tutes/week01.dvi
School of Computing and Information Systems
COMP30026 Models of Computation Tutorial Week 1
26–30 July 2021
Introduction to tutorials
Welcome to the first Models of Computation tutorial for 2021. We hope you will enjoy the tutorials,
and also that you will contribute to making them enjoyable for your class mates. Your tutor will
explain how they would like to run your tutorial.
The exercises
T1.1 Connect to your tutorial’s Microsoft Teams Team (see the tutorial table on the welcome page
of Canvas). Your tutor will show you around the different channels you can use and how you
can participate in the tutorial.
T1.2 Introduce yourself to your classmates and tell them a bit about yourself.
T1.3 Three playing cards lie face down on a table. One is red, one is black, and one is the joker.
On the back of each card is written a sentence:
Card 1 Card 2 Card 3
C
a
r
d
3
is
th
e
jo
k
e
r
!
C
a
r
d
1
is
b
la
c
k
!
I
a
m
th
e
jo
k
e
r
!
The red card has a true sentence written on its back and the black card has a false sentence.
Which card is red, which is black, and which is the joker? Is the solution unique?
T1.4 What is an algorithm? Discuss with your group and try to come up with a definition – the
more specific, the better. The following questions might help in prompting discussion. Give
examples where relevant.
• What do algorithms do?
• What kinds of inputs/outputs do they have?
• What is the difference between an algorithm and a function?
• What does it mean for an algorithm to solve a particular problem?
• What does it mean for a human/computer to “run” an algorithm?
• Are there any sensibility constraints on what kinds of steps an algorithm can require of
the human/computer?
• When are two algorithms the same?
T1.5 In Lecture 1 we play a word rewriting game. Here is an example of a similar kind of game,
the so-called Post’s Correspondence Problem. We have a set of “dominoes” such as
{
b
ca
,
a
ab
,
ca
a
,
abc
c
}
The dominoes use a small alphabet, say the letters a, b, and c. Each domino has a string
written in the upper half, and one in the lower half. The given set of dominoes is always
finite, but there is an unbounded supply of each domino, that is, we can use it many times.
The goal is to find a sequence of dominoes which, when laid side by side, spell out identical
non-empty strings across the top and the bottom (or alternatively, determine that no solution
is possible). For example, the set given above has a solution, namely
a
ab
b
ca
ca
a
a
ab
abc
c
(a) Can you find a solution to
{
baa
abaaa
,
aaa
aa
}
?
(b) How about
{
a
cb
,
bc
ba
,
c
aa
,
abc
c
}
?
(c) How about
{
ab
aba
,
bba
aa
,
aba
bab
}
?
T1.6 Can you come up with a general algorithm to solve Post’s Correspondence problem? Refer
back to your discussion of what an algorithm is – does it qualify as an algorithm? What are
its inputs and outputs? Will your algorithm always arrive at the answer?