计算理论代写 COSC 1107/1105代写 Computing Theory代写
614Computing Theory COSC 1107/1105 Assignment 1: Fundamentals 计算理论代写 Assessment Type Individual assignment. Submit online via Canvas → Assignments → Assignment 1. Marks awarded for mee...
View detailsSearch the whole station
代写计算理论 Assessment Type Individual assignment. Submit online via Canvas → Assignments → Assignment 1. Marks awarded for meeting requirements as closely as
Assessment Type
Individual assignment. Submit online via Canvas → Assignments → Assignment 1. Marks awarded for meeting requirements as closely as possible. Clarifications/updates may be made via announcements/relevant discussion forums.
Marks 110 worth 25% of your final assessment
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.
The generalised Platypus green game (GPGG) is defined as follows. Let M_{1} and M_{2} be Turing machines, which share the same tape. The tape is initially all green. The initial configuration of the two machines is as shown below.
As in the Platypus game, each machine takes turns to move (but there is no scoring involved).
Show that the halting problem for GPGG is undecidable. You may use any reduction that you like. (6 marks)
Suppose the GPGG 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 GPGG, can this reduction be used to conclude that A is NP-complete? Why or why not? Explain your answer. (2 marks)
Seedout, a rather adventurous and reckless hobbit, has proposed the reduction below as a way of showing the Empty Language problem is undecidable by reducing the Halting Problem to it. Unfortunately there are two errors in this reduction. Identify these errors, explain why these are incorrect and how they may be corrected. (4 marks)
Seedout’s explanation is: ”Assuming the Empty Language problem is decidable (and hence the existence of a Turing machine Empty which decides the problem), we can construct a solution to the Halting Problem as follows. First, given the Turing machine M and input w, we use these to construct another Turning machine M′′ which deletes any input on the tape, writes w on the tape and then acts as M would. So the language accepted by M′′ is empty iff M halts on w. See the diagram below for more details.”
Undecidability results are often given in terms of Turing machines. Explain how these results are relevant to modern programming languages, using three examples of undecidable problems that occur in such languages. (3 marks)
Consider the incomplete NFA M_{0} below, whose alphabet is {0, 1}.
Use M_{0} to create three more NFAs M_{1}, M_{2} and M_{3} according to the constraints below. Explain in one or two English sentences how you constructed each NFA.
(a) The size of the DFA corresponding to M_{1} is 2 or 3. (3 marks)
(b) The size of the DFA corresponding to M_{2} is 5. (2 marks)
(c) The size of the DFA corresponding to M_{3} is at least 9 (this may be harder than you think!) (3 marks)
There are three errors in the statement of the Pumping Lemma for regular languages below. Find all three, state how to correct them, and explain your answers. (4 marks)
Let L be a regular language. Then ∃n ≥ 1 such that for any w ∈ L such that |w| > n, ∃x, y, z such that w = xyz where
i. |xy| ≤ n
ii. x ≠ λ
iii. xy^{i}z ∈ L for all i ≥ 1
Galadriel, on her Elftiki tour of Middle-Earth in the Second Age, comes across some scraps of parchment in the Hall of Records of Numenor. These scraps, numbering 10 in all, are partly burned and not always legible, but contain some ancient runes that not even Galadriel can decipher. But she can make some educated guesses, and first must decide on the relevant order of the fragments, before choosing from potential translations for each of them, 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:
The Pumping Lemma for regular languages states a necessary property for such languages. Is it possible that the same property is true for context-free and context-sensitive languages? Explain your answer. (3 marks)
Let L the language of a DFA with n states. Explain why either L = ∅ or there is a string w ∈ L such that |w| < n. (3 marks).
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^{i}zu^{i}v ∈ L for all i ≥ 0
“And long there he lay, an image of the splendour of the Kings of Men in glory undimmed before the breaking of the world.” – The Lord of the Rings, by J.R.R. Tolkien.
It may be a very long time before “the breaking of the world”. How would you interpret this time? This may be thought of as estimating how much time is left before “the end of the world”, however you may interpret that. Give your estimation of this length of time in years. Justify your answer. (3 marks)
The Towers of Hanoi is a classic problem in computing. To move a tower of height n from one pole to another (observing the rules of course) takes a minimum of 2^{n }− 1 steps. It is said the world will end before this problem can be solved when n = 64.
Calculate how long it will take to solve this problem for the cases where 32 ≤ n ≤ 64, assuming 0.1 seconds per move. Does this support the claim about the end of the world being sooner?
Use a spreadsheet for this calculation, and report the cases for n = 32, 40, 48, 56 and 64. (3 marks)
It is estimated that the Big Bang was 13.7 billion years ago. This is
13, 700, 000, 000 × 365.25 × 24 × 60 × 60 = 432, 339, 120, 000, 000, 000
seconds ago.
Calculate the value of n for which the Towers of Hanoi problem can be solved in this time at the rate of 10 seconds per move.
Compare this value with the number of machines that could play a complete Platypus tournament in this time at the rate of 0.1 seconds per match.
You will also find a spreadsheet very useful for this. (3 marks)
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.
Please note that I am not at all interested in what you can find on Google or Wikipedia or anything like that. What I really want to see is some evidence of you thinking about intractable problems and what effect these have, such as the relationship between the vertex cover problem and sensor networks.
Perhaps an interesting way to address this is to consider what differences it would make if your intractable problem could be solved efficiently. For example, if we could solve say the Travelling Salesperson problem in O(n2 ) time, what would be possible that is impossible now?
Another possibility is to consider how intractability can be a useful thing, such as keeping information secure in cryptosystems or in related applications such as blockchain.
Whatever problems you choose, please avoid the temptation to ’cut, copy and edit’; as soon as you do that, you have done something wrong. I would far prefer to read your own words and your own perspective on these problems.
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.
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.
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.
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.
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.
Before answering the questions below, do the following.
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.
Intuitively, machines classified as reachable are in some sense “genuine” with the others being “imposters”. Accordingly, having separate tournaments for each seems only fair.
– All 2,500 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 below.
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
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 below. (2 marks)
Class | Number | Percentage |
Reachable | ||
Unreachable | ||
None |
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
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. (2 marks)
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)
In the previous assignment, your calculated the largest Platypus tournament you can play on your machine in 4 hours, ie 4 × 60 × 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 tour-naments 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). (2 marks)
Players Matches required
2 n(n + 1)/2
3 n(n + 1)(n + 2)/6
4 n(n + 1)(n + 2)(n + 3)/24
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)
You should submit the following.
No other file formats will be accepted.
Your assessment will be marked according to the criteria below.
更多代写：Machine Learning代写 gmat online代考 英国物理学网课代做 英国essay范文 executive summary怎么写 代写平台
合作平台：essay代写 论文代写 写手招聘 英国留学生代写
Computing Theory COSC 1107/1105 Assignment 1: Fundamentals 计算理论代写 Assessment Type Individual assignment. Submit online via Canvas → Assignments → Assignment 1. Marks awarded for mee...
View detailsCOMP3710, Computer Microarchitecture Homework 1 (Weight: 20%) 计算机微体系结构代写 Total Points: 100 Important Instructions: (1) Write down the names and UIDs of each student in a group (if ...
View details