Questions about Turing computability and recursion theory, including the halting problem and other unsolvable problems. Questions about the resources required to solving particular problems should be tagged (computational-complexity).
Questions tagged [computability]
2395 questions
0
votes
1 answer
Proof that $\sup\{\mathcal M(y)| y\le x\}$ is not primitive recursive.
Let $f$ be a function that is recursive but not primitive recursive, and let $\mathcal M$ be a Turing machine which computes $f$. I am trying to prove that the function
$$ g(x) = \sup\{\mathcal M(y)|y\le x\} $$
is not primitive recursive. I know…
Addem
- 5,656
0
votes
1 answer
Is $R\subseteq\mathbb N$ computable if $a\in R\iff\exists n
In this script of Lou van den Dries I encountered (total) functions $\mathbb N^n\to\mathbb N$ and relations $R\subseteq\mathbb N^n$ that are marked as computable.
They are introduced in section 5.1. on page 82.
Addition, multiplication, coördinate…
drhab
- 151,093
0
votes
1 answer
Prove that there is a p.c. function $θ$ such that $λx [ μy [ ψ(x, y) = 1 ] ]$ is not p.c.
Exercise 1.6.28. The partial computable functions are not closed under $μ$. Prove that there is a p.c. function $θ$ such that $λx [ μy [ ψ(x, y) = 1 ] ]$ is not p.c.
Found this little problem that seems so simple which makes it the more interesting…
H.C Manu
- 133
0
votes
0 answers
Why must the proof predicate be rudimentary?
In Boolos, Burgess, and Jeffrey (2007, 5th edition), the following statement is found on p. 224:
"[Consider] that the set of sentences that are provable and the set of sentences that are disprovable from any recursive set of axioms is semirecursive,…
nontology
- 19
0
votes
1 answer
What type of unsolvable theory is Elementary Function Arithmetic ($EFA$)?
It is known that Robinson Arithmetic ($Q$) is essentially undecidable. Is Elementary Function Arithmetic ($EFA$) also essentially undecidable, and what is the Turing degree of its decision problem?
Thomas Benjamin
- 1,291
0
votes
1 answer
If $f$ is computable, $f \geq g$, and $g$ is increasing, then is $g$ computable?
Suppose we are considering functions on the natural numbers. I once asked if $f$ being computable and $f \geq g$ implies that $g$ is computable. I got a negative answer. However, what if we add the additional hypothesis that $g$ is increasing? Then,…
user107952
- 20,508
0
votes
0 answers
Is there a function that grows faster than all computable functions but does not have this property?
Does there exist a strictly increasing function $f$ from $\mathbb{N}$ to $\mathbb{N}$ which grows faster than all computable functions, but which does not have the following property: For all computable functions $g$, there exists an $n$ such that…
user107952
- 20,508
0
votes
1 answer
Not computable but left computable number
I can't find an example of number that is not computable but it is left computable.
In general is already difficult to give example of non computable numbers, but I can't even find any number which is not left computable.
Any help is…
miraunpajaro
- 1,560
0
votes
1 answer
If a problem is $\Sigma^1_1$-hard, it is then not in co-RE?
I am reading a paper where the authors prove that a certain problem is $\Sigma^1_1$-complete; in particular, it is also $\Sigma^1_1$-hard. Does this imply that the problem is not co-recursively enumerable (i.e., that its complement is not…
Jan Tušil
- 145
0
votes
1 answer
A proper general recursive function which grows slower than a primitive recursive function.
Does there exist a general recursive function which is not primitive recursive, which grows slower than some primitive recursive function? In fact, is there such a function which is bounded by a constant function?
user107952
- 20,508
0
votes
1 answer
Is the number of real numbers that satisfy this definition of ε-computability always countable?
My question basically boils down to “is there a minimum error bound to which almost all numbers can be computed to?” It’s possible that the definition I’m inventing here for rigor already exists, but googling got me nowhere.
For any $\epsilon > 0$,…
0
votes
1 answer
Partial and total functions definitions
I have an IT background and I'm trying to find proper and formal definitions of partial and total functions.
I'm unsure about my answers, this is why I'm posting here.
Do you think you could give me some feedback? Do you think the following…
Pol Dellaiera
- 129
- 6
0
votes
0 answers
Encodings of Turing Machines?
My question (in brief) is:
(1) Given an encoding for a TM M (i.e. given $\langle M \rangle$, how do we simulate the actual machine M in a computable manner? and,
(2) Given the actual machine M, how do we get it's encoding (i.e. $\langle M \rangle$)…
Anon
- 2,460
- 1
- 15
- 23
0
votes
1 answer
Is computability theory the only theory that doesn't introduce new axioms to develop its theory?
Generally, a mathematical theory is characterized by its axioms (like group theory). Computability theory is characterized by definitions (such as those of Turing machines or general recursive functions) and doesn't introduce any new unique axioms…
Kalernor
- 21
0
votes
1 answer
Choosing an element of $W_x$ in a computable way
If $W_x$ denotes the domain of the program with number $x$, the question is:
Is there a partial computable function $f$ such that if $W_x$ is not empty then $f(x)\in W_x$, and otherwise, $f(x)$ is undefined?
My attempt is to take $f(x)=x$ if $x\in…
xyz
- 929
- 4
- 12