Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.