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.
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 …
- 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
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 …
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
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
11
votes
Accepted
Can a stochastic Turing machine output a consistent extension of PA with positive probability?
The answer is no, but it's almost yes. A stochastic Turing machine can find a diagonally non-computable ($\textsf{DNC}$) function ($f$ with $f(x)\ne\varphi_x(x)$ for all $x$) and finding a complete ex …
- 24.8k
11
votes
Can We Decide Whether Small Computer Programs Halt?
You're right that such a project is possible. Calude et al. (http://www.emis.de/journals/EM/expmath/volumes/11/11.3/Calude361_370.pdf) have some results in this direction.
- 24.8k
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
9
votes
Is every non-recursive set in $\Sigma_1$ complete in $\Sigma_1$ (relatively to many-to-one r...
Not every set in $\Sigma_1\setminus\Delta_1$ is $\Sigma_1$-complete.
For Turing reductions it was known as Post's Problem and resolved by Friedberg and Muchnik around 1957. Interestingly there is sti …
- 24.8k
8
votes
Accepted
Reverse Math of High Sets?
In the paper "On a conjecture of Dobrinen and Simpson regarding almost everywhere domination", Binns, Lerman, Solomon and I constructed $\omega$-models of this "high" principle which demonstrate it do …
- 24.8k
8
votes
Accepted
Define Turing machine with algebraic concepts/structures
Yes, there is now Pavlovic's characterization of Turing computability in terms of the monoidal computer, based on monoidal categories. http://arxiv.org/abs/1208.5205
- 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
7
votes
Complexity of Turing Machine behavior
If you restrict attention to TMs that always halt, then:
One measure of complexity of a Turing machine is its running time, the maximum number of steps taken before it halts on inputs of length $n$, …
- 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
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