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 1946
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.
5
votes
Accepted
Turing degrees of lim infs of computable functions
You need a uniformity requirement in your limit characterization of $0'$, that is, the functions $f_k(n)$ need to be uniformly computable, in that there is a single computable function $f(k,n)$, such …
- 236k
1
vote
Accepted
Resource request (probability theory, computability theory, algebra)
Here are a few areas of overlap for those research topics.
Computable model theory is a nice overlap of computability theory and algebra, since one is looking at the nature of computably effective pr …
- 236k
1
vote
Accepted
What is the computational complexity to verify a P solution with a deterministic Turing mach...
In general it is computationally undecidable to determine if a given program $p$ solves a given decision problem, and also to decide whether it does so in polynomial time. For example, consider the tr …
- 236k
15
votes
2
answers
871
views
Which are the hereditarily computably enumerable sets?
My question is about sets that are computably enumerable with respect to their hereditary membership structure. Specifically, let me define that a hereditarily computably enumerable (h.c.e.) set is on …
- 236k
10
votes
What do we know about the computable surreal numbers?
Let me explicate fuller details about the computable surreal number operations. Let's start by showing that they form a ring.
Theorem. The computable surreal numbers form a ring.
Proof. We have to sho …
- 236k
17
votes
What do we know about the computable surreal numbers?
Here is some partial progress. I claim that the computable surreal numbers include some noncomputable real numbers, confirming my guess in connection with question 2.
For each TM program $e$ we can wr …
- 236k
43
votes
4
answers
3k
views
What do we know about the computable surreal numbers?
The surreal numbers are built up in a natural iterative process, by which at any ordinal stage, if one has two sets of surreal numbers $L$ and $R$, with every number $x_L$ in $L$ strictly below every …
- 236k
7
votes
Splitting 0' into two 1-generic reals
Let us construct $x$ and $y$ in stages from oracle $0'$, so that they are both $1$-generic, but $x\oplus y$ will code $0'$. We specify the binary digits of $x,y$ in stages. At the first stage, we spec …
- 236k
10
votes
Accepted
Natural Numbers
Here is a positive way to interpret your question, and I think this is probably what you had intended to ask about.
Theorem. There is no computable model $M$ on domain $\mathbb{N}$ in a language $L$ i …
- 236k
1
vote
why $L=\{\langle M\rangle\mid M \text{ is a TM that accepts all even number}\} \notin \text{...
You have made an error. One cannot prove that a set is computably enumerable by reducing the halting problem to it. That would be like trying to show that someone is short by proving that they are at …
- 236k
5
votes
Accepted
Infinite multiplicity set of continuous functions
There is no such computable decision procedure, largely because of the same issues underlying Rice's theorem, as mentioned in the comment of Steven Stadnicki. The moral of Rice's theorem is that you c …
- 236k
28
votes
Using Busy Beavers to prove conjectures
Although the other answers point out correctly that the exact value of $\text{BB}(n)$ is independent of ZF for large enough and even moderately sized values of $n$, nevertheless I should like to point …
- 236k
3
votes
Is there an injective homomorphism on the Turing degrees?
This does not answer the question, but let me argue that one can add such an injective homomorphism (for the ground-model degrees) by forcing.
The argument relies on the fact that the Turing degree or …
- 236k
8
votes
Is the usual enumeration of $\mathsf{PA}$ "minimal for consistency strength"?
The cautious enumeration idea in my paper has some affinity with your suggestion.
Joel David Hamkins, Nonlinearity and illfoundedness in the hierarchy of large cardinal consistency strength, arxiv:22 …
- 236k
8
votes
Accepted
Gaps in the ordinals writable by Ordinal Turing Machines with a single countable parameter
The answer is yes. For example, take $\beta=\omega_1$, the first uncountable ordinal. Since there are only countably many programs, there can be only countably many writable ordinals relative to $\bet …
- 236k