sqrt(2)^sqrt(2) is actually irrational (so you now know two irrationals p & q so p^q is rational)

["Subbarao Kambhampati" <rao@asu.edu>]

First of all, my apologies for the confusion I caused today by not acknowledging the convention of right-associativity for exponentiation. There is really 
no excuse--2^2^n (as in the number of boolean functions over n variables, or the size of the search space of when you have n state variables and you can't observe
the value of any of the) is up there in the haloween nightmares of computer scientists. 

Part 1: 

Coming back to the original question, the existential proof that I showed didn't quite tell you any specific irrational numbers p and q for which p^q is rational (we had two pairs of 
possibilities for p and q). 
In case you are dying to know, sqrt(2)^sqrt(2) is actually
 irrational (actually transcendental  (*)). So a constructive proof for 
our theorem is with p=sqrt(2)^sqrt(2) and q=sqrt(2)

see http://www.math.hmc.edu/funfacts/ffiles/10004.3-5.shtml

(which also points out a more general and easy to understand constructive proof. Consider
  e^{log_e q} for any transcendental number e and rational number
q--which will be q. All you need to show is log_e(q) is irrational and
you can show this easily (If log_e(q) = m/n with integers m and n
without common factors, then 
q = e^{m/n}. This would mean that e is the root of an algebraic
equation x^m - q^n = 0. But the definition of trancendental number is
that it cannot be the root of any algebraic equation!). 


(*)
By the way, transcendental => irrational but not vice versa. In
particular, transcendentals are those irrational numbers that cannot be
roots of any algebraic equation. Two famous examples of course are e
and pi.  Notice that proving that a number e *is* transcendental
involves showing that e^r for any rational number r cannot be rational
(since if it is, then e will be the root of an algebraic equation).
Thus, proving transcendentality is not all that easy.

Part 2:  

Check out

 http://digitalphysics.org/Publications/Cal79/html/cmath.htm

for a nice discussion on the Constructive vs. Classical mathematics--and 
how during Hilbert's time there was a pretty big controversy in mathematics--with mathematicians such as Brouer insisted 
that all math that depended on existential proofs be thrown out.Papa Hilbert had to come to rescue--pretty heady stuff.

You might also look at

http://plato.stanford.edu/entries/mathematics-constructive/

which also talks about the "slick" irrational power irrational can be 
rational proof...