All Questions
4 questions
2
votes
0
answers
113
views
Description of all total recursive functions where operator is effective?
What is a description of all total recursive functions $g(x)$ for which the operator$$\Phi_g: \mathcal{F}_2 \to \mathcal{F}_1$$defined by the formula$$\Phi_g(f)(x) := g(\mu y(f(x, y) = 0))$$is ...
- 45
11
votes
0
answers
556
views
Various definitions of recursion from ordinal machines
Background: I'm trying to get an intuitive understanding of α-recursion and related concepts in higher recursion theory. Once nice book is Peter Hinman's Recursion-Theoretic Hierarchies, available ...
44
votes
3
answers
5k
views
"Simpler" statements equivalent to Con(PA) or Con(ZFC)?
Given any reasonable formal system F (e.g., Peano Arithmetic or ZFC), we all know that one can construct a Turing machine that runs forever iff F is consistent, by enumerating the theorems of F and ...
- 9,833
3
votes
1
answer
3k
views
What is a universal function?
This question stems from Dick Lipton's recent blog post on the Axiom of Choice. I asked there but got no takers. I promise I'm not an inept Googler, but I couldn't find a satisfactory answer. I ...
- 1,823