代做COMP 4003 25F Assignment 3代做留学生Matlab程序

COMP 4003 25F

Assignment 3

Note: before drawing the transition graph of your TM, please slightly describe how your TM works (like the explanation on Lec 9 page 6). This will help the marker to understand your design.

Q1. Design a standard TM to decide each of the following languages. Assume that initially, the input has been written on the tape and the control unit is pointing at the left-most symbol. (15pt for each)

Q2. Computation (8pt for each)

To unify the constructions, we assume that

- the tape symbol “□” stands for anyone of 0, 1, or ⊔ (empty);

- the control units can “stay” at the current position;

- the right-most bit is the least significant bit; and

- each transition of a 2-tape TM is presented as “0 → 1, L; 1 → 0, R”, where 0 → 1, L is the action on Tape 1 and 1 → 0, R is the action on Tape 2. For 3-tape TMs, the presentation is similar.

x) Design a 1-tape TM to calculate the predecessor a binary positive integer a s.t.

- a is a binary string over {0,1};

- a is initially written on the tape;

- the control unit is initially pointing to the left-most symbol; and

- the result is written on the tape as a side-effect.

For example, “1000” is converted to “111” because

(1000)2 一 (1)2 = (8)10 一 (1)10 = (7)10 = (111)2

a) Design a 2-tape TM to convert a binary natural number b to its unary form. s.t.

- b is considered as a binary string over {0,1};

- b is initially written on Tape 1;

- Tape 2 is initially empty and used for the output (side-effect); and

- the unary number is presented as a sequence of x.

For example, “101” is converted to “xxxxx”.

Hint: use Q2x) as a subroutine.

b) Design a 3-tape TM to calculate binary addition s.t.

- the two operands a and b are considered as binary strings over {0,1};

- initially, a is written on Tape 1 and b is on Tape 2; and - Tape 3 is initially empty and for the output.

For example, initially Tape 1 has “101” and Tape 2 has “11”. After computation, Tape 3 should have “1000”.

Furthermore,

- usually, the control units are initially at the left-most symbol of the input, which is the most significant bit in this question; and

- the two operands may have different length.

Unfortunately, these two facts will greatly increase the complexity of the TM construction. Thus, students can use the following assumptions.

i. The control units are initially at the right-most symbol.

ii. The two operands are of the same length.

For those who want to have a challenge and do not use these two assumptions, 1% bonus will be given for each.

Q3. In Lecture 12, we prove ACCEPT is undecidable by a reduction from HALT. And thus, ACCEPT is no “easier” than HALT. In fact, these two are of the same difficulty. So, please accomplish this prove by constructing the reduction ACCEPT ≤ HALT. (8pt)

Q4. By assuming HALT, ACCEPT, EMPTY, EQUAL (languages included in Lec 12) are all undecidable, prove that the language

INTX = {〈M1, M2〉I there is a string w accepted by both M1 and M2}

is undecidable. (8pt)