# Tag Info

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

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

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