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 4600
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
Accepted
Sets meeting and avoiding computable sets
$X$ is hesive iff $X$ is bi-immune.
Jockusch showed that a Sacks generic has bi-immune-free degree.
Jockusch, C. G. Jr., The degrees of bi-immune sets, Z. Math. Logik Grundlagen Math. 15, 135-140 (196 …
- 24.8k
3
votes
1
answer
103
views
Join-like operation and Medvedev reducibility
Let $\mathcal C, \mathcal D\subseteq 2^\omega$.
Let
$$
\DeclareMathOperator{\Either}{Either}
\Either(\mathcal C,\mathcal D)=\{A\oplus B: \text{either }A\in \mathcal C, B\in\mathcal D\text{, or }B\ …
- 24.8k
13
votes
How did the Baker-Gill-Solovay paper come to be?
Apparently, we would have gotten at least half of the BGS result without any of the three named authors and also without any of the 4 people they credit, all we needed was Dekhtiar. 😊
The Annals of t …
- 24.8k
3
votes
Accepted
Finding 1-generic paths through a tree $T \subseteq 2^{<\omega}$
What conditions can we impose on $T$ that guarantee $[T]$ contains a 1-generic member?
An element that is 1-generic relative to $T$ will not be on $[T]$ unless $[T]$ contains a whole clopen cone $[\ …
- 24.8k
12
votes
Accepted
Is the collection of primitive recursive functions a lower set in the poset of computable fu...
No. Let $g$ be the constant function 1.
Let $\{h_n\}$ be a computable list of all primitive recursive functions and let $f_n(x)=\min(h_n(x),1)$.
So $\{f_n\}$ is a computable list of all primitive recu …
- 24.8k
3
votes
Do all non-computable functions grow faster than computable functions?
Let $f(x)=1$ if we can write $x=2^a3^b$ where $BB(a)=b$, and $f(x)=0$ otherwise. This $f$ is also noncomputable, and takes values only in $\{0,1\}$.
- 24.8k
2
votes
Variously pointed closed sets
Let $\mu$ be a measure on $2^\omega$ which doesn't have a least Turing degree.
This exists by Theorem 4.2 of
Day, Adam R.; Miller, Joseph S., Randomness for non-computable measures, Trans. Am. Ma …
- 24.8k
2
votes
Downward density of w-REA sets under arithmetic reducibility?
Probably still open. James Barnes' dissertation (2018) addresses initial segments under the arithmetic reducibility, but is not specifically about $\omega$-CEA degrees.
Barnes, James S., On the deci …
- 24.8k
2
votes
Accepted
Correct Proof Of ZBC Theorem From Odifreddi? Also Extension Question
A proof of Harrington’s ZBC Lemma can be found in Theorem 2.5 of
Hinman, Peter G.; Slaman, Theodore A., Jump embeddings in the Turing degrees, J. Symb. Log. 56, No. 2, 563-591 (1991). ZBL0745.03036. …
- 24.8k
5
votes
Accepted
10
votes
Accepted
What non-standard model of arithmetic does Hofstadter reference in GEB?
My first guess is that the triples come from the fact that nonstandard countable models of PA look like
$$\mathbb N + \mathbb Z\times\mathbb Q$$
and elements of $\mathbb Q$ can be represented by pairs …
- 24.8k
33
votes
Accepted
Is there a known Turing machine which halts if and only if the Collatz conjecture has a coun...
$\newcommand\PA{\mathit{PA}}$Let's note that this is not a question of whether Collatz is undecidable.
The statement $\neg\mathrm{Con}(\PA)$ is undecidable (by $\PA$, assuming $PA$ is consistent) but …
- 24.8k
6
votes
Accepted
Automorphism group of the Turing degrees
Let $p_i$ denote the $i$th prime number, and let $\oplus$ be the recursive join on $\omega$. Let $\mathcal O$ be Kleene's $\Pi^1_1$-complete set and $\mathcal O'$ its Turing jump.
For any $B$, let $G …
- 24.8k
2
votes
Accepted
Name for "partially complete" invariants in classification problems?
It seems totally fine. Maybe instead of "complete over $C'$" use "complete for $C'$" or "complete invariant of path graphs".
- 24.8k
7
votes
Different notions of computable binary sequence
You can look at automatic structures, replacing Turing machines by finite automata. In that setting, the whole first order theory is decidable (in particular you can add existential quantifiers like y …
- 24.8k