The University of Melbourne
School of Computing and Information Systems
COMP30026 Models of Computation
Sample Answers to Tutorial Exercises, Week 1
T1.3 Card 3 cannot be red, because red cannot lie, and Card 3 says it is the joker. So suppose
Card 2 is red. Then Card 1 is black and Card 3 is the joker. But then Card 1 actually speaks
a truth, which cannot happen. So we conclude that Card 1 is the red card. It follows that
Card 3 is the joker and Card 2 is black.
T1.4 The answer to this question – “what counts as an algorithm?” – is the subject of the
Church-Turing thesis. Here is an extract from the Stanford Encyclopedia of Philosophy
on the Church-Turing thesis, which provides a definition of an “effective or systematic or
mechanical method”.
https://plato.stanford.edu/entries/church-turing/#ThesHist
The Church-Turing thesis concerns the concept of an effective or systematic or mechan-
ical method in logic, mathematics and computer science. ‘Effective’ and its synonyms
‘systematic’ and ‘mechanical’ are terms of art in these disciplines: they do not carry
their everyday meaning. A method, or procedure, M, for achieving some desired result is
called ‘effective’ (or ‘systematic’ or ‘mechanical’) just in case:
1. M is set out in terms of a finite number of exact instructions (each instruction being
expressed by means of a finite number of symbols);
2. M will, if carried out without error, produce the desired result in a finite number of
steps;
3. M can (in practice or in principle) be carried out by a human being unaided by any
machinery except paper and pencil;
4. M demands no insight, intuition, or ingenuity, on the part of the human being
carrying out the method.
These all seem pretty reasonable expectations for an algorithm, but, as we will discover later
in this subject, condition (2) can be rather difficult, and often impossible to satisfy! This
is the notion of the decidability of an algorithm, which we will return to towards the end of
this subject.
T1.5 (a) Here is a solution: aaa
aa
baa
abaaa
aaa
aa
(b) No solution is possible. Why?
(c) No solution is possible. Why?
T1.6 You may have conjured an algorithm for Post’s Correspondence Problem, but this is only
possible if you violated at least one of the four conditions mentioned above (in the solution
to 1.4). Most likely it was the second, since this problem is undecidable. Have a look at your
algorithm – is it possible that it might run forever for some input?
Undecidability pops up not only in puzzle problems such as Question 1.5, but also in many
practical problems, such as most of the problems faced by designers of optimizing compilers.
https://plato.stanford.edu/entries/church-turing/#ThesHist