Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

In this question I asked, if it was possible to define certain functions without the use of the recursion theorem. The answer, among other things, indicated that it theoretically would be possible, but very tedious. To help me get a feeling of how difficult/tedious things will get, if I don't have the recursion theorem at hand, I was pointed to an exercise in the book Gödel,Escher,Bach by Hofstaedter, which, as the answerer indicates, says

characterize the predicate '$n$ is a power of $2$' in explicit fashion - note that 'explicit' here means without the use of recursion or iteration (which is, for these purposes, recursion in disguise)

Now I wasn't able to find said exercise in the book and I also couldn't solve it, which is why I'm kindly asking for a solution here.

If the above has an explicit solution would it also true that every predicate/function/'mathematical object we get via the recursion theorem' can also be obtained without the recursion theorem, but in a very tedious and "writing-intensive" way ?

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.