Computing Theory
COSC 1107/1105
Assignment 2: Computability
Assessment Type Individual assignment. Submit online via Canvas → As-
signments → Assignment 1. Marks awarded for meeting re-
quirements as closely as possible. Clarifications/updates may
be made via announcements/relevant discussion forums.
Due Date Week 12, Sunday 15th October 2023, 11:59pm
Marks 100 worth 25% of your final assessment
1 Overview
This assignment requires you to demonstrate your knowledge of the key concepts of
Turing machines, universality, computability and the Chomsky Hierarchy. You are also
required to report on some further experiments with the Platypus game.
2 Assessment details
1. Computability (15 marks)
(a) Prove that the Empty Language problem is undecidable by reducing the All
Inputs problem to it. Make sure that all of the details of the reduction are
clearly specified. You may use a diagram to assist with this if you wish. (4
marks)
(b) Prove that the Halting problem is undecidable by reducing the Same Language
problem to the Halting problem. Make sure that all of the details of the
reduction are clearly specified. You may use a diagram to assist with this if
you wish. (4 marks)
Note: The classic way to prove the Same Language problem is undecidable
is to reduce the Halting problem to it; this is asking for a reduction in the
’opposite’ direction.
(c) Grumble, a grumpy wizard, claims to have done the following.
ˆ Identified a decision problem over graphs, which he calls the Balrog prob-
lem, for which he has a (secret) Turing machine which will solve any
instance of the Balrog problem in at most n3 + n2 + 5 steps for an input
of size n.
ˆ Found a (deterministic) Turing machine which transforms an input w to
the 3-SAT problem to an input B(w) to the Balrog problem in at most
n2 + 4 steps for an input of size n.
ˆ Found a (deterministic) Turing machine which transforms an input w to
the Hamiltonian circuit problem to an input H(w) to the 3-SAT in at
most n4 + 7 steps for an input of size n.
Grumble claims that this establishes that the Balrog problem is NP-complete.
Do you agree or disagree? Explain your answer. (4 marks)
(d) Gimli the Gumby, a friend of a more famous Gimli, has written the following
discussion. There are a number of incorrect statements in the paragraph below.
Identify all incorrect statements and justify each of your answers. (6 marks)
Note: A single sentence counts as one statement.
“Algorithms are an expression of knowledge that makes computers work. In
order to solve a particular computational problem, such as finding the factors
of a given number, or sorting a list of students by their student number, an
algorithm must be developed and implemented. It comes as a great surprise
to many people that there are some problems for which there is no algorithm
possible. These are known as undecidable problems and include the Halt-
ing problem for Turing machines, the Hamiltonian Circuit problem, the busy
beaver problem, the tile problem and the blank tape problem. Alan Turing
was the first to show there was an undecidable problem, and since that time
many other problems have been shown also to be undecidable. This is done
by reducing a problem (say A) with unknown status to a problem known to
be intractable (say B). From this reduction it is simple to show that problem
A must be intractable using the Pumping Lemma. The existence of unde-
cidable problems means that certain properties of programs cannot be guar-
anteed. The Church-Turing thesis, which states that anything computable
can be performed by a Turing machine, indicates that we cannot avoid un-
decidable problems by changing technologies. Undecidable problems are also
an issue for nondeterministic pushdown automata and nondeterministic finite
state automata, as nondeterminism introduces computations based on chance.
Unrestricted grammars do not have any issues with undecidable problems, as
there are by definition unrestricted. Note though that NP-complete and other
intractable problems are all decidable.”
2
2. Nondeterminism (8 marks)
Consider the incomplete NFA M0 below, whose alphabet is {0, 1}.
Use M0 to create three more NFAs M1, M2 and M3 according to the constraints
below. Explain in one or two English sentences how you constructed each NFA.
ˆ Each of M1, M2 and M3 must contain at least 10 transitions (potentially but
not necessarily including λ-transitions) and must be an NFA but not a DFA.
Specifically there must be at least one combination of state and input (either
0 or 1) for which there are at least two possible states. Put another way,
removing all λ-transitions must not result in a DFA.
ˆ All states in M1, M2 and M3 must be connected by a transition.
ˆ q3 is the only final state, and q0 is the initial state.
ˆ Use JFLAP to transform M1, M2 and M3 into equivalent DFAs.
ˆ The sizes of the DFA (i.e the number of states in the DFA) resulting from the
determinising algorithm must be as below. Note that the JFLAP implemen-
tation of this often omits an “error” state, i.e. it may be necessary to add an
extra state to the result from JFLAP in order to account for this. The size
constraints below assume a fully deterministic DFA; one way to check for this
is that if the DFA has k states, there must be exactly 2k transitions (one for
each of 0 and 1 in each state).
(a) The size of the DFA corresponding to M1 is 2 or 3. (3 marks)
(b) The size of the DFA corresponding to M2 is 5. (2 marks)
(c) The size of the DFA corresponding to M3 is at least 9 (this may be harder
than you think!) (3 marks)
3
3. Pumping Lemma (15 marks)
(a) Prove that the language L1 = {1i2j32i2j1i} is not regular by using the Pumping
Lemma. Use the string 1n2n32n and i = 3 at appropriate points in the proof.
(4 marks)
(b) Write out the proof of the same result which uses the string 1n32n and i = 0
instead. Which steps are different? Which steps remain the same? (2 marks)
(c) There are some errors in the proof below that the language L2 = {1i2i#32i@2i1i}
is not context-free. Find and correct all such errors. The best way to do this is
to write out the correct proof, highlighting the differences between the correct
proof and the one below. (5 marks)
Claim: The language L2 = {1i2i#32i@2i1i} is not context-free.
Proof: Assume L2 is regular. Then the Pumping Lemma applies and so for
some n ≥ 1 such that for some w ∈ L such that |w| ≥ n, w = xyzuv where
ˆ |yzu| ≤ n
ˆ y ̸= λ and u ̸= λ
ˆ xyizuiv ∈ L for all i ≥ 0
Choose w = 1n2n#32n@2n1n and so w ∈ L and |w| ≥ n. So by the Pumping
Lemma w = xyzuv = 1n2n#32n@2n1n and |yzu| < n. This means that y and
u can contain at most two of 1, 2 and 3. We will refer to the part of the string
before # as zone 1, the part of the string between # and @ as zone 2, and the
part of the string after @ as zone 3.
Now if y or u contains # or @, then clearly xy2zu2v ̸∈ L, as this would contain
two occurrences of either # or @.
Hence neither u nor v contains either # or @.
Now note that both y and u can only cover at most two of zone 1, zone 2,
and zone 3, as |yzu| ≤ n. This means that xy2zu2v ∈ L, as one of the zones
will have the same string as w, but the other two will have longer strings, and
hence xy2zu2v is not of the form 1i2i#32i@2i1i.
This is a contradiction, and so L2 is not context-free.
(d) Let L be a regular language over the alphabet {0, 1}. Use the Pumping Lemma
to show that ∃n ≥ 1 such that for all w ∈ L where |w| ≥ n, there is another
string x such that x ∈ L and |x| < n. (4 marks)
4. Intractability (10 marks)
The Travelling Salesperson Problem (TSP, often known as the Travelling Salesman
Problem) is a well-known example of an intractable problem. Compare the perfor-
mance of a complete solution to this problem (i.e. one that uses an algorithm that
is guaranteed to always find a minimum) with two more efficient algorithms, which
could be either approximation algorithms, heuristics or other means. Your compar-
ison should show the time taken in seconds for all three algorithms to some value
of n, which should correspond to your interpretation of some reasonable maximum
time for the complete algorithm (say 30 minutes). Whatever your maximum time
is, determine the largest value of n which can be solved in this time for each of the
more efficient solutions.
4
You should also describe what input data was used and how you obtained it.
Some possible efficient algorithms include the Christofides or Christofides-Serdyukov
algorithm, the double-tree algorithm, greedy algorithms, the Lin-Kernighan heuris-
tic, and genetic algorithms.
5. Creative Cloud (3 marks)
The Adobe Creative Cloud suite includes a beta version of Firefly, which is a text-
to-image generator. Use this tool to generate the image you like best using a
prompt containing the phrase “playtpus game”. For example, the prompt “a game
involving a platypus and other Australian animals” leads to (amongst others) the
image below. I am sure you can do better!
Show both your image and the prompt/s that created it. Why did you use that
particular prompt? Explain your answer.
You can find the details about the Adobe Creative Cloud at this link.
6. Get Creative! (30 marks)
This is part 2 of an investigation or creative artefact which you began
in Assignment 1.
You are strongly encouraged to use the Adobe Creative Cloud suite, to
which all RMIT students have access. You can find the details about the Adobe
Creative Cloud at this link.
5
In Assignment 1, you investigated one of the following three topics, or came up
with your own related topic or creative story.
ˆ Two-dimensional Turing machines
ˆ Small universal Turing machines
ˆ Notable universal Turing machines
As mentioned in Assignment 1, there are many aspects of Computing Theory that
allow you to show your investigative or creative skills. This could be in the form
of an investigation into a particular topic (Universal Turing machines, Langton’s
Ant, Paterson’s Worms, two-dimensional Turing machines, ...) or by coming up
with a creative artefact (story, movie, VR experience, images, ...) which takes as its
subject a topic relevant to Computing Theory. Investigations will typically generate
empirical data, often by using existing software (with some possible modification of
your own if need be). One such investigation would be to use Colmerauer’s universal
Turing machine (or any other explicitly defined universal Turing machine). Another
would be to generate your own experimental data on well-known concepts such as
Langton’s Ant or Patersons’s Worms. If creative practice is more to your liking,
then coming up with a creative story involving a Turing machine of some kind, or
a topic of similar relevance to Computing Theory (such as the Enigma machine, or
Chomsky’s work on grammars). You could also present this in animated or video
form, or as text.
For this assignment, you are required to build on your earlier experience. This
will require you not only to show how you have extended your original work, but
also to include a reflection on what you have learned from it, and what you would
do differently if you were to do this again from scratch. The reflection should be
around 500 words.
As in Assignment 1, you may also propose an alternative topic, or write a creative
story involving a Turing machine of some kind. You can do this even if you did not
choose either of these in Assignment 1. However, for any alternative topic or
creative story, please seek approval from the lecturer before commencing
work on it. This is to make sure that what you are doing is appropriate for this
assignment — I would hate to see an outcome where you do a lot of work, only for
it not to count because it does not address the intended content.
One alternative topic of particular interest is quantum computing; if anyone
is interested in pursuing this, you are strongly encouraged to do so (but as above,
please do consult me first). You may also be interested in Amazon Braket. Another
possibility is zero-knowledge proofs, but again please consult me before doing
this.
A further point is that you can present your information in other ways
that a formal report if you wish . You are also encouraged to consider
the use of the Adobe Creative Cloud suite, to which all RMIT students have
access. You can find the details about the Adobe Creative Cloud at this link.
Some suggestions are below. Please keep in mind that you still need to discuss the
technical content; the point is to find a way that assists you with this, rather than
being a blockage for you.
6
ˆ Pick a side in the debate about the 2007 universal TM competition
ˆ Langton’s Ant vs Paterson’s worm
ˆ ‘Cellular automata are better than Turing machines’
ˆ Write a children’s story, movie scene, poem, . . .
ˆ 2D TMs as a game, map, drawing a picture, annotating photos, . . .
ˆ Implementation of some aspects (be careful of rabbit holes!)
ˆ Experiment with Java implementation of 2D Universal TM
ˆ Langton’s ant with ‘boundaries’ (see an example here)
You will be marked according to the rubric below.
Points Description Details
18-24 Exemplary You have explored your chosen topic well.
Your report is clear and well-written,
and has the appropriate length.
This is interesting and informative,
and your reflection shows insight and learnings.
12-17 Accomplished You have explored your chosen topic reasonably well.
Your report is generally good,
but can be improved with some more attention
in specific areas, particularly in technical depth.
Your reflection is reasonable,
but could be improved in places.
6-11 Developing Your report needs some further work,
either to increase the level of content or
to improve the choice of material and its presentation.
Your reflection needs some more work.
0-5 Beginning Your report does not show evidence
of sufficient investigation, and is lacking in detail.
Your reflection is inappropriate.
7. The Platypus game For this task you will need to be familiar with the
Platypus game. (16 marks)
Need to determine number of machines to be allocated. Generate and
then set up in the Teams channel.
We have previously talked about running as large a tournament as possible with the
Platypus game. The way we will do this in this assignment is for each of your to run
a tournament of 2,000 machines. From these, you will report your top 10 machines
(see below for details). These 10 will then be part of a knock-out tournament to
determine the overall winner.
Before answering the questions below, do the following.
ˆ Get your allocation of 2,000 machines, which have been randomly selected.
These will be in this folder. Look for a file in the folder with your student
number, i.e. if your student number is 7654321, look for the file 7654321.pl.
Store this somewhere that suits you with a name like machines.pl for conve-
nience.
7
ˆ Download the updated version of the platypus code. This is platypus23.pl
which is available here. This has some extra functionality compared to the
version used in Assignment 1.
ˆ Open a new SWI-Prolog shell and consult both platypus23.pl and machines.pl
(or whatever you called it). Then run the command below. This will classify
your list of machines into three categories, and will generate one file each cate-
gory named none.pl, reachable.pl and unreachable.pl, as per the descrip-
tion below. This will be in the directory specified by the results directory
predicate in platypus.pl; you can change this to something more convenient
for you if you like.
?- classify machines.
None The machine has no platypus state in the fourth row of columns 1-6
Reachable It is possible reach the platypus state from the kangaroo state
Unreachable It is not possible reach the platypus state from the kangaroo state
The point of this analysis is to work out whether it is possible for the machine
to terminate the game or not. An example of each class of machine is below.
In the first case, the machine cannot terminate the game, as it is not possible
for it to go from the start state (kangaroo) to the platypus state as there is
no transition that will move the machine into the platypus state.
Y G Y G Y G Y
K K E E W W P
g y y g y y g
Emu Emu Wombat Kangaroo Wombat Emu Kangaroo
w gg gg w w w gg
The second and third cases occur when there is indeed such a platypus state.
When it is possible to move from the kangaroo state to the platypus state
(depending on the cells on the tape of course), then the machine is classified
as reachable, as in the machine below. This is because it is possible to move
from the kangaroo state to the emu state (column 1 or 2), from the emu state
to the wombat state (column 3) and from the wombat state to the platypus
state (column 6).
Y G Y G Y G Y
K K E E W W P
g y y g y y g
Emu Emu Wombat Kangaroo Wombat Platypus Kangaroo
w gg gg w w w gg
It is also possible that even if such a platypus state exists, it is not possible
to move into that state from the kangaroo state. In this case, the machine is
classified as unreachable, as in the machine below. In this machine we can get
from the kangaroo state to the wombat state and vice-versa, but we can never
8
get to the emu state or platypus state from either of these.
Y G Y G Y G Y
K K E E W W P
g y y g y y g
Wombat Wombat Platypus Kangaroo Wombat Kangaroo Kangaroo
w gg gg w w w gg
Intuitively, machines classified as reachable are in some sense “genuine” with
the others being “imposters”. Accordingly, having separate tournaments for
each seems only fair.
ˆ Run a tournament for each of the following classes of machines
– All 2,000 machines
– Only machines classified as reachable
– Only machines classified none or unreachable (ie all those not classified as
reachable).
To do this, you will first have to prepare a file containing only the machines
as above (the above classify machines command will more or less do this
for you). You will also need to use the command below, which will run the
tournament with all of the options Tree, Tiebreaker and Terminate from the
list below.
?- my tournament([competition23]).
Variation Description
Tree 5 points for whenever either tree is reached
Green 2 points rather than 1 for changing green to yellow
Animal 1 point every time a change of animal occurs
Tiebreaker A random starting configuration is chosen with game length is 200
Terminate 25 points for player that ends the game
Chess Chess-like initial board with the Billabong yellow
Check Chess-like initial board with the Billabong green
Break All cells initially green
The combination Tree, Tiebreaker and Terminate was chosen based on the
results of the survey about this.
If you wish you can also run tournaments with any other combination of op-
tions as well, but you must include results from the above combination for
comparison purposes. To run a different combination use a command like the
below.
?- my tournament([tree,green,animal,tiebreaker,terminate,chess]).
(a) For each of your tournaments, report the overall time taken, the top 10 ma-
chines (by ’football’ ranking), the overall number of wins and draws, and the
number of winless machines. How many machines were classified as none,
reachable and unreachable respectively? Report your results in a table as be-
low. (3
marks)
9
Class Number Percentage
Reachable
Unreachable
None
(b) Do either of the following tasks.
ˆ Re-run your tournament of all machines, but this time you are to include
10 extra machines of your own choice. These should be different from any
machines in your list already, but otherwise you are free to choose them
however you like.
You can use platypus.pl from Canvas (link here) to assist with this if
you wish. This will check whether your 10 added machines are ’legal’,
and whether or not they were already part of your allocation. To do
this, consult platypus.pl and machines.pl as above, and a third file
extra.pl. Then run the command
?- check new.
This will then output whether your added machines are legal, and whether
they are already part of your allocation or not (and if they are, which ones
are already in their allocation).
i. Report where each of these 10 machines finish in the ’football’ ranking,
and your reasons for choosing each of them. (3 marks)
ii. Were you surprised how your chosen 10 machines performed? What
can you conclude from this about high performing Platypus machines?
If you had to choose one machine to represent you in a tournament,
what machine would it be? Briefly explain your decision. (4 marks)
ˆ Choose an alternative tournament to run with all of your machines. This
can use a different combination options if you wish. You should report
the differences in outcomes between this tournament and the original one.
You should also, as above, discuss high performing Platypus machines,
choose a machine to represent you in a tournament, and briefly explain
why this machine is your choice. (7 marks)
You may also propose an alternative task if you wish, but you must discuss
it with the lecturer beforhand.
(c) If the Platypus tournament were to be run again, what alterations would you
recommend? Some ideas are below; you can add others as you see fit. You
should have at least three suggestions. (6 marks)
ˆ Once students are allocated their machines, they play a tournament amongst
these to find the best 10. These 10 then take on the best 10 from other
students. This could include the possibility of students choosing their 10
machines from their allocation or from the set of machines which are not
allocated to any student.
ˆ The initial tape and scoring processes are changed from tournament to
tournament. These are announced in advance, and allow choices to be
made for which machines will be used.
ˆ Non-player machines can be added. These are not competitors, but may
change the tape in ways that influence the game. Such machines would
10
not be allowed to terminate the game (presumably by allowing them tran-
sitions for a green cell with a platypus).
ˆ When a player has a platypus on a green cell, the game does not halt,
but is “rebooted”, i.e. the tape reverts to its initial state, the player which
’halted’ the game gets a bonus or a penalty, and the machines involved
are changed in some way. This change could be swapping rows 3, 4 and
5 of column 1 and 2 (kangaroo), and the same for columns 3 and 4 (emu)
and 5 and 6 (wombat). There could be a maximum of say 5 reboots per
game.
ˆ (insert your idea here!)
Note that parts (b) and (c) above are really about getting you to think about
the properties of machines, and whether humans can ’outsmart’ machines that run
through a large number of possibilities and select the best. If you wish, you can
propose alternative tasks for these of your own design. But please discuss it with
the lecturer beforehand.
3 Submission
You should submit the following.
ˆ A PDF file containing your answers to the questions.
ˆ All .csv files generated by running your tournaments.
No other file formats will be accepted.
4 Rubric
Your assignment will be graded in accordance with the rubric in Canvas (which will be
available shortly).
11