To solve the whole question as soon as possible.

Question

(a) Let n > 0 be an integer and Ln be the language of all linear equations a1X1 + a2X2 + · · · + anXn + an+1 = 0 in n unknowns X1, X2, . . . , Xn and over integer coefficients a1, a2, . . . , an, an+1, which have a solution in the integers.

(i) Show that Ln is semi-decidable by describing, in general mathematical terms, an algorithm that takes as input a linear equation a1X1 + a2X2 + · · · + anXn + an+1 = 0 with a1, a2, . . . , an, an+1 in the integers, and halts exactly when this equation has a solution in the integers.

(ii) We now use the fact (stated in the lectures) that Ln is actually decidable. Describe an algorithm, using a decider for Ln as a subroutine, which for any linear equation a1X1 + a2X2 + · · · + anXn + an+1 = 0, with a1, a2, . . . , an, an+1 in the integers, decides whether or not it has an integer solution, and if it does, finds at least one such solution.

(b) Argue that the following languages over the alphabet {a, b, c} belong to the complexity class P. It is enough to give an implementation level description of the relevant Turing machines, and explain why their complexity is polynomial.

(i) {w ∈ {a, b, c} ∗ | |w|a = |w|b = |w|c}

(ii) {w ∈ {a, b, c} ∗ | it is not the case that |w|a = |w|b = |w|c} [3] Note that we use the notation |w|a to denote the number of occurrences of the letter a in w, and similarly for |w|b and |w|c.

Answer 1

(a)

(i) Use dove-tailing, and exhaustively search for a solution.

The procedure terminates if it finds a solution, and fails to terminate if there is no solution.

Next is greater detail.

Define an ordering all all n-tuples (x1, x2, ..., xn) of integers.

(Each n-tuple is a candidate solution).

The ordering is done in groups 0, 1, 2, ...

Group 0 contains the single n-tuple of all zeros (0, 0, ..., 0).

Group k contains those n-tuples (x1, x2, ..., xn) such that each |xi| <= k,

and the n-tuple does not belong to a lower group.

This grouping has the property that every n-tuple belongs to a group.

Secondly, each group is finite, and therefore it can be ordered alphabetically.

This then gives us a sequence of all n-tuples.

Our semi-decision procedure walks through the sequence of n-tuples,

substitutes each n-tuple into the equation, and returns if the

n-tuple is a solution.

(ii)

First query the subroutine whether the given equation has a solution.

If the answer is "yes", then use the procedure in (i) to find a solution.

(b)

It is easy to give a linear algorithm on a machine with random-access memory.

The algorithm scans the given string once, counting the occurrences of a, b, c.

Then it compares the counts for equality (i) or inequality (ii).

A Turing machines suffers only a polynomial slow-down versus RAM machine,

and therefore there exists a Turing machine that can do it in polynomial time.

I do not know whether you are expected to actually provide a Turing machine code,

but I am not going to do it.

Here is just an outline of one potential approach.

First of all we need to assume that the input word w is on the tape with a start-marker to the left and an end-marker to the right.

The Turing machine would have the following states:

LookForA,

LookForB,

LookForC,

LookForStart

In state LookForA:

If scanning end-marker then decided that "|w|a = |w|b = |w|c".

If scanning 'a' then replace it with 'x', enter LookForB, and go right.

Otherwise go right.

In state LookForB:

If scaning end-marker then decided that "It is not the case that |w|a = |w|b = |w|c".

If scanning 'b' then replace it with 'x', enter LookForC, and go right.

Otherwise go right.

In state LookForC:

If scanning end-marker then decided that "It is not the case that |w|a = |w|b = |w|c".

If scanning 'c' then replace it with 'x', enter LookForStart, and go left.

Otherwise go right.

In state LookForStart:

If scanning start-marker then enter LookForA, and go right.

Otherwise go left.

This Turing machine has at most quadratic performance:

It may need the scan the whole input before replacing anything with 'x'.

The number of such scans is at at most as many as the number of letters to replace with 'x'.