user avatar
user avatar
user avatar
Dan Turetsky
  • Member for 9 years, 7 months
  • Last seen this week
16 votes

For a computable binary tree, is having no computable branches the same as having no probabilistic algorithm for producing branches?

11 votes
Accepted

Can noncomputable sets be distinguishable in $RCA_0$?

10 votes
Accepted

Does every cofinal branch through Kleene's O compute true arithmetic?

10 votes
Accepted

Does permission always work?

9 votes
Accepted

Busy beaver function vs low Turing degrees

8 votes

Undecidable infinite analogs of NP-complete problems?

7 votes
Accepted

Infinite descending chain of Turing jumps with equality

7 votes

Antirandom reals

7 votes
Accepted

What is the Arithmetical complexity of determining whether a 2-ary computable predicate has exactly one infinite column

6 votes
Accepted

About infinite subset of halting probability and 1-random set

6 votes
Accepted

Is $\mathbb{Q}$ the orbit of a continuous function that is computable when restricted to $\mathbb{Q}$?

5 votes
Accepted

How far does this restricted definition on $\mathcal{O}$ goes?

5 votes
Accepted

Where does the deterministic simulation of non-deterministic ω-Turing machines fail?

5 votes

A question on many-one reducibility

4 votes

Is every non-recursive set in $\Sigma_1$ complete in $\Sigma_1$ (relatively to many-to-one reductions)?

4 votes
Accepted

Various notions of Turing reduction for partial functions

4 votes
Accepted

Indices of r.e. sets

4 votes
Accepted

What is the strength of the second-order statement 'an uncountable closed set in $\mathbb{R}$ has a limit point'?

4 votes
Accepted

Is there a "listable" structure of computable dimension $\omega$?

3 votes
Accepted

Borel ranks of Turing cones

3 votes
Accepted

Impredictable subsets of $\mathbb{N}$

3 votes
Accepted

Are all $P$-noncomputable sets $P$-random?

3 votes

Productive sets and indices of constant functions

3 votes
Accepted

Computable images of differences of r.e. sets

2 votes

Disjoint sets of fixed points 2

2 votes

Cohesive set with degree below non-high Martin-Löf random reals

2 votes

Disobedience of some complete r.e. set to some additive cost function

2 votes
Accepted

Kruskal's tree theorem and $\Pi_1$ sentences of linear orderings with finitely many constants

2 votes
Accepted

Is self-escaping without self-dominating possible?

2 votes
Accepted

Does "productive = dimension $\omega$" for computable structures?