Search Results
| Search type | Search syntax |
|---|---|
| Tags | [tag] |
| Exact | "words here" |
| Author |
user:1234 user:me (yours) |
| Score |
score:3 (3+) score:0 (none) |
| Answers |
answers:3 (3+) answers:0 (none) isaccepted:yes hasaccepted:no inquestion:1234 |
| Views | views:250 |
| Code | code:"if (foo != bar)" |
| Sections |
title:apples body:"apples oranges" |
| URL | url:"*.example.com" |
| Saves | in:saves |
| Status |
closed:yes duplicate:no migrated:no wiki:no |
| Types |
is:question is:answer |
| Exclude |
-[tag] -apples |
| For more details on advanced search visit our help page | |
Results tagged with computability-theory
Search options not deleted
user 23648
computable sets and functions, Turing degrees, c.e. degrees, models of computability, primitive recursion, oracle computation, models of computability, decision problems, undecidability, Turing jump, halting problem, notions of computable randomness, computable model theory, computable equivalence relation theory, arithmetic and hyperarithmetic hierarchy, infinitary computability, $\alpha$-recursion, complexity theory.
2
votes
1
answer
139
views
Are Cohen Generics Minimal Covers?
Are Cohen generics (in $2^\omega$) minimal covers?
I'm ultimately interested in this question for some more effective notion of forcing but I realized I wasn't sure how to show this even assuming full …
- 44.4k
1
vote
0
answers
97
views
Name For Effective Cantor-Bendixsonish Derivitive
When dealing with a tree (substring closed subset of $\omega^{< \omega})$ a useful operation will frequently be to remove any nodes with finite ordinal rank (i.e., all nodes whose extensions on the tr …
- 3,029
6
votes
2
answers
262
views
Extending polynomial hierarchy above $\omega$
The arithmetic hierarchy is naturally extended to all ordinals via ordinal notations creating a hierarchy for all hyperarithmetic sets. The polynomial time hierarchy is defined analogously to the ari …
- 328
2
votes
0
answers
92
views
Direct construction of an arithmetically high degree below $0^{(\omega)}$
The existence of a high arithmetic degree (meaning the degrees induced by the notion of relative arithmetic definability) below $0^\omega$ can be established by using Harrington/Simpson's constructio …
- 3,029
4
votes
2
answers
126
views
Properties of all relatively computable branches
I'm probably just missing something obvious but suppose that $T \subset 2^{< \omega}$ is a perfect tree with no terminal nodes (what about just $[T]$ non-empty?). If $Y \leq_{T} X$ for all $X \in [ …
- 3,029
1
vote
Properties of all relatively computable branches
Dan's idea above is good but he made a tiny mistake that left $T$ non-perfect so I figured I'd fix that and at the same time give a solution that doesn't use machinery from randomness.
Build r.e sets …
- 3,029
3
votes
0
answers
129
views
Lower Bound of Solutions to P=NP?
Do we at least know that simulating polynomial time non-deterministic Turing machines requires more than a linear slowdown? That is, do we know there is some non-deterministic Turing machine with so …
- 3,029
7
votes
2
answers
224
views
Why does Weihrauch reducibility make use of multi-functions?
This is probably a kinda dumb question, but why is Weihrauch reducibility defined in terms of multi-functions (i.e. why isn't it just the degree structure of regular functions under that reducibility) …
- 4,359
3
votes
1
answer
130
views
A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w_1^{CK}$
In Harrington's mimeographed notes (see here) solving McLaughlin's conjecture he builds reals $f \in \omega^\omega$ which have the property of being $\alpha$-subgeneric defined as follows. He does th …
CommunityBot
- 1
2
votes
Hyperarithmetically least elements in $\Pi^1_1$ sets
I'm pretty sure the claim isn't even true for every $\Pi^0_1$ class (working in $\omega^\omega$ or $\Pi^0_2$ if working in $2^\omega$). It's well known that one can produce a recursive tree in $\omeg …
- 3,029
5
votes
0
answers
190
views
Complexity implications on computability
Are there any known links between complexity theory and computability theory by which I mean non-trivial theorems of the form: If NP $\neq$ co-NP then there is no strong minimal pair of r.e. sets or w …
- 63.9k
2
votes
1
answer
122
views
Splitting $\Pi^0_2$ Singletons?
Given a (non-computable) $\Pi^0_2$ singleton $Y$ are there Turing incomparable $\Pi^0_2$ singletons $X_0, X_1$ with $Y \equiv_T X_0 \oplus X_1$?
What about the same question for arithmetic reducibilit …
- 1,780
1
vote
A $\Pi^0_1$ class of $\alpha$-subgenerics for all $\alpha < w_1^{CK}$
So I emailed back and forth with Leo about this and, after the usual part where I drag the conversation into confusion by getting overly specific, I believe I understand how this is supposed to work.
…
- 3,029
2
votes
1
answer
132
views
Harrington's notes on McLaughlin/Arithmetically incomparable singletons
At one point I had copies of the handwritten notes Leo created about the McLaughlin conjecture and I know a similar set of notes exist titled Arithmetically incomparable arithmetic singletons. I've s …
- 3,029
1
vote
Harrington's notes on McLaughlin/Arithmetically incomparable singletons
Thanks to the individual who helped me out (not sure if they want to be publicly identified). Since I'm sure Leo wouldn't mind I'm posting a link to the McLaughlin notes here (I'll add the other one …
- 3,029