COSC 1107/1105 Assignment 2: Computability
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Computing Theory
COSC 1107/1105
Assignment 2: Computability
Assessment Type Individual assignment. Submit online via Canvas → As-
signments → Assignment 2. Marks awarded for meeting re-
quirements as closely as possible. Clarifications/updates may
be made via announcements/relevant discussion forums.
Due Date Tuesday 19th October 2021, 11:59pm (note new date)
Marks 100 worth 25% of your final assessment
1 Overview
This assignment requires you to demonstrate your knowledge of some key issues in com
putability, and of non-determinism. There is also a part which deals with the Platypus
game.
2 Assessment details
1. Passwords (8 marks)
The Dwarves of the Lonely Mountain have a lot of time on their hands, and are
very worried about information about the size of their horde of gold getting around
various parts of Middle-Earth, as they fear invasion by all and sundry if any hint
of their true wealth were to be revealed. Accordingly King Durin XIII decrees
that all records are to be written only in encrypted Khuzdul, in which there are
32 distinct characters. The encryption process is based on a Khuzdul keyword of
n characters in length. Durin’s advisors inform him that an evil wizard with an
army of orc-slaves at his disposal (or a few of the lesser intelligent hobbits :-)) could
exhaustively search through all possible keywords at a rate of 100,000 keywords per
day. Durin decrees that the royal Khuzdul keyword must be secure ”until the end
of the age”.
(a) Determine an appropriate interpretation of Durin’s statement ”until the end
of the age”. In other words, define what you think this means and hence what
the maximum such time would be. (2 marks)
(b) Given your previous answer, how long should the royal keyword be? Explain
your answer. (2 marks)
(c) Sillibo, a passing hobbit, happens to point out to Durin that not all of the
32 Khuzdul characters are equally likely to be used, as there are 18 that are
only used very rarely. Hence an outsider might concentrate on the other 14
and make significant progress. Assuming Sillibo is correct, calculate how long
it would take an evil wizard to discover a Khuzdul keyword of length given in
your previous answer, assuming that at most 14 different Khuzdul characters
are used in the keyword. (2 marks)
(d) Sillibo also tells Durin, who is very impressed with the hobbit’s knowledge,
that the royal keyword should not include a Khuzdul translation of the name
”Arkenpebble” (a famous jewel revered by all dwarves), as this is very well
known to all in Middle-Earth, and hence will certainly be known to any evil
wizard. Given the translation of Arkenpebble into Khuzdul uses 6 characters,
evaluate Sillibo’s claim. In other words, is the royal keyword still as secure as
Durin would like if it does contain the translation of Arkenpebble and the evil
wizard correctly guesses this. (2 marks)
2. Computability (14 marks)
The generalised 3-player Platypus game is defined as follows. Let M1, M2, and M3
be Turing machines, which share the same tape. The tape is initially blank. The
initial configuration of the three machines is as shown below.
As in the Platypus game, each machine takes turns to move (but there is no scoring
involved).
(a) Show that the halting problem for the 3-player generalised Platypus game is
undecidable. You may use any reduction you like. (6 marks)
(b) Suppose the 3-player generalised Platypus game is played on a Turing machine
with a finite tape (making the halting problem decidable), and that this prob
lem has been shown to be NP-complete. Given your above reduction from
some problem A to the 3-player generalised Platypus game, can this reduction
be used to conclude that A is NP-complete? Why or why not? Explain your
answer. (2 marks)
(c) Consider the two Turing machines M1 and M2 below.
M1: Whatever the input is, M1 overwrites each character in the input, resulting
in a totally blank tape. M1 then terminates.
M2: Given an input string w, M2 outputs another Turing machine Mw which
will take a blank tape as input, print w on the tape and then terminate.
Explain how these two Turing machines are used in at least three reductions
of the Halting problem to other undecidable problems. (6 marks)
2025-12-24