MathOverflow
Dan Turetsky's user avatar
Dan Turetsky's user avatar
Dan Turetsky's user avatar
Dan Turetsky
  • Member for 11 years, 5 months
  • Last seen this week
Profile Activity

40 Answers

Score Activity Newest
7 votes
Accepted

Complexity of |a| < |b| for ordinal notations?

1 vote

If the join of two degrees compute one of their jumps, what can we say about the jump of the other degree?

8 votes

What are some interesting applications/corollaries of Kleene's Recursion theorem?

5 votes
Accepted

What's the measure of all 1-generic sets?

2 votes
Accepted

Computable functionals avoiding embeddings of linear orderings

10 votes
Accepted

Does permission always work?

6 votes
Accepted

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

3 votes
Accepted

Borel ranks of Turing cones

8 votes

Undecidable infinite analogs of NP-complete problems?

1 vote
Accepted

Analytic sets and Turing determinacy

7 votes
Accepted

Infinite descending chain of Turing jumps with equality

4 votes
Accepted

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

2 votes
Accepted

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

4 votes
Accepted

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

10 votes
Accepted

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

1 vote

Fixed points of recursive functions with finite range

3 votes
Accepted

Impredictable subsets of $\mathbb{N}$

5 votes
Accepted

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

1 vote
Accepted

Non-relativized, Computable and Schnor randomness w.r.t a measure

1 vote
Accepted

Kurtz randomness and supermartingales with infinite *limit*

3 votes
Accepted

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

2 votes
Accepted

Is self-escaping without self-dominating possible?

2 votes
Accepted

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

18 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$?

7 votes

Antirandom reals

5 votes

A question on many-one reducibility

1 vote

A ("Rice-like") conjecture about the decidability of primitive recursive (PR) problems

10 votes
Accepted

Busy beaver function vs low Turing degrees

4 votes

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

1
2