CS370 2005-2006 Test 2 Sample Solutions [Marking scheme in square brackets]

Q1(a).

1. HALTJ <= ADDJ
2. ADDJ
3. HALTJ
4. ADDJ
5. J,y
6.

public ... main(...) {
  int a = 0, b = 0, c = 1;
  // Run J(y)
  c = 0; // or any piece of code that makes c=a+b
}

7. M',a,b,c
8. ADDJ
9. HALTJ
10. HALTJ

[six marks for entry number 6, one mark for each of the others]


Q1(b).

We will prove that ADDJ is Turing-recognisable by showing the existence of a Turing machine M that recognises ADDJ.

M = "On input <J,a,b,c> do the following:
     1. Run J.
     2. Keep track of values in variables a, b, c at each timestep.
     3. If at any point c = a + b then accept."

Since M recognises ADDJ this proves that ADDJ is Turing-recognisable.

[four marks for the machine, one mark for the conclusion sentence]


Q1(c).

The complement of ADDJ is defined as \overline{ADDJ} = {<J,a,b,c> : J is a Java program, a, b, c are integer variables
declared in J, and when J is run c never becomes equal to a + b}.

In part (a) it was shown that ADDJ is undecidable. Therefore either ADDJ or its complement \overline{ADDJ}, or both, must be
outside the Turing-recognisable class. In part (b) it was shown that ADDJ is Turing-recognisable. Therefore this proves that
\overline{ADDJ} is not Turing-recognisable.

[two marks for the definition, three marks for the proof]




Q2(a).

1. ATM <= \overline{LESSJ}
2. \overline{LESSJ}
3. ATM
4. \overline{LESSJ}
5. M,w
6.

public ... main(...) {
  int a = 0, b = 0;
  // Run M on w
  a--; // or any piece of code that makes a<b
}

7. M',a,b
8. \overline{LESSJ}
9. ATM
10. ATM

[six marks for entry number 6, one mark for each of the others]


Q1(b).

We will prove that LESSJ is not Turing-recognisable. In part (a) it was shown that \overline{LESSJ} is undecidable. Therefore
either \overline{LESSJ} or its complement LESSJ, or both, must be outside the Turing-recognisable class. We will prove that
\overline{LESSJ} is Turing-recognisable, by showing the existence of a Turing machine M that recognises \overline{LESSJ},
thus proving that LESSJ must be outside the Turing-recognisable class.

M = "On input <J,a,b> do the following:
     1. Run J.
     2. Keep track of values in variables a and b at each timestep.
     3. If at any point a < b then accept."

Since M recognises \overline{LESSJ} this proves that \overline{LESSJ} is Turing-recognisable, which proves that LESSJ is not
Turing-recognisable.

[four marks for the machine, one mark for the conclusion sentence]


Q1(c).

The complement of LESSJ is defined as \overline{LESSJ} = {<J,a,b> : J is a Java program, a,b are integer variables declared
in J, and when J is run a < b at least once}.

It was proved that \overline{LESSJ} is Turing-recognisable in part (b).

[two marks for the definition, three marks for the proof (whether it was actually proved here or in part (b))]




Q3.

We assume that the worst-cost complexities will arise when the input words are to be accepted rather than rejected.

Time complexity:

Worst-cost time complexity for an input length of 3n: 4n^2 + 4n [ten out of ten marks]
-OR- if the student gave something like 4n^2 + ... [eight out of ten marks]
-OR- if the student gave something with n^2 as the highest power of n [three out of ten marks]

It would be equally valid to give an answer in terms of m=3n, where m is the length of the input. Then the correct answer
would be (4/9)m^2 + (4/3)m.


Space complexity:

Worst-cost space complexity for an input size of 3n: 3n (or equally correct 3n+1) [five out of five marks]

It would be equally valid to give an answer in terms of m=3n, where m is the length of the input. Then the correct answer
would be m (or equally correct m+1).