COMP2048 Theory of Computing Semester One Examinations, 2022
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Semester One Examinations, 2022
COMP2048 Theory of Computing
Question 1 – Finite State Machines
Design and define the following FSMs using either a transition table or state diagram
a) An FSM M1 that only accepts set of strings containing an odd number of ones
b) An FSM M2 that only accepts set of strings containing an even number of zeros
c) An FSM M3 whose language is the intersection of the languages of M1 and M2 . (3 Marks)
Question 2 – Turing Machines
Show that the language C = {a i bj c k | i × j = k and i, j, k > 1} cannot be recognisable by a finite state machine by designing a Turing machine that decides it.
(4 Marks)
Question 3 – Lambda Calculus
Define and discuss the significance of the following two combinators in Lambda
Calculus:
a) Composition Combinator
b) Y Combinator
Describe how each of these combinators contribute to the Turing completeness of
Lambda Calculus.
(5 Marks)
Question 4 – Lambda Calculus
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.
(5 Marks)
Question 5 – Quantum Computation
Describe the Deutsch problem and explain why a quantum computer can solve it much faster than a conventional computer.
(5 Marks)
Question 6 – Applied Problem
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:
O The crew will have no programming or computing hardware experience but will have a strong understanding of mathematics and mathematical principles.
O The crew will need to compute simulations and calculations, as well as run communication, navigation and life support throughout the mission.
O The hardware for the computing system is to be a digital computer similar to the desktops we use today.
O The programming interface for the computing system is limited to a Twitter-like interface with an input of only 280 characters allowed, so each program can only have this maximum size.
O The computing system must run for long periods without crashing and/or rebooting.
O 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. ( 1 Mark)
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.
(2 Marks)
iii. The mathematical evidence or principle(s) that makes your model(s) possible within the constraints of the hardware and programming interface. ( 1 Mark)
iv. How the programming interface and chosen computation model(s) will be used to compute all the requirements of the crew and the mission. ( 1 Mark)
v. How the hardware and programming interface will interact to complete computations and the mathematical principles that guide your design.
(1 Mark)
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)
2022-07-18