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 44362
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.
6
votes
2
answers
755
views
Let Abit$(x,y,n)$ be the $n$th bit of Ack$(x,y)$ (the Ackermann function). Is the function "...
Example of "Abit": Ack$(2,3)=9=1001_2$ (base 2). Thus Abit(2,3,3)=1
(the leftmost bit of $1001$. The index of the rightmost bit is 0)
Question 1: Is the function "Abit" primitive recursive (PR)?
…
- 489
3
votes
0
answers
294
views
Equivalence of LOOP (primitive recursive functions) and of SRL (reversible transformations) ...
This is a question about the decidability of program equivalence.
Primitive recursive functions correspond exactly to the functions
that can be implemented on a specific register machine usually
name …
- 489
6
votes
2
answers
2k
views
Are there proofs of Rice Theorem without using the undecidability of some problem?
Most proofs of Rice theorem seem to be based on the undecidability of
the halting problem. They are "reduction-based".
Are there "direct" elementary proofs, perhaps based on diagonalization?
I think …
- 489
9
votes
5
answers
2k
views
Are there natural, small, and total recursive functions that are not primitive recursive?
In a sense the Ackermann function is not primitive recursive (PR)
because it grows too fast.
Are there total recursive, not PR, small functions?
Using a diagonal argument,
we may define a total rec …
- 489
5
votes
2
answers
375
views
A ("Rice-like") conjecture about the decidability of primitive recursive (PR) problems
Question: is the conjecture below true?
Consider decision problems in which the instance is (the PR index, definition,
or LOOP program of) a primitive recursive function.
Denote the PR function (with …
- 489
8
votes
3
answers
1k
views
"Rice (like) Theorem" for primitive recursive functions?
As primitive recursive (PR) functions seem to be so important
(see for instance Kleene normal form Theorem) we may expect that
many decision questions related to PR functions are undecidable.
(INPUT) …
- 489
5
votes
2
answers
747
views
Is every non-recursive set in $\Sigma_1$ complete in $\Sigma_1$ (relatively to many-to-one r...
Most well known sets in $\Sigma_1 \setminus\Delta_0$, such as the
Halting problem, are complete in $\Sigma_1$, relatively to the
many-to-one reduction. In fact I don't know any example of a (non r …
- 489