Building off of Qiaochu's comment on my answer to a previous mathoverflow question, I would like to know: can the Recursion Theorem, $$\forall e\exists k[\Phi_e\text{ is total }\im …

Let $A$ be a recursive set. $A$ is recursively enumerable, so $A$ may be defined by a $\Sigma^0_1$ formula, i.e. by $\exists \overrightarrow{a} \phi (\overrightarrow{a}, n)$, where …

I am usually confused by questions of the type "could such and such a problem be undecidable", because as far as I know there are two distinct possible meanings of "undecidable". …

(Base theory $RCA_0$)The domination principle says there exists a function g such that g dominates any X-recursive function for any X in the model. i.e. For any $f\le_T X$, $\exis …

Hello. I am a maths undergraduate. I am doing a project about history of mathematics. I am looking for the original solution to Hilbert's 10th problem, or at least the theorems tha …

Background I work in a subfield of computability theory called algorithmic randomness. We have been using martingales as long as probability theory (going back to work of von Mis …

Does an existence of large cardinals have implications in more down-to-earth fields like number theory, finite combinatorics, graph theory, Ramsey theory or computability theory? A …

It is customary to define the class of partial recursive functions by taking the set of primitive recursive functions $PR$ and taking closure over unbound search operation. Do we …

I have a question about primitive recursive functions. Maybe it's trivial, if it is I will move it into math.stackexchange. Is there a primitive recursive function $f$ which is a …

I have a couple of conjectures on recursive functions, that I feel must have been proved or refuted by someone else, but I don't know where to look. In short: 1. The primitive rec …

I failed to get an answer at http://math.stackexchange.com/questions/364061/can-all-programs-reducible-to-ones-with-only-arithmetic-operations-on-inputs-be, so I am asking here. I …

I'm sure this is a fairly basic question, but I can't seem to find a solid answer: My primary question is: Is there a reasonably nice subsystem of second-order arithmetic correspo …

Sometime around 1975, Leo Harrington wrote a set of notes, apparently 13 pages long, entitled Kolmogorov's $R$-operator and the first nonprojectible ordinal. I do not know how wid …

Grzegorczyk-hierarchy divides primitive recursive functions in distinct classes with respect to their growth-rate. It seems that the higher we go the hierarchy, the more tools we h …

The last part of the paper Located Sets and Reverse Mathematics [Journal of Symbolic Logic 65 (1999), 1451–1480] by Giusto and Simpson involves a proof as follows: Given $A$ …