comp2022/2922 A3 (90 marks) – Turing Machines s2 2023

• This assignment is due in Week 10 on Sunday 15 October, 11:59pm.

• Submission is on GradeScope.

– For problems 1 and 2, you will submit one PDF with your solutions.

– For problem 3, you will submit your TMs in files named problem 3 1.txt, problem 3 2.txt, problem 3 3.txt.

– For problem 4, you will submit files named run.sh, build.sh and other files you require. The first argument of run.sh, either tm to ptm or ptm to tm, should choose the solution that is run. A skeleton will be provided on Ed.

– For problem 5, you will submit your 2-tape TM in one file named problem 5.txt.

• All work must be done individually without consulting anyone else’s solutions in accor dance with the University’s “Academic Dishonesty and Plagiarism” policies.

• For clarifications and more details on all aspects of this assignment (e.g., level of justification expected, late penalties, repeated submissions, what to do if you are stuck, etc.) you are expected to regularly monitor the Ed Forum post “Assignment FAQ”.

Machine”.

All tapes in this assignment are doubly-infinite. When asked to give a low-level description use Morphett’s format, and its extension to 2 tapes as follows: the instruction

q a b c d L R s

means that if the TM is in state q and reads a on the first tape and b on the second tape then it writes c on the first tape and d on the second, and moves the first tape left and the second tape  right, and changes to state s.

For instance, suppose the question asked you to provide a 2-tape DTM that checks if a string has the same number of 0s as 1s. Here is an answer: 

1. (5 marks) Is the complement of every context-free language Turingdecidable? Give a brief justification of your answer.

2. (5 marks) Suppose that L is the intersection of a context-free language L1 and a regular language L2. Argue that L is in P. You may use any facts proven in the lecture slides.

3. (5 marks) Fix Σ = {0, 1}. Consider the operation dub that maps a string u to the string in which every 0 is replaced by 00. For a language L let dub(L) = {dub(u) : u ∈ L}. For instance, if L = {10, 1001, 11, ϵ} then dub(L) = {100, 100001, 11, ϵ}, and if L = {0 n1 n : n ≥ 0} then dub(L) = {0 2n1 n : n ≥ 0}.

Suppose that L is decidable. Give a high-level description of a decider for dub(L).

4. (5 marks) Consider the language L consisting of the set of strings (SourceM1 , SourceM2 , SourceM3 ) such that L(M1) is not regular, L(M2) is not regular, and L(M1) ∪ L(M2) = L(M3).

Show that L is undecidable. You may only use facts from the lecture slides to do so, e.g., that the acceptance problem TMs is undecidable.

Problem 2. (10 marks) Below is a NTM over input alphabet {a, b}.

1. (5 marks) Describe in one sentence the language that it accepts. Briefly justify your answer. No marks will be awarded for describing how the TM operates.

2. (5 marks) What is the asymptotic time complexity (aka running time) of the NTM? Give your answer in big-Theta notation, and briefly explain your answer.

Problem 3. (20 marks) Fix Σ = {0, 1}.

1. (5 marks) Give a low-level implementation (in Morphett’s format) of a 1- tape DTM that decides the language consisting of strings of the form x1y where |x| = |y|. For instance, 1, 011, 10100 should be accepted, while ϵ, 0, 00, 000, 11, 11000 should be rejected.

2. (5 marks) Give a low-level implementation (in Morphett’s format) of a 1- tape DTM that decides the language consisting of strings of the form x1x. For instance, 1, 010, 10110 should be accepted, while ϵ, 0, 00, 000, 11, 10101 should be rejected.

3. (10 marks) Give a low-level implementation (in Morphett’s format) of a 1-tape DTM that decides the language consisting of strings of the form xyxxz where x is non-empty. For instance, 1011, 000, 01110110110, 1001000010101 should be accepted, while ϵ, 0, 1101, 01101101, 0011101 should be rejected.

Problem 4. (20 marks) Following recent advances in interdimensional technology, a new type of Turing Machine has been developed, the portal Turing Machine (PTM). These machines have the remarkable power to use 0 symbols on the tape as portals, allowing them to traverse unbounded distances in a single step. (0 looks like a portal, you see.)

The semantics of a PTM are that when a machine is in a cell with a 0 and moves left or right, instead of moving one cell, it moves to the next 0 in that direction.

If there is no 0 in that direction, it ”wraps around” the tape and moves to the 0 furthest in the other direction (eg. from the leftmost 0, a ”move left” instruction moves to the rightmost 0). If there is only one 0 on the entire tape, a move left or move right instruction causes it to stay put. Note that in each step, the write instruction is executed before the movement instruction (since this may affect whether a 0 is present when moving).

1. (10 marks) Write a program to convert a basic TM into an equivalent PTM.

2. (10 marks) Write a program to convert a PTM into an equivalent basic TM.

Input will be a machine with input alphabet {0, 1}, tape alphabet {0, 1, , 2, 3}, all states other than the two halting-states (”halt-reject” and ”halt-accept”) are of the form 0, 1, 2, · · · , 9 (i.e. states are single digit numbers and there are at most 10 non-halting states). Your output should be a machine with the same input alphabet. The tape alphabet may be larger. Input and output machines are both expected in Morphett’s format. Particularly, your output should start with the state named 0 (zero).

For full marks, your simulating machines should have at most 100 states and be reasonably efficient. Public tests and guidelines will be provided to judge this efficiency.

Problem 5. (20 marks)

Build a 2-tape DTM S that takes as input an automaton A over input alphabet {0, 1, #} on tape 1, and a string u ∈ {0, 1} + on tape 2, and accepts if u ∈ L(A), and rejects otherwise. The TM S should run in polynomial time.

The input string u is guaranteed to be non-empty, but is otherwise an arbitrary string the alphabet {0, 1}.

The states of our automata are denoted q1, q2, · · · , qn for some n. The initial state is q1, and qn is the only final state (for simplicity). The automaton has no epsilon transitions. Such an automaton will be represented as a string over input alphabet {0, 1, #} as follows. The string encoding the automaton is of the form u1u2 . . . un where each ui is of the form #vi,1#vi,2# . . . #vi,n# where each vi,j ∈ {00, 01, 10, 11} is defined as follows: the first bit of vi,j is 1 iff the automaton has a transition from qi to qj on symbol 0, and the second bit of vi,j is 1 iff the automaton has a transition from qi to qj on symbol 1.

You can assume that the input string to your TM is an encoding of an automaton, i.e., the string matches the regular expression (#((0|1) 2#) n ) n for some n. Subject to this syntactic requirement, the automaton is otherwise arbitrary.

For example, the string

#11#10#00##00#00#01##00#00#11#

encodes the following NFA:

For full marks, your TM should have at most 100 states and be reasonably efficient. Public tests and guidelines will be provided to judge this efficiency.

Your TM should be written in the extension of Morphett’s format to 2-tape machines (described above).