闪电代写 -代写CS作业_CS代写_Finance代写_Economic代写_Statistics代写_代码代做_IT代写_加急帮助

Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

COMP2048

Theory of Computation

Problem 1 (2 Marks)

Show that a Turing machine is more powerful than a finite state machine by using an example language that is only decidable by a Turing machine. Provide a high-level description of the Turing machine that decides this language.

Requirements: Present your answer in less than ½ page A4 size, 12 pt with Normal (2.54 cm) margins (excluding figures or tables). Use tables via the word-processor if any are required.

Problem 2 (2 Marks)

Describe and contrast Turing machines and Lambda Calculus as theories of computation, while highlighting the advantages and disadvantages of each theory.

Problem 3 (4 Marks)

Describe how Boolean logic can be defined in Lambda Calculus and therefore the three main operations of AND, OR and NOT can be encoded into it making sure to explain all the relevant combinators, their arguments and function bodies.

Requirements: Present your answer in less than 1 page A4 size, 12 pt with Normal (2.54 cm) margins (excluding figures or tables). Use tables via the word-processor if any are required.

Problem 4 (4 Marks)

Describe how one can compute the factorial function using recursion in Lambda Calculus. Make sure to mention all the relevant combinators and theorems required to achieve your result.

Requirements: Present your answer in less than 1 page A4 size, 12 pt with Normal (2.54 cm) margins.

Problem 5 (4 Marks)

Use the Deutsch problem and principles of quantum mechanics to explain why a quantum computer can solve problems much faster than a conventional computer.

Requirements: Present your answer in less than 1 page A4 size, 12 pt with Normal (2.54 cm) margins.

Problem 6 ( 14 Marks)

Answer the following questions using dot points wherever possible (preferably numbered) and note assumptions made if any.

You have been tasked to construct a computing system for a crewed spaceship that will be used for a human expedition to Mars. The computing system has the following constraints:

x The crew will have no programming or computing hardware experience but will have a strong understanding of mathematics and mathematical principles.

x The crew will need to compute simulations and calculations, as well as run communication, navigation and life support throughout the mission.

x The hardware for the computing system is to be a digital computer similar to the desktops we use today.

x The programming interface for the computing system is limited to an input of 280 characters, so each program can only have this maximum size.

x The computing system must run for long periods without crashing and/or rebooting.

x The expedition will utilize mathematical proofs and principles to ensure robustness and quality assurance of the computing system to prevent bugs and errors within the system.

1. You must design the computing system for the crewed mission to Mars using the principles and material taught in this course given the constraints above. Your answer should contain:

i. A description and definition of the computational model(s) that will be required for each part of your proposed computing system. (2 Marks)

ii. How each model(s) will work and the reason for the choice(s) of the model(s) including their features relevant to the constraints of the crew and the mission. (4 Marks)

iii. The mathematical evidence or principle(s) that makes your model(s) possible within the constraints of the hardware and programming interface. (2 Marks)

iv. How the programming interface and chosen computation model(s) will be used to compute all the requirements of the crew and the mission (such as communication, navigation etc.). (2 Marks)

v. How the hardware and programming interface will interact to complete computations and the mathematical principles that guide your design. (1 Marks)

vi. What if any ‘off-the-shelf’ solutions currently available within computer science and software engineering can be used to construct your proposed system. (1 Marks)

2. Now consider if the entire system were to be implemented using a quantum computer. In a few dot points, describe if there would be any advantages and disadvantages of this decision to the mission, as well as the challenges the crew and the mission would face as a result. (2 Marks)

Requirements: Present your answer in less than 2 pages A4 size, 12 pt with Normal (2.54 cm) margins.