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
1
vote
1 answer
Is there a c.e. set $A\subset\mathrm{Tot}$ such that $A$ contains an index for every total computable function?
Phrased differently, is there a computable list of (indices for) total computable functions, such that every total computable function appears at least once? If true, it would mean that even though we can't list all the total computable algorithms,…
A. Howells
- 845
1
vote
1 answer
For a one-to-one function is the pullback of a recursively enumerable set $f^{-1}[W_e] = W_{g(e)}$ where $g$ is one-to-one?
Let $\phi_e : \mathbb{N} \to \mathbb{N}$ be the recursive function coded by $e$ and $W_e = \{ x : \phi_e(x) \text{ is convergent}\}$.
A set $A$ is recursively enumerable if $A = W_e$ for some $e$.
Is it true that given a recursive one-to-one…
zrbecker
- 4,048
1
vote
1 answer
Application of Generalized Rice's Theorem
I'm trying to understand how to apply the generalized Rice's theorem to prove that a problem is Turing-Recognizable.
Suppose that I have two TMs and I have to evaluate if there exists a string that both are able to accept.
Is this problem…
gefavasej
- 131
- 5
1
vote
1 answer
Show that the greatest common divisor $gcd(x,y)$ is primitive recursive.
Let $x,y \geq 2 $. Actually I have to show that $CD(x,y)$ is primitive recursive, where
$ C(x,y) = 1$ if $gcd(x,y)=1$, otherwise $CD(x,y) = 0$. But I have showed that it is enough to show that $gcd(x,y)$ is primitive recursive.
Which functions are…
RukiaKuchiki
- 1,143
1
vote
1 answer
Prove that function is totally computable
The problem that I'm working on is
Graph of function $f : \mathbb{N}\rightarrow \mathbb{N}$ is set {$(x, f(x))$, $x \in \mathbb{N}$ and $f(x)$ $\neq \perp$} $\subseteq \mathbb{N}^{2}$. Prove that function $f$ is totally computable when $f(x)$ is…
1
vote
1 answer
Proving that sets are recursive
I am stuck on proving that given sets are recursive or recursively enumerable. Those sets are:
$$\begin{align}
f(A) &= \{y, \exists x \in A:f(x) = y\}\\
f^{-1}(A) &= \{x, f(x) \in A\}
\end{align}$$
where $A$ is a recursive set and $f : \mathbb N…
1
vote
1 answer
Prove that EXT,TOT and INF are not recursively enumerable
I am currently working on the reduction method to demonstrate that a set is not recursively enumerable but I am struggling to find suitable functions for the reductions.
In particular I have started working on the proving that the EXT set is not…
1
vote
1 answer
Computability of function of two arguments.
I understand that this question shouldn't be hard but still.
Let $U: \mathbb N \times \mathbb N \rightarrow \mathbb N$ be a function such that for any fixed $c$ function $D_c(y) = U(c, y)$ is computable. Does it imply that $U$ is computable?
I…
Gleb Chili
- 1,133
1
vote
0 answers
Proving non-recursiveness
I ran into trouble with question 6.9 from Logic and Computability by Boole.
Let h(x, y) = 1 if the one-place recursive function with code number x is defined for argument y, and h(x, y) = 0 otherwise. Show that this function is not recursive.
As…
Steven
- 2,296
1
vote
1 answer
Repeated minimization
As I understand, the Ackerman function is not primitive recursive because it needs unbounded number of primitive recursion (to oversimplify things, addition needs one primitive recursion. Multiplication needs two primitive recursion. Exponentiation…
1
vote
1 answer
I need reference proving Turing computable function with oracle of $\chi_A$ is $A$-recursive
Many introductory book for computability theory introduces turing machine with oracle and $A$-recursiveness and often assumed that they are equivalent. I can prove $A$-recursive functions are turing computable with oracle of $\chi_A$ but the other…
fbg
- 861
1
vote
2 answers
question about m-degrees : Is $<_m$ except $\{\mathbb{N} \}$, $\{\emptyset\}$ total order?
I'm recently reading computability theory(nigel cutland p.162.). This book introduces $m$-degree $a,b,c...$ and defines $a<_mb$ and shows this is partial order.$<_m$ is a partial order because of $\bf{0}=\{\emptyset\}$, $\bf{n}$=$\{\mathbb{N}\}$.…
fbg
- 861
1
vote
0 answers
Prove $A$ is creative set
Let $\varphi_i$ be the $i$-th partial function of our enumeration. Consider the set
$$ A = \{ y \in \mathbb{N} \mid \varphi_{\mathrm{fact}(y)}(y) \downarrow \} $$
I have to prove this set to be creative. $A$ is recursively enumerable because its…
incud
- 107
- 1
- 10
1
vote
1 answer
Arity problem while showing factorial is primitive recursive.
So i have been recently introduced to computability and recursion. And we are doing everything very formally. That is why when forming a primitive recursion we need g,h to be computable and then f is when $f(x_1,x_2...x_n,0)=g(x_1,x_2...x_n)$ and…
Sorfosh
- 3,266
1
vote
1 answer
Application of pumping lemma
Thank you in advance if you can help me out with this.
So, i have a grammar that produces strings like [([([(00000)(01101)(011)])(000)])].
Non-empty ( ) can contain [ ] or any number of 0s and 1s.
Non-empty [ ] can only contain ( ).
And i need to…
remit
- 11