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.
38
votes
1
answer
3k
views
Is the area of the Mandelbrot provably computable?
Recall the Mandelbrot set $M$ is the set of points $c$ in the complex plane such that the sequence $z_0 = 0, z_{n+1} = z_n^2 + c$ is bounded. It is well-known that $M$ is a compact set of positive ar …
- 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
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
17
votes
0
answers
671
views
The topos for forcing in computability theory
My understanding is that forcing (such as Cohen forcing) can be described via a topos. For example this nlab article on forcing describes forcing as a "the topos of sheaves on a suitable site."
My …
- 6,287
15
votes
1
answer
1k
views
Is there a known primitive recursive upper bound on the nth "Zhang prime"
(This question is pure curiosity. Feel free to close it if you feel it is not appropriate for mathoverflow.)
In 2013 Zhang showed that there are infinitely many pairs of primes which are less that 7 …
- 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
11
votes
0
answers
223
views
Savings property: A transformation which turns nonnegative martingales into uniformly integr...
Background
I work in a subfield of computability theory called algorithmic randomness. We have been using martingales as long as probability theory (going back to work of von Mises). However, since …
- 6,287
8
votes
Accepted
Computing the complex roots of a monic polynomial
I'm worried that I'm misunderstanding your question, but I think one could argue there is no satisfactory answer here except to say that this result likely predates "computability" itself.
From the wi …
- 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
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
6
votes
Accepted
Recent trends in effective analysis
(At François's request, my comment in now an answer.)
Yes, it is still an active research area. It however is spread out throughout a number of camps (traditions): The Weihrauch camp, the reverse mat …
- 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
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
4
votes
floating point representation via the perspective of TTE/computable analysis
Background:
For those who don't know, TTE is two things: A type-two Turing machine a theoretical model of computation whose input and output is an infinite sequence of natural numbers. (Such a machin …
- 6,287