COMP2022/2922 Assignment 3
Assignment 3 (80 marks)
Problem 5. (30 marks) Australian hardware engineers at Outback Computing have
developed a new model of deterministic Turing machine, the kangaroo Turing
Copyright By PowCoder代写 加微信 powcoder
machine (KTM). These KTMs are left-bounded, and have the additional property
that, when instructed to move left, they will not merely move left one step but
will instead jump back to the very beginning of the tape.
Spokespeople at Outback Computing have hyped up the announcement, saying
that this represents a leap forward in computing, some even going so far as to
say that these machines violate the Church-Turing thesis with their previously
unknown power to move unboundedly many steps in one. On the other hand,
cynics have decried the project as a boondoggle, criticising the machines as fun-
damentally crippled due to their inability to move one step left, preventing them
from doing the same things normal machines can.
You are neither of these. You are a computer scientist. So you ready your crafty
constructions to show that KTMs are equally powerful as TMs.
1. Implement a program to convert a KTM to a LBTM. (5 marks)
2. Implement a program to convert a LBTM to a TM. (5 marks)
These two show that KTMs are no more powerful than TMs.
3. Implement a program to convert a IM to a LBTM. (5 marks)
4. Implement a program to convert a LBTM to a KTM. (15 marks)
These two show that TMs are no more powerful than KTMs.
Input and output are expected in the usual (Morphett) format.
For the final part (LBTM to KTM), a test case is provided. You are permitted
to hardcode this case. It is worth 5 marks. The remaining 10 marks will be for
hidden test cases. In addition, some public cases for 0 marks are provided.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com