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.
6
votes
Accepted
Is every computable real primitively recursively computable?
No. Counterexample: consider a real number $0<x<1$ whose binary expansion is
$$0.x_1x_2\dots$$
where
$$x_{\langle i,j\rangle}=f_i(j)$$where $f_i$ is the $i$th function in a fixed computable list of th …
- 24.8k
3
votes
"Rice (like) Theorem" for primitive recursive functions?
Here is why one cannot get such a result under one reasonably definition of "nontrivial".
Let $g$ be a total recursive but not primitive recursive function.
Consider the property
$$
\varphi(f)\quad …
- 24.8k
4
votes
Accepted
How to approximate non-computably recursive set by computably recursive set
If $S$ is selected randomly under the fair-coin (Lebesgue-Cantor) measure on $2^\omega$ then $S$ will be immune and $S$ will asymptotically contain $1/2$ of the elements of $D$, plus $1/2$ of the elem …
- 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
5
votes
Can we represent computable functions by r.e. sets ?
Some related functions have the following application (D. Myers 2007, unpublished).
Define
$$
A\le B\quad\Longleftrightarrow\quad A=f^{-1}(B) \quad\text{ for some $f$ that maps every $\Sigma^0_n$ se …
- 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
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
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
5
votes
Accepted
Is there a Turing degree which is a strong minimal cover and does not have itself a strong m...
Not known, I think. Traditional ways to produce a SMC $ a $ by completely controlling the structure of $[0, a] $ (starting with Spector 1956, see Lerman's 1983 book) led to c.e. traceable degrees, but …
- 24.8k
7
votes
Accepted
Is DNC/DNR stronger than "prompt" non-computability?
The graph of the course-of-values variant
$$\{(x,(f(0),\dots,f(x))): x\in \mathbb N\}$$
of such a function would be effectively immune. Namely, if we enumerate a subset of this graph then there is an …
- 24.8k
1
vote
Turing degree of finding independent formulas
From your use of "$\downarrow$" it seems you do not require $f$ to give an answer on non-$\omega$-consistent theories.
At least we can get a function $f$ partial computable in $0^{(3)}$ (perhaps you …
- 24.8k
7
votes
(reference request) Chaitin's constant is incompressible
This is in Downey and Hirschfeldt: Algorithmic randomness and complexity, Theorem 6.1.3, which cites
Chaitin, G. Information-theoretical characterizations of recursive infinite
strings, Theoretical C …
- 24.8k
4
votes
Accepted
On fast-growing hierarchy
Let $\varphi_a $ be the $ a $ th partial computable function in a standard way.
Given a recursively enumerable set $ W $, let $ f (n) $ be the maximum of $\varphi_a (b)$ over $ b\le n $ and $ a $ amo …
- 24.8k
5
votes
Relation between Turing degrees and functions computable with them
Your condition is equivalent to $A''\le_T B'$, that is $B$ is high above $A$.
Here $'$ is the Turing jump operator, i.e., the relativized halting problem operator.
In the case $A=0$, $B$ is high. The …
- 24.8k
7
votes
A decision problem for clones
Every finitely generated clone on a finite set is computable.
Indeed, fix $k$. If we want to determine which $k$-ary functions belong to the clone $\mathcal C$, we can start generating functions by c …
- 24.8k