*a*_{0}=(1,0)

*a*_{1}=(*x*,1)

*a*_{2}=(*x*^{2},2)

etc., until

*a*_{y}=(*z*,*y*)

This constitutes a proof if the first tuple is (1,0), the last tuple is
(*z*,*y*), and each tuple is related to the next tuple by a
multiplication of the first part by *x* and incrementing the second part
by 1.

Unfortunately, QCPL doesn't support sequences or tuples. Therefore, we will need to represent a tuple of naturals as a natural and a series of naturals as a natural.

Representing a tuple of naturals as a natural can be done as follows:
the tuple (*a*,*b*) can be represented as
*a***m*+*b*. This works if we can guarantee that *m* is
greater than any *b* we may wish to encode. Because we won't need to
put anything larger than *y* on the right hand side of our tuples, any
*m* larger than *y* will do.

A useful QCPL function for packing and unpacking tuples is
**DIVMOD**.

The function **LT** is true if and only if *b*<*m*.
It, and the other useful comparators, can be defined as follows:

GE(a,b): LE(b,a)

LT(a,b): !GE(a,b)

GT(a,b): !LE(a,b)

NE(a,b): !(a=b)

Representing a sequence, *a*_{0} through *a*_{y}, can
be done by selecting a base, *n*, and taking the sum of
*n*^{i}*a*_{i} for all *i* between 0 and
*y*. This works for any *n* larger than the maximum expected
*a*_{i} value, which, in our case, can be anything at least as
large as (*z*+1)*(*y*+1). (NB - This packing method is a bit
simplistic, as it doesn't work well if we have trailing zero values in the
sequence. It's always possible to just add one to every element to solve this
problem, but for our current purposes this was deemed unnecessary.)

To unpack a single element of a sequence, we can use the following function.

Using this function with *n*^{i} as the value of *v*
will give the element *a*_{i} of the sequence packed into
the natural *a*.

This, however, seems to return us back to where we started: now we need to
be able to verify that a number is a power of *n*. In fact, this is a
much simpler problem than the original one, and that for two reasons:

- We don't need to specify the exponent.
- We can choose an
*n*convenient for us.

This definition uses the definition for **PRIME** given in the
question. In words, it says
(with a few simplifications) that if *x* is a prime power of *p* then
*p* is its only prime divisor.

So, armed with all this, we can verify the three conditions required of a
natural (representing a sequence of tuples) to be our proof. First, it must
begin with (1,0). Letting *a* be the "proof" sequence, *p* be the
prime used for decoding it and *m* be the modulo for decoding tuples inside
it, this condition can be stated as

Second, the sequence must end with (*z*,*y*).

(We don't use the function **ELEMENT** here, because this allows
us to easily verify, as part of the extraction, that this is, indeed, the last
element in the sequence. For all elements other than the last, the *z*
value that satisfies the condition is greater than *p*.)

Third, each element in the sequence (except the last) must be related to the
next element by multiplication of the left part of the tuple by *x* and
incrementing the right part by one.

GT(v*p,a) | /* ignoring the last element of a */

(Ed,Ee,Eq,Er,Es,Et, ELEMENT(a,p,v,d) & ELEMENT(a,p,v*p,e) & DIVMOD(d,m,q,r) & DIVMOD(e,m,s,t) & (q*x=s) & (r+1=t))

With these three conditions, we can now formulate our main function.

(!((x=0)&(y=0))) & /* avoiding 0^0 */

Ea, /* a is our "proof" sequence */

Ep, /* p is the prime used in decoding a */

Em, /* m is used in decoding tuples within a */

GT(m,y) & PRIME(p) & GT(p,m*(z+1)) & CONDITION_ONE(a,p,m) & CONDITION_TWO(a,p,m,z,y) & CONDITION_THREE(a,p,m,x)

Here are some asides you may find interesting regarding this month's riddle:

- The name "Professor G." was a hint, referring to Kurt Gödel, who is famous for his use of naturals that encode proofs in his incompleteness theorem.
- A language quite similar (at least in spirit) to QCPL actually exists. Aptly enough, it is called The Gödel Programming Language.
- The professor is actually wrong when he says that QCPL is Turing-complete. His quantum computer is much stronger than a Turing machine, making QCPL a "Turing-hard" computing model. For example, using QCPL one can easily solve the halting problem (on Turing machines) with very similar tools to those used in the riddle's solution. There is no halting problem on QCPL machines, of course, as these always halt and answer a Boolean immediately.
- Due to the fact that the Gödel Programming Language runs on computers that are more similar to Turing machines than to Professor G.'s fictional quantum computer, from the previous bullet one can safely conclude that not all QCPL expressions can be converted to Gödel expressions and evaluated by an actual Gödel evaluator.
- Bojan Bašić directed my attention to the paper Hilbert's Tenth Problem is Unsolvable where a different solution to the same problem is given. Those of you who thought that QCPL is somewhat restrictive may find it interesting to note that the solution used in the paper also avoids the use of "A", "|", "&" and "!".