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

COMP2048

Theory of Computing

2021

Problem 1 ( 1 Mark)

Describe the main advantages and disadvantages of an FSM in terms of computation. Be sure to include at least one example and discussions on the consequence of having only a fixed number of finite states.

Requirements: Present your answer in less than ½ page A4 size.

 

Problem 2 (2 Marks)

Design and formally describe a Turing machine that decides  =  0ଶ⃞   ห ⃞  ⃞ 0}, the language consisting of all strings of 0s whose length is a power of 2. Include

a)   a high-level description of its algorithm,

b)   a formal description of the Turing machine,

c)   a transition/state diagram or table of the Turing machine,

d)   a sample run of the machine on the string 0000 noting its configuration at each step.

Requirements: Present your answer in less than 1 page A4 size.

 

Problem 3 (4 Marks)

Describe how qubits are constructed, including the principles used in their construction with the  appropriate  mathematical  expressions,  comparisons  to  classical  bits  with  the  same notation, as well as the advantages that are offered by them with respect to computation.

Requirements: Present your answer in less than ½ page A4 size.

 

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


Problem 5 (9 Marks)

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

The Search for Extraterrestrial Intelligence (SETI) has made an astonishing discovery of an alien signal from space via  radio telescopes. The observed signal seems to have multiple statements each with strange symbols. You have been tasked with deciphering this signal as a  computer  scientist  using  theories  of  computation,  since  the  signal  seems  to  pose  a mathematical question as if expecting an answer to be transmitted back to the source of the original signal. The signal is found to have following properties:

x    The signal consists of twelve unique statements and all statements (except the eighth) begin with the same symbol. We will denote this symbol as the initial symbol.

x    Each statement (except the eighth and the last two) seems to list each unique symbol (i.e. mentioned in the rest of the statement) paired with the initial symbol mentioned above as many times as required to ensure all unique symbols are listed.

x    This list of initial/unique symbol pairs is finally followed by a symbol that is only used once throughout the statement. We will denote this symbol as the mid’ symbol.

x    Each statement then continues after this mid symbol with various combinations of the unique symbols that are listed with the initial symbol before the mid symbol.

x    In the first four of the twelve statements, a particular symbol is repeated in all of these four statements, but in increasing number of times. The frequency of the occurrences of this symbol is 2,3,5 and 7.

x    The next two statements seem to repeat one of their two unique symbols (not including the initial symbol). The first of these statements repeats the first symbol once, while the second statement repeats the second of the unique symbols once.

x    The seventh statement seems to contain both the previous two statements within it while describing two unique symbols with the initial symbol. The second of the previous two statements is embedded within two squiggle symbols not seen before followed by the first of the previous two statements outside these two squiggle symbols.

x    The eighth statement simply describes a unique symbol that is never seen in any of the other statements immediately followed by the second statement embedded within two squiggle symbols followed by some short wavey lines, then followed by the first statement in the signal.

x    The ninth statement describes a single unique symbol with the initial symbol and then this symbol is mentioned twice after the mid symbol.

x    The tenth statement contains two unique symbols with the initial symbol and appears to contain the ninth statement within it twice. The second occurrence of the ninth statement appears to be embedded within two squiggle symbols as also seen in the seventh and eighth statements.

x    The  eleventh  and twelfth  statements  repeat the first  four  statements. The  eleventh statement repeats all four of the first four statements, but each seemingly separated by a new small round symbol not seen before ending with this unseen symbol, while the twelfth statement simply states the third statement.

x    The hardware for the calculating any statements is to be a digital computer similar to the desktops we use today.

i.       Describe  what  the  first  four  statements  could  mean  and  write  it  out  using  the conventions developed on Earth.                                                                            (1 Mark)

ii.       Describe what the next two statements could mean, their importance and write it out using the conventions on Earth.                                                                               (1 Mark)

iii.       Describe  what  the  seventh  statement  could  mean  and  write  it  out  using  the conventions on Earth.                                                                                                 (1 Mark)

iv.       Describe what the ninth and tenth statements could mean, their importance and write it out using the conventions on Earth.                                                                    (1 Mark)

v.       Speculate what the eighth statement might represent and what operation the unique symbol that is never seen in any of the other statements represents.          (1 Mark)

vi.       Use  your  own  words  to  describe the  significance  and  mathematical  evidence  (or principle(s)) of the first ten statements of the signal.                                         (1 Mark)

vii.       Fulfill the requirements of the eleventh and twelfth statements by composing a reply to the signal using the points developed above. For the twelfth statement, ensure your answer uses the tenth statement (and any other statements that might be relevant) in developing an answer for this reply. Make sure to describe all details and include any derivations required. Also mention how you would use the computing hardware provided to you to complete these statements.                                                  (3 Marks)

Requirements: Present your answer in less than 2 pages A4 size. All answers should be justified and explained carefully but within the page limit.

 

Problem 6 (0 Marks)

Please specify any assumptions you have made in completing this examination and which questions those assumptions relate to. You may also include queries you may have made with respect to a particular question, should you have been able to ‘raise your hand’ in an examination room.