## 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$ ...

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 ...

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 ...

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 ...

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 ...

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,\...

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 ...

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 ...

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{...

Top 50 recent answers are included

#### Related Tags

computability-theory × 831lo.logic × 436

set-theory × 139

computational-complexity × 94

computer-science × 86

reference-request × 81

descriptive-set-theory × 54

model-theory × 50

nt.number-theory × 42

reverse-math × 32

proof-theory × 30

ordinal-numbers × 28

theories-of-arithmetic × 28

co.combinatorics × 27

gr.group-theory × 27

decidability × 27

ct.category-theory × 19

algorithms × 16

diophantine-equations × 14

forcing × 13

constructive-mathematics × 12

soft-question × 11

it.information-theory × 11

formal-languages × 11

lambda-calculus × 11