New answers tagged computability-theory
0
votes
$\Pi^0_2$ singleton of minimal arithmetic degree?
Less an answer than a potential sketch at an approach right now but I wanted to put it up here just in case it was right (but it's way too simple to be right)
Let $A$ be a non-arithmetic $\Pi^0_2$ ...
- 1,515
0
votes
How large is the supremum of halting times of Infinite Time Turing Machines, assuming that halting times are bounded and inputs are arbitrary?
This and related questions about decision times of ITTMs are addressed in this paper:
"Decision times of infinite computations"
https://arxiv.org/abs/2011.04942
The ordinal you are asking ...
- 1
7
votes
Does permission always work?
Dan's answer is very nice and should be the accepted answer. However, I thought it might be worth pointing out that there's a much easier counterexample to your first question (with the stricter ...
- 426
9
votes
Accepted
Does permission always work?
No, there is a counterexample. The idea is that the use of the computation $X \le_T ran(g)$ can be much worse than identity, and since we only care about the reduction in one direction, we can drive ...
- 2,159
3
votes
Accepted
Existence of an inseparable minimal pair
Here's a construction of a computably inseparable minimal pair. I believe that it is not hard to modify this construction to give c.e. sets by using a priority construction. However, I have not ...
- 426
8
votes
Accepted
How often are forcing extensions of countable computably saturated models of $\mathsf{ZFC}$ computably saturated?
The answer to Question 1 is positive (thus the answer to Question 2 is also positive). More explicitly, the positive answer to Question 1 follows from the following well-known facts:
Lemma 1. $(M,\...
- 14.5k
4
votes
Comprehension axiom who helps in the opposite direction
There are many such examples in higher-order Reverse Mathematics. I discuss a couple and indicate a relevant paper of mine related to David's. As usual, let RCA$_0^\omega$ be Kohlenbach's base theory ...
- 1,859
9
votes
Accepted
Comprehension axiom who helps in the opposite direction
David Belanger's work is relevant.
The principle $\mathsf{WKL_0}$ (= "Every infinite subtree of $2^{<\omega}$ has an infinite path") is not literally a comprehension principle, so its ...
- 21.7k
1
vote
Accepted
Natural strong logic with Barwise compactness property
A very nice family of examples is provided by Harrington's 1980 paper Extensions of countable infinitary logic which preserve most of its nice properties. Harrington shows that if we expand $\mathcal{...
- 21.7k
Top 50 recent answers are included