Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: YSYY66

MATH3306 Assignment 4

Semester 2/2021

Marks will be deducted for sloppy working. Clearly state your assumptions and conclusions, and justify all steps in your work.

Q1 Design a numerical Turing machine that computes the function f : defined by f(n) = n/2 . Show all the states of the machine, and give a brief explanation as to how it works.

(10 marks)

Q2 Suppose you have numerical Turing machines that computes the functions f : and g : . Describe how you would build a numerical Turing machine to compute the function h: defined by h(n) = f(n) + g(n).

For convience, you are welcome to use a tape alphabet larger than just {0, 1}. However, your input and output should be expressed in unary (using a sequence of 1s) in the usual manner.

(It is clear that h is partial recursive, and so we already know it is computable. Your task is to describe how you would build a Turing machine that actually computes it.)

(10 marks)

Q3 Recall that the halting problem asks to compute a function g : , where g(n, y) = 1 if is defined, and g(n, y) = 0 otherwise. We know now (as Turing did in the 1930s) that this is undecidable.

Your task is to determine whether the following functions are decidable (i.e., whether they can be computed by a Turing machine, or equivalently, whether they are partial recursive). You must prove your answers correct.

(a) h: , where h(n, y) = 1 if is defined, and h(n, y) is undefined otherwise;

(b) k : , where k(n, y) is undefined if is defined, and k(n, y) = 0 otherwise.

Essentially, each of h and k tests “one direction” of the halting problem only.

You may, if you wish, use the fact that the halting problem is undecidable.

(10 marks)