Reference no: EM133026069

COSC 1107/ COSC 1105 Computing Theory Assignment - RMIT University, Australia

Assignment - Computability

1. Overview

This assignment requires you to demonstrate your knowledge of some key issues in computability, and of non-determinism. There is also a part which deals with the Platypus game.

2. Assessment details

1. Passwords

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.

(b) Given your previous answer, how long should the royal keyword be? Explain your answer.

(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.

(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. Computability

The generalised 3-player Platypus game is defined as follows. Let M₁, M₂, and M₃ 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.

(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 problem 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.

(c) Consider the two Turing machines M₁ and M₂ below.

M₁: Whatever the input is, M₁ overwrites each character in the input, resulting in a totally blank tape. M₁ then terminates.

M₂: Given an input string w, M₂ outputs another Turing machine M_w 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.

3. Nondeterminism

Consider the incomplete NFA M₀ below, whose alphabet is {0, 1}.

Use M₀ to create three more NFAs M₁, M₂ and M₃ according to the constraints below. Explain in one or two English sentences how you constructed each NFA.

Each of M₁, M₂ and M₃ 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.

Use JFLAP to transform M₁, M₂ and M₃ into equivalent DFAs.

The sizes of the DFA resulting from the determinising algorithm must be as below. Note that the JFLAP implementation 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 M₁ is 2.

(b) The size of the DFA corresponding to M₂ is 5.

(c) The size of the DFA corresponding to M₃ is at least 9 (this may be harder than you think!)

4. Pumping Lemma

(a) There are three errors in the statement of the Pumping Lemma for regular languages below. Find all three, and state how to correct them. Explain each of your corrections.

Let L be a regular language. Then ∃n ≥ 1 such that for some w ∈ L such that |w| ≥ n, ∀x, y, z such that w = xyz where

i. |xy| < n + 1

ii. y ≠ λ

iii. xyⁱz ∈ L for all i ≥ 1

(b) One fine day, as soon as lockdown was over, Elladan and Elrohir talk an afternoon walk in the gardens of Lothlorien. While contemplating the meaning of existence underneath the massive ancient trees, they come across ten pieces of parchment, which appear to have been hastily ripped up during the recent War of the Ring, on which are written some strange runes that they cannot read. Desperate to find out what these mean, they send the fragments to Imladris for analysis, where the wisest still in Middle Earth would be found. After several anxious weeks, a passing eagle delivers a package to them. Inside they find a letter from Elrond himself, explaining that despite their best efforts, they were unable to fully translate the runes, and so there are some places where there are several possible translations of particular phrases. Elladan and Elrohir therefore have two tasks. The first one is to arrange the fragments in the most likely order. Then they have to select from each of the possible translations so that the overall message makes sense.

The fragments are below, with the parts where there are alternative translations labelled with capital letters, like this:

(Translated text) A (Translated text)

A1: Alternative 1

A2: Alternative 2

A3: Alternative 3

You do not need to write the proof out in full. Just indicate the fragment order and your choice for each of the letters in a sequence like the one below.

9K2 8J3 4E4 ...

(c) Let L be any regular language and let M be a DFA for it with n states. Explain how you can use the Pumping Lemma to show that L is infinite iff there is a string w ∈ L such that n |w| ≤ 2n - 1.

(d) Let L be any regular language over {a, b, c}. Show how the Pumping Lemma can be used to demonstrate that in order to determine whether or not L is empty, we need only test at most (3ⁿ -1)/2 strings.

(e) The Pumping Lemma for context-free languages is below. Let L be a context-free language. Then there is an n ≥ 1 such that for any string w ∈ L with |w| ≥ n there exists strings x, y, z, u, v such that w = xyzuv and

i. |yzu| ≤ n

ii. |y| + |u| > 0

iii. xyⁱzuⁱv ∈ L for all i ≥ 0

Use this to show that the language L = {a^{i^2+i}|i ≥ 0} is not context-free by filling in the gaps below.

5. Intractable problems

Intractable problems are decidable problems, but for which the best known solution is exponential (or worse). Describe two intractable problems and their practical application. You should write one introductory paragraph on intractable problems, and two further paragraphs, one on each problem, and a reason that you selected each one. Some suggestions will be given in class and on Canvas.

6. Universality

In a nutshell, you are expected to revise and extend your work on this topic in Assignment 1.

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

For this assignment, you are expected to either continue your investigation from Assignment 1 on the same topic in more depth, or to make a different choice. In other words, you can either continue with your choice from Assignment 1, or make a different one now. Whatever your decision, you are expected to write about 1800-2000 words (9 or 10 paragraphs) overall. This should include a revised version of your Assignment 1 submission, so that if you continue with the same choice as in Assignment 1, this is will be an extended form of that work. If you make a different choice, that is fine, but you should include your (potentially revised) Assignment 1 submission as part of this submission. So you have two different choices for the two assignments, you are expected to write about the same length on each; if you have the same choice for each, you should write about 1800-2000 words overall. Either way, the submission for Assignment 2 will involve around 1000 words over and above what you submitted for Assignment 1.

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). 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. 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.

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

7. The Platypus game

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,500 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.

(a) For each of your tournaments, report the overall time taken, the top 10 machines (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.

(b) 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 le 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).

You should report where each of these 10 machines finish in the 'football' ranking, and your reasons for choosing each of them.

(c) 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.

(d) In the previous assignment, your calculated the largest Platypus tournament you can play on your machine in 4 hours, ie 4 x 60 x 60 = 14,400 seconds. This is of course for the 'standard' 2-player game. 3-player and 4-player tournaments will of course take longer. Calculate the largest 3- and 4-player tournaments you can play on your machine in 4 hours. You may assume that a 3- or 4-player match takes the same time as a 2-player one. You may also find the following table useful (see the notes on 3- and 4-player tournaments for how these are derived).

Players	Matches required
2	n(n + 1)/2
3	n(n + 1)(n + 2)/6
4	n(n + 1)(n + 2)(n + 3)/24

(e) 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.

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 not be allowed to terminate the game (presumably by allowing them transitions 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.

Attachment:- Computing Theory Assignment File.rar