COMP 3030 Fall 2019 Homework Assignment 4 due Friday, November 1, 2019, 11:59pm Must be submitted on Crowdmark, not UM Learn 1. Consider the following Turing Machine (Q,Σ,Γ, δ, q0, qaccept, qreject): • Q = {A,B,C,D,E} • Σ = {0} • Γ = {0, } • δ defined by: δ(C, ) = (B, 0, R) δ(C, 0) = (A, 0, R) δ(B, ) = (B, 0, L) δ(B, 0) = (D, ,R) δ(D, ) = (D, 0, L) δ(D, 0) = (C, 0, L) • q0 = C • qaccept = A • qreject = E (a) [3 marks] Draw a Turing Machine diagram for the machine defined above. (b) [3 marks] Suppose that all tape squares are initially blank, and the given machine is executed. Write out a list: on line 0 of your list, write a blank tape. For each line i ≥ 1, write the tape contents after executing the machine for i steps (each transition is one step). Some specifics: • As the tape is infinite, there will be an infinite number of blank symbols after the rightmost non-blank symbol: you should only draw the first 3 of these blanks, then stop. When drawing a blank tape, only draw the 3 leftmost squares. • If the tape does not change when taking the ith step, then lines i− 1 and i of your list should look identical. In other words: don’t delete duplicate lines. • If the machine gets stuck in an infinite loop, then stop your list at the end of the first iteration of the loop, and draw an arrow back to the earlier line that has the tape contents where the loop started. (c) [2 marks] What language does the given machine recognize? 2. [3 marks] For this question, refer to the Turing Machine diagram on page 4 of this assignment. The initial tape contents will always be of the form #x#y# where x and y are arbitrary binary strings that both start with 1. The machine will always terminate, and it will modify the tape contents in some way. Your Task: Explain what the tape contents are when the machine terminates. More specifically, imagine that you are writing a “user manual” for someone that wants to use the machine and you want to explain its purpose: what should the user expect as output based on the strings x and y that they provide as input? Hint: think of x and y as binary representations of integers. 1 3. In the first 4 parts of this question, you’ll be drawing Turing Machines. Along with your drawing, you must provide a brief English description of what the machine is doing, i.e., pretend that someone is having trouble understanding how your machine works. In the final part of the question, you will not be asked to draw a machine, but you will need to describe how to put together the machines from parts (a) – (d). You do not need correct answers to parts (a)-(d) to be able to complete part (e). In all parts, you should assume that n ≥ 1. (a) [3 marks] Assume that the tape initially has a string 0n written on it. Draw a Turing Machine diagram that eventually accepts, and, when it accepts, the string $0n# is written on the tape and the tape head is pointing at the $. (b) [4 marks] Assume that the tape initially has a string $0n# written on it. Draw a Turing Machine diagram such that the machine stops with the string $0n# written on the tape, the tape head is pointing at the $, and: • If n = 1, the machine stopped in the accept state qaccept. • If n is even, the machine stopped in a state called qeven. • If n > 1 and n is odd, the machine stopped in a state called qodd. (c) [5 marks] Assume that the tape initially has a string $0n# written on it, where n is even. Draw a Turing Machine diagram that eventually accepts and, when it accepts, the string $0n/2# is written on the tape, and the tape head is pointing at the $. (d) [6 marks] Assume that the tape initially has a string $0n# written on it, where n > 1 and n is odd. Draw a Turing Machine diagram that eventually accepts and, when it accepts, the string $03n+1# is written on the tape, and the tape head is pointing at the $. (e) [4 marks] Consider the following function f that takes a positive integer n as input: if n is even, then f(n) = n/2, and if n is odd, then f(n) = 3n+ 1. For a given n ≥ 1, to “iterate f with initial term n” means: calculate f(n) to get a number n1, then calculate f(n1) to get a value n2, then calculate f(n2) to get a value n3, and keep doing this forever. As an example, if I iterate the given function f with initial term n = 13, I will get a sequence of numbers: 13→ 40→ 20→ 10→ 5→ 16→ 8→ 4→ 2→ 1→ 4→ 2→ 1 · · · Your task: Using the previous parts of this question, describe how to construct a Turing Machine that recognizes the following language: L = {w | w = 0n with n ≥ 1, and iterating function f with initial term n outputs the number 1 at least once} From the example above, we see that 013 ∈ L since the number 1 appears in the sequence at least once when iterating f with initial term 13. I do not want you to draw a machine for this part. I would like you to provide a complete set of instructions so that someone else can combine the machines from the solutions of parts (a) – (d) of this question. You should assign names to certain important states, for example: “Let Q1 be the start state of the machine from part (a) of this question”. Then, you should describe how to link the machines together, for example “add a transition labeled $→ $, L from state Q3 to state Q6”. 2 4. [6 marks] Often, when describing Turing Machine algorithms, we say things like “try each possible binary string”. For example, in Lecture 17, I said “try every possible choice string”. In this question, we’ll see how this could be implemented. On a single tape, I want to be able to iterate through every possible binary string. I want to iterate through them in increasing lexicographic order, i.e., , 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, 110, 111, 0000, etc. More specifically, I want an ‘increment’ operation that does the following: • If the tape contents are 1k for some k ≥ 0, then modify the tape so that it just has the string 0k+1 written on it. Note: a completely blank tape is equivalent to having the empty string written on it. • Otherwise, the tape has some string s ∈ {0, 1}∗ written on it that is not 1k for some k ≥ 0: in this case, modify the tape so that it just has the string s′ ∈ {0, 1}∗ written on it such that the base-10 integer value of s′ is one greater than the base-10 integer value of s. Your task: Draw a Turing Machine diagram that implements the above ‘increment’ operation. Make sure to include a brief English description of how the machine works to help the reader understand your drawing. To clarify: each time I run your machine, it should do one ‘increment’ operation to get the next binary string from the list written above. For example, starting with a blank tape, if I run your machine 5 times consecutively, the tape contents should be 10, then after the sixth time the tape contents should be 11, then after the seventh time the tape contents should be 000, and so on. 5. In this question, assume that each function is of the form f : N → N, i.e., takes one non-negative integer as input, and outputs one non-negative integer. A function f is totally computable if there is an algorithm that always calculates the correct value of f(n) for every given n. An equivalent definition using Turing Machines is the following: a function f is totally computable if there is a Turing Machine M such that, for every n ≥ 0, if 0n is initially on the tape, then running M will eventually halt and the tape contents will be 0f(n). As an example, question 3(d) on this assignment can be used to prove that f(n) = 3n + 1 is totally computable. You can probably write one-line programs in your favourite programming language to prove that many other functions, such as f(n) = n2 + n+ 1, are totally computable. In this question, we will prove that there exists at least one function that is not totally computable, i.e., there is no algorithm that can correctly calculate its value. We start with the following observations, which you can use without proof: for each totally computable function, there exists at least one Turing Machine
that can correctly compute its value. We saw in class that the number of Turing machines is countably infinite, which implies that the number of totally computable functions is also countably infinite. This means we can make an infinite list of all totally computable functions: g1, g2, g3, g4, . . .. (a) [5 marks] Using the Diagonal Method, prove that there exists a function f : N → N that is not totally computable. Note: while it might be useful for you to draw a table when trying to figure out the solution, marks will only be awarded for giving a formal definition of f and writing a proof that it is not totally computable. (b) [2 marks] Using part (a), prove that there does not exist an algorithm that takes two parameters a, b ∈ N and always outputs the correct value of ga(b). 3 0 ! 0x; R 1 ! 1x; R 0 ! 0; R 1 ! 1; R # ! #; R # ! #; R 1 ! 1; R 0 ! 0x; L 1 ! 1x; L 1x ! 1x; L 0x ! 0x; L # ! #; L 1x ! 1x; R 0x ! 0x; R # ! #; R 1 ! 1; R 0 ! 0; R # ! #; R Accept ! 0; L ! 1; L # ! #; R 1 ! 1; L 0 ! 0; L 1x ! 1x; R 0x ! 0x; R 1x ! 1x; R 0x ! 0x; R 1x ! 1x; R 0x ! 0x; R # ! #; R 1 ! 1; R 0 ! 0; R # ! #; R 1 ! 1; R 0 ! 0; R 0 ! 0; R # ! #; R # ! #; L # ! #; L # ! #; L 1x ! 1; L 0x ! 0; L 1 ! 1; L 0 ! 0; L 1x ! 1; L 0x ! 0; L 1 ! 1; L 0 ! 0; L 0 ! 0; R 1 ! 1; R # ! #; R 4
