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 9896
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.
7
votes
2
answers
1k
views
Models of computation with decidable halting problem?
There are numerous examples of models of computation in which all programs halt, for example primitive recursion.
Are there (non-trivial) examples of models in which only some programs halt, but the …
- 3,475
11
votes
1
answer
1k
views
Machine model for primitive recursion?
General computable functions can be described either functionally (in terms of closure of
the coordinate functions, constant functions, composition, primitive recursion, and $\mu$-recursion), or in te …
- 3,475
1
vote
Accepted
Equivalence of monadic axioms
The comment showed that decidability of axiom equivalence is implied by decidability of pure logic. (I.e. to decide if $\Theta$ and $\Theta'$ are equivalent, it is equivalent to decide if $\vdash \The …
- 3,475
15
votes
1
answer
813
views
Undecidable theories easier than $Q$
Most proofs of undecidability for various theories (pure logic with binary relation, group theory, etc.) show that the natural numbers and Robinson's $Q$, in one form or another, can be encoded approp …
- 3,475
16
votes
2
answers
3k
views
Can randomness add computability?
I have been looking at Church's Thesis, which asserts that all intuitively computable functions are recursive. The definition of recursion does not allow for randomness, and some people have suggested …
- 3,475
3
votes
Graph properties: definability and decidability
Almost any language I can think of (FO theories, etc) isinvariant under isomorphism, i.e. if $\cal A$ satisfies the sentence $\sigma$ then so does $h(\cal A)$ for any isomorphism $h$. Hence if a class …
- 3,475