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.
26
votes
2
answers
2k
views
Decidability of 3 body problem
Is there a result showing that something along the lines of the three body problem is undecidable? Or are they known to be decidable or neither?
I mean problems along the lines of the following formu …
- 3,029
8
votes
1
answer
395
views
Good source for admissible set theory?
So I need to writeup some old results of Harrington's which imply various results about admissible ordinals. I've never really learned admissible recursion theory so what's a good reference?
- 3,029
7
votes
1
answer
155
views
Join Density in R.E. Degrees: Are there r.e. B, C with all r.e. X below B computable or C jo...
Are there r.e. sets $B >_T 0$ and $C >_T 0$, $C \not\geq_T B$ such that for all r.e. $W \leq_T B$ either $W \leq_T 0$ or $C \oplus W \geq_T B$. The explanation for the title is because one can think …
- 3,029
7
votes
1
answer
166
views
2-REA PA degrees
Remember that an n-REA set is a set of the form $A_0 \oplus A_1 \oplus \cdots \oplus A_n$ with $A_n$ relatively r.e. in $A_m, m<n$ (so $A_0$ is r.e.) and that a degree is PA just if it computes a path …
- 3,029
7
votes
0
answers
217
views
$\Pi^0_2$ singleton of minimal arithmetic degree?
Is it known if there is a $\Pi^0_2$ singleton of minimal arithmetic degree?
To elaborate a bit, this is asking whether there is a non-arithmetic set $X$ such that for any $Y$ arithmetic in $X$ either …
- 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) …
- 3,029
6
votes
Reference for a "recursive" fragment of infinitary logic?
Yes, these are called computable infinitary formulas. I recommend the following references (as a matter of taste I prefer them to Barwise...don't remember why...possibly just it's more canonical in m …
- 3,029
6
votes
0
answers
248
views
$\omega$-models of $\mathbf{\Sigma^1_1}-DC$ and $\mathbf{\Delta^1_1}-CA$
So what is needed to demonstrate something (say like $L_{\omega_1^{CK}}[a]$ is a $\omega$-models of $\mathbf{\Sigma^1_1}$-$DC$ or $\mathbf{\Delta^1_1}$-$CA$? It's not like I don't understand what the …
- 3,029
6
votes
3
answers
438
views
Is $0^{(\omega)}$ a minimal cover in the arithmetic degrees
Is it known if $0^{(\omega)}$ a minimal cover in the arithmetic degrees? In the Turing degrees to show that $0'$ (indeed $0^{(n)}$) isn't a minimal cover one uses the density of r.e. degrees. Howeve …
- 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 …
- 3,029
5
votes
1
answer
170
views
Given B,C incomplete, incomparable r.e. sets must C compute low r.e. set avoiding cone below...
I feel like there must be a classical result answering this question (or easily modified to do so) but a quick flip through Soare didn't produce anything so rather than waste time I figured I'd just a …
- 3,029
5
votes
1
answer
197
views
Does every cuppable r.e. set cup with a low set?
Remember, that an incomplete r.e. set $A$ is cuppable if there is an incomplete r.e. set $B$ such that $A\oplus B \equiv_T 0'$. It's relatively easy to build a low cuppable set but my question is whe …
- 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 …
- 3,029
5
votes
0
answers
205
views
Status of Problems in 102 problems in mathematical logic
Is there any location that records the current status of the problems in 102 problems in mathematical logic? Or, better yet, serves as a status board for open problems in mathematical logic? Mathove …
- 3,029
5
votes
Theorems in set theory that use computability theory tools, and vice versa
My favorite are the results in computability theory that rely on Martin's cone theorem (if A is sufficiently definable degree invariant set (Certainly if Borel but I think more) then either A or it's …
- 3,029