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.