12 votes

Growth rate of primitive recursive functions

The answer is no, there is no exponential bound on PR. PR contains Knuth's up-arrow functions, Elementary functions, etc. PR is equal to the union of Grzegorczyk hierarchy. Exponential functions ...
Kaveh's user avatar
  • 21.6k
4 votes

Turing meta-oracle

Such an $H$ would let us solve the halting problem: We begin by running $H(H(P))$ until it halts (which it does by assumption on $H$). If the output of $H(H(P))$ is "doesn't halt," then we know $H(P)...
Noah Schweber's user avatar
4 votes

What is the relationship between tail recursion with other recursions?

From the point of view of lambda-calculus "tail call optimization" means take a CPS converted version the program, and eta-reduce continuations of the form $\lambda x. k\;x$ to $k$ Since eta-...
Neel Krishnaswami's user avatar
3 votes

Recursive generic oracles

I think the point is that every notion of genericity has uncountably many generic oracles in it (see, e.g., Fenner-Fortnow-Kurtz-Li Lemma 3.12), but there are only countably many computable sets, so ...
Joshua Grochow's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible