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.
19
votes
Accepted
Is Turing degree actually useful in real life?
Application to everyday life
Any time you watch the "spinning beach ball" or "hour glass" on your computer, trying to decide whether it's time to reboot or just wait a little longer, you are doing som …
- 101
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 …
- 12.9k
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
25
votes
Accepted
Languages beyond enumerable
Yes, for starters there is the arithmetical hierarchy, where enumerable = $\Sigma^0_1$ and it continues $\Pi^0_1$, $\Delta^0_2$, $\Sigma^0_2$ etc.
See also the Computability Menagerie.
- 24.8k
6
votes
Accepted
Is 0' of PA degree relative to a non-low set?
No, by the Arslanov completeness criterion $0'$ is only DNC (Diagonally non-computable) relative to low sets. And PA implies DNC.
- 44.7k
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\ …
- 4,727
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