Using your Head is Permitted

"The powers of my Quantum Computing machine are quite extraordinary," he says, "because it is able to parallelize its computations over an infinity of universes, but, unfortunately, I was a bit restricted regarding my choice of programming language for it. Ultimately, I decided on developing my own language, QCPL. It is very user friendly. It's a functional language, much like LISP and CAML, you see."

"So, everything is part of a function, and there are no for loops, no variable assignments and no side-effects of any kind?" asks the student. "Everything is done using recursion?"

"All correct, except the part about the recursion," answers Professor G.. "QCPL doesn't support recursion. It is much like my favorite programming language, FORTRAN, in this regard. A function cannot call itself, and cannot call any function that calls itself, even if it does so only indirectly."

"I'm afraid I lost you," says the student. "Can you explain the syntax for me, please?"

"Nothing is simpler!" exclaims Professor G. "In QCPL, everything is a function that receives naturals (that is, non-negative integers including zero) as its input variables - these are denoted by lowercase letters - whereas the output of each function is a Boolean. Here's an example:"

"This, really, demonstrates almost everything the language has to offer: we begin with either variables or explicit natural constants, mix these together by use of either addition ('+') or multiplication ('*'), then make them into Booleans by comparing them ('=') and all that is defined as a function, where one function is chosen to be the final expression. In the example, the function is called "MULT_PLUS_TWO" and takes three variables. Functions can take any (constant) number of variables, and are denoted by uppercase letters and underscores. Parentheses are also allowed, for disambiguation."

"Anything else?" asks the student.

"Well, the Boolean values also have several Boolean operators that they can be used in. There's '&' for and, '|' for or and '!' for not."

"And where does the strength of Quantum Computing enter this programming language?"

"Ah, I forgot all about that," confesses the professor. "The beauty of the language is that it can evaluate all assignments of input values into these functions simultaneously. Running over parallel universes, it can find out, for example, what all possible outcome values of MULT_PLUS_TWO are. The language supports two constructs that enable you to query the outcome of these evaluations. I call these 'quantifiers'. There's "Ex," which is the syntax for the existential quantifier, and "Ax," which is the syntax for the universal quantifier. The first is true if there is any evaluation of the function that yields 'true'. That is, if there is any natural that can be substituted for x to make the expression immediately following the quantifier true. The second is true if every natural can be substituted instead of x to make the expression following the quantifier true. If the expression is a function of more than just the variable x, for example if it's a function of x, y and z, then the resulting expression will also be a function, but of one less variable. x will be removed from the list of its input variables, leaving only y and z."

"I've lost you completely," admits the student. "Can you give an example of how QCPL can be used to solve any real life problem? How, for example, do you use it to check if a number is prime or composite?"

"Nothing easier!" exclaims the professor.

"The first statement is equivalent to saying that a composite is any natural that can be represented as the multiplication of two naturals, both greater than one. The second statement more or less says that a prime is any natural greater than one that is not a composite," says the professor. "In fact, QCPL is clearly Turing-complete. Let me give you an small exercise to demonstrate this fact. We'll program, together, functions for the sum, the product and the power of two numbers. Here, I'll begin with the first two examples, and you'll finish with the last. We'll begin with the first, defining sums:"

"See? Nothing easier. The function is only true when z is the sum of x and y."

"Yes," says the student, "but -"

"Need another example?" continues the professor. "No problem. We'll do product-taking."

"What did I say? Absolutely nothing to it."

"But, professor -" tries the student again.

"Oh, I'm sure you've grasped the hang of it by now," says the professor. "For tomorrow, show me how you program POWER(x,y,z) that will be true if and only if x^y=z."

Can you help the poor student and solve professor G.'s question? In your answer, please make full use of the ability to define functions, and be sure that all your functions are sufficiently well documented to make the resulting QCPL program legible, as they have a tendency to become obfuscated very quickly.

For your convenience, here is a table summarizing all QCPL operators:

Symbol	Operator name	Input	Output
+	addition	two naturals	a natural
*	multiplication	two naturals	a natural
=	equality	two naturals	a Boolean
&	logical and	two Booleans	a Boolean
|	logical or	two Booleans	a Boolean
!	negation	a Boolean	a Boolean
E	existential quantifier	a variable and an expression	an expression
A	universal quantifier	a variable and an expression	an expression

List of solvers: