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 12978
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
Are there natural, small, and total recursive functions that are not primitive recursive?
Many decision questions are natural, $0$-$1$ valued, and not primitive recursive (or even recursive). One of the most famous is Hilbert's 10th problem: determine if a polynomial $p$ in multiple varia …
- 6,287
1
vote
Accepted
Are these two definitions of arithmetical hierarchy of real numbers equivalent?
They are the same as the following induction proof shows.
Base case: For $\Sigma_1$, if $x = \sup_i f(i)$ for $f$ computable, then $q < x$ is equivalent to the $\Sigma_1$ statement $\exists i [q<f(i) …
- 6,287
5
votes
Accepted
Random infinite sequences
This of course depends on your definition of "random".
Is 12345678901011121314151617181920212223... random (notice the pattern)? This depends on what properties you want a random string of symbols t …
- 6,287
2
votes
Accepted
Lower-semicomputable supermartingales with bounded increments
(Note: It is very possible I misunderstood the questions.)
By $X$ dominates $Y$ up to an additive constant, do you mean $X,Y$ are supermartingales with bounded increments, and $X(S)>Y(S)-C$ for some …
- 6,287
24
votes
Can a group be a universal Turing machine?
I think the answer is yes, there is such a universal group. Let $G$ be the direct sum group $\bigoplus_{n \in \mathbb{N}} G_n$, where $G_n$ is $\mathbb{Z}$ if the $n$th Turing machine does not halt, …
- 6,287
12
votes
Accepted
Computabillity of packing of spheres with different radii
Yes, it is computable. Use the decidability of the theory of the real numbers $(\mathbb{R}, 0, 1, \times, +, <)$. With a very little standard work, you can define $\mathbb{R}^3$, vector addition, an …
- 6,287
18
votes
2
answers
2k
views
What proofs cannot be relativized
I am afraid this post may show my naivety. At a recent conference, someone told me that there are some arguments in computability theory that don't relativize. Unfortunately, this person (who I thin …
- 6,287
4
votes
1
answer
289
views
Analogy of $\omega$-models in constructive mathematics
I apologize that this question is a bit vague, however that is partially the point.
In subsystems of second order arithmetic, one considers $\omega$-models, these are models of $\mathsf{RCA}_0$ whose …
- 6,287
4
votes
What class of probability distributions do probabilistic turing machines induce?
There are different meanings to induced probability measure of a probabilistic Turing machine. First, lets consider the finitary case since that is easier. A Turning machine with oracle input and na …
- 6,287
3
votes
Accepted
Randomness about coefficients of series
This question is not well formed.
First, I assume by $K(a_1 a_2 \ldots)$ you mean $K(\langle a_1, a_2, \ldots \rangle)$. As the size of the sequence increases (regardless of the choice of $a_i$), …
- 6,287
3
votes
Rationale behind an requirement on Turing machines
It is important to realize that a Turing machine---and even more so, a specific implementation of a Turing machine---is just one of many models of computation. The earliest models of computation, for …
- 6,287
1
vote
Computable Categories in the most direct sense?
Is this what you are looking for?
http://www.cs.man.ac.uk/~david/categories/
- 6,287
7
votes
Are there two computable binary trees such that each has a branch not computing any branch t...
Yes, this is a question about mass problems. It is basically saying there are incomparable $\Pi^0_1$ sets of $2^\mathbb N$ under weak reducibility (a set P is weakly reducible to Q if every element …
- 6,287
3
votes
Accepted
What is the relation between KC and height of rational number?
After thinking about it for a bit, the relationship is as follows for a rational $q$,
$$K(\text{height}\,q) \leq^+ K(q) \leq^+ 2\,\text{height}\,q.$$
This isn't really a surprising or useful relations …
- 6,287
3
votes
1
answer
274
views
What is the extension of the truth-table degrees to Baire Space called?
Recall that for sets $A, B \in 2^\omega$ that we say $A \leq_{tt} B$ if there is a total Turing functional $F \colon 2^\omega \to 2^\omega$ such that $F(B)=A$. This is called truth-table reducibility …
- 6,287