Questions tagged [computability-theory]
computable sets and functions, Turing degrees, c.e. degrees, models of computability, primitive recursion, oracle computation, models of computability, decision problems, undecidability, Turing jump, halting problem, notions of computable randomness, computable model theory, computable equivalence relation theory, arithmetic and hyperarithmetic hierarchy, infinitary computability, $\alpha$-recursion, complexity theory.
1,131 questions
-3
votes
0
answers
106
views
Does this theorem about Turing machine execution traces follow from the hardware lemma alone, without Kolmogorov's Coding Theorem? [closed]
Given a Turing machine executing on a universal machine $U$, define:
$c_0$ — the initial (null) configuration before any instruction is fetched
$\tau(P) = (c_0, c_1, \ldots, c_n)$ — the execution ...
- 103
17
votes
0
answers
214
views
Are the Chaitin-style incompleteness theorems a consequence of Lawvere's Fixed Point Theorem?
Lawvere's famous fixed point theorem shows that in any Cartesian-closed category with objects $X,Y$, if there is a weakly point-surjective morphism $f:X\to Y^X$ then every endomorphism $g:Y\to Y$ has ...
- 171
6
votes
1
answer
621
views
Halting problem and "hardest to predict" programs
I was trying to formalize a notion of "hardest to predict" programs, but I feel like this concept (or something close) must have been studied before. Hence, I post here with a "...
- 211
3
votes
1
answer
128
views
How large is the smallest ordinal $\gamma$ such that every ITTM-countable-limit recognizable $x \subseteq \omega$ is an element of $L_\gamma$?
It is known that every ITTM-recognizable real number $x$ (i.e., $x \subseteq \omega$) is an element of $L_\sigma$, where $\sigma$ is the smallest ordinal such that $L_\sigma \prec_{\Sigma_1} L$ (see ...
- 1,071
9
votes
0
answers
109
views
Does $\mathsf{IZF}_{\mathrm{Rep}}$ prove that $L_{\omega_1^{\mathrm{CK}}}$ is a model of $\mathsf{IKP}$ (with $\Sigma_0$-collection)?
Let $\def\IZF{\mathsf{IZF}_{\mathrm{Rep}}}\IZF$ be intuitionistic Zermelo-Fraenkel set theory with the replacement scheme. (See this SEP article for a definition of the replacement scheme.) Let $\def\...
- 21.4k
6
votes
1
answer
419
views
References on computability and intuitionism
I'm not sure if my question makes sense, but I'm currently studying computability theory, and intuitionistic logic is something that really interests me. My question is, are there any current research ...
- 239
7
votes
2
answers
181
views
Reference request for uniform separation of closed sets
I am looking for a reference for the following separation principle.
Let $(C_n)_{n \in \mathbb{N}}$ and $(D_n)_{n \in \mathbb{N}}$ be
sequences of closed and non-empty sets in the unit interval ...
- 4,411
4
votes
1
answer
394
views
Recursion theory of $0^\sharp$?
As the notation suggests, one can foolishly view $0^\sharp$ as an inner-model theoretic $0'$.
Has any existing research addressed any problems of the following forms, possibly weakened/strengthened ...
- 355
4
votes
1
answer
522
views
What did Sacks mean by this remark on the admissible minimal degree problem in the Chong and Yu interview?
There is this interview with Sacks from 2009 with a transcript that can be read in the Chong and Yu monograph. At one point in the interview, the problem of minimal degrees for admissible ordinals is ...
- 1,671
6
votes
0
answers
363
views
A version of Rosser's trick in computability
While thinking about various problems in computability, I have twice encountered the following “trick” which I can illustrate on a simple but amusing proposition:
Proposition: Let $h\colon\mathbb{N} \...
- 41k
2
votes
0
answers
171
views
Designing turing machines that are nonhalting unprovably from strong large cardinals
The busy beaver function BB(n) is typically defined as the maximum amount of steps any of the n-state turing machines (TMs) will take before halting. BB(n) not only grows faster than any computable ...
- 123
7
votes
1
answer
475
views
Must all tame expansions of the reals be provably complete?
Say that a (first-order, finite-language, recursively-axiomatizable) theory $T$ is provably complete iff there is an index $c\in\mathbb{N}$ such that $W_c$ (viewed as a set of sentences via some fixed ...
- 19.1k
6
votes
2
answers
302
views
Is there a transitive model of $\mathsf{ATR_0^{set}}$ whose height is neither admissible nor limit admissible?
The theory $\mathsf{ATR_0^{set}}$ is a version of set theory, comprising Extensionality, Foundation, closure under rudimentary functions, Infinity, Axiom of Countability (Every set is countable), and ...
- 3,905
8
votes
2
answers
392
views
On arithmetically recursible Harrison order
A Harrison order is a recursive ill-founded linear order with no hyperarithmetical descending sequence. Harrison stated in his Recursive Pseudo-Well-Orderings that Harrison order satisfies parameter-...
- 3,905
10
votes
2
answers
361
views
“Uniformly” minimal pairs of Turing degrees
For $f,g\colon\mathbb{N}\to\mathbb{N}$, consider the following three conditions:
(at least) one of $f$ or $g$ is computable;
there exists $e \in \mathbb{N}$ such that for all $p,q,m,n \in \mathbb{N}$...
- 41k