COMPSCI 350FC 2024
Assignment 2: Turing Machines
There are four problems listed below. To get full credit for this assign- ment you need to complete all of them. If you are stuck or confused by the wording of any of the problems, please ask your tutor, lecturer or Piazza.
You are allowed to discuss the problems with your peers and refer to online materials, but you are not allowed to share solutions or copy ma- terials from any source. You may find the academic integrity rules at https://academicintegrity.cs.auckland.ac.nz/.
To get full marks you need to show all working unless a question explicitly states not to. You do not always need to provide fully formal proofs, but your arguments should be mathematically rigorous.
You should submit via Canvas a single typed PDF file containing the answers to the written questions. A handwritten submission is not accept- able. You may use a tool such as https://madebyevan.com/fsm/ to draw automata diagrams. We will allow neatly handwritten diagrams at your own risk, so if the marker cannot understand your diagram, that is on you.
Please try to submit your assignments no later than 5 min before the due
time. Late assignments will not be accepted. If you need an extension due to
illness or other personal circumstance, please email [email protected] as early as possible before the due date.
Best of luck, and enjoy the problems!
Question 1. [10 marks]
Implement Reverse Ternary addition on a Turing machine M with Σ = {0, 1, 2}. Your Turing machine’s tape should initially have 2 strings of digits in Reverse Ternary, separated by a space. If your Turing machine ends in an accepting state, its tape will contain the sum of the two strings, in Reverse Ternary.
(a) Give both a state diagram, and an implementation-level description of M that clearly shows how your machine works.
You do not need to prove its correctness.
(b) Confirm that M yields the correct sum when adding the Reverse Ternary strings 12 and 221.
That is, for each of these two strings, provide a sequence of configura- tions that yieldM the next member of the sequences, that starts with the initial configuration and ends in an accepting configuration with their sum on the tape.
Note: Ternary is a number system like Binary or Decimal, but with 3 symbols. Reverse Ternary has the lowest digits on the left. Using Reverse Ternary should make your Turing machine easier to implement.
Example: The number 19 in Decimal notation is 91 in Reverse Decimal, 201 in Ternary, and 102 in Reverse Ternary.
Question 2. [10 marks]
Provide a proof that Turing machines with infinite tape to both the left and right have the same power as standard Turing machines. Use the general approach / intuitions sketched in the lecture slides.
You can use the proofs for Multi-tape and Non-deterministic Turning Machine power equivalence from the lectures / slides / Sipser as guides to the level of detail and rigour required, but not as templates. That is, you must write your own proof, not copy-paste/edit from the slides or book (or internet).
Question 3. [10 marks]
Assume that there is a Turing machine M with Σ = {0, 1} that decides: L1 = {w ∈ {0, 1}* | w contains fewer 1’s than 0’s}.
(a) Using closure results, prove that L2 is Turing-decidable, where: L2 = {w ∈ {0, 1}* | w contains the same number of 1’s and 0’s}.
(b) Now suppose M is a Turing-recogniser but not a Turing-decider. Use closure results to prove that L2 is Turing-recognisable, or explain clearly why closure results can’t prove this.
Question 4. [10 marks]
We asked ChatGPT: “If a Turing Machine could have all the Real numbers in their tape alphabet, how (if at all) would this change its computational power?” Critique both of ChatGPT’s answers provided below:
(A) If a Turing Machine could have all the real numbers in their tape alphabet, it would not change its computational power. Turing Machines are equivalent in power to other models of computation, such as the Lambda Calculus and the Recursive Functions. They are capable of computing any function that is computable by any other model of computation. This prop- erty is known as Turing Completeness. The Turing Machine’stape alphabet is not a limiting factor in its computational power. The tape alphabet can be finite or infinite, and it can include any symbols, including real numbers. However, the use of real numbers as tape symbols would not expand the set of functions that a Turing Machine can compute. This is because any real number can be represented as a finite or infinite sequence of symbols from a finite alphabet. Furthermore, the use of real numbers as tape sym- bols would introduce additional complexity and inefficiency in the Turing Machine’s operations. Manipulating real numbers would require additional computational resources and would slow down the machine’s operations. Therefore, the inclusion of real numbers in the Turing Machine’s tape al- phabet would not change its computational power.
(B) If a Turing Machine could have all the real numbers in their tape alphabet, it would significantly change its computational power, making it more powerful than a standard Turing Machine. In a standard Turing Machine, the tape alphabet is typically finite, consisting of a fixed set of symbols. However, if the tape alphabet were expanded to include all real numbers, it would enable the machine to perform operations on an infinite range of values, which is not possible with a finite tape alphabet. With this expanded tape alphabet, the Turing Machine could perform computations on uncountably infinite sets of values, allowing it to solve problems that are not computable by standard Turing Machines. For example, the ma- chine could perform continuous computations, such as solving differential equations or computing integrals, which are not possible with a finite tape alphabet. Furthermore, the use of real numbers as tape symbols would allow the Turing Machine to represent and manipulate continuous functions, mak- ing it more versatile in solving mathematical problems. It could also provide more accurate results in scientific simulations. In summary, the inclusion of all real numbers in the Turing Machine’s tape alphabet would significantly expand its computational power, making it capable of solving a wider range of problems that are not possible with a standard Turing Machine.