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.
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
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
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
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
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
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
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
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
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
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
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
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
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
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
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