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
Proving Decidable Language
Let $E$ be a Turing machine outputting a list of codes of Turing machines $\{\left \langle M_1 \right \rangle, \left \langle M_2 \right \rangle, ...\}$ where every $M_i$ is deciding some language $L_i$.
How do I prove that there is a decidable…
Graham
- 1
0
votes
1 answer
What's the $e^{th}$ partial recursive function?
What's the $e^{th}$ partial recursive function?
It refers here to the $e^{th}$ partial recursive function. Since no reference is provided, the reasonable implication seems to be that there's a canonical ordered set of such functions.
it's a hire car baby
- 9,243
0
votes
1 answer
Is $f(A) \in \Delta_n$ if $A \in \Delta_n$ when $f$ is computable?
It's not hard to see that at least $f(A) \in \Sigma_n$, but is $f(A) \in \Pi_n$ true in general?
Jori
- 1,698
0
votes
1 answer
Complement of the halting set one to one reducible to $\{y | \phi_y = \phi_x\}$ for fixed $x$.
Let $x \in \mathbb{N}$ be fixed. Let $K$ be the set $\{y | \phi_y(y) \downarrow\}$. I need to prove that $K^c \leq_1 \{y | \phi_y = \phi_x\}$. If I understand correctly, we need to find an injection $f$ such that $\phi_{f(x)} = \phi_x$ if and only…
user388557
- 2,544
0
votes
1 answer
What makes computable, decidable sets recursive?
What does recursive mean in this case and how does recursion apply?
csp2018
- 401
0
votes
1 answer
recursively enumerable of Godel numbering
There are statements for natural number x, like followings
m: "x is even natural number"
n: "x+1 is odd number and x>1"
l: "x is positive integer multiple of two"
m, n, l has same boolean value for x. If m(x) is true, n(x), l(x) is also true. m(x)…
martian03
- 75
0
votes
0 answers
is there a definition of Turing computability for multivariate functions?
Suppose we have a function $f:\omega^{n}\rightarrow\omega^{m}$ with $n,m\in\omega$ with $n,m\geq 1$ for which there exists a Turing machine that on input $(k_{1},...,k_{n})$ produces $f(k_{1},...,k_{n})$ as output.
My question is: Is there any…
0
votes
1 answer
recursive maps and decimal representation
I'm trying to think of an example of a real number $R$ such that the map $n \mapsto R[n]$, where $R[n]$ is the $n$th digit of the decimal representation of $R$, is not recursive.
So I was thinking to take an irrational number such as $\pi$, or $e$.…
Buddy Holly
- 1,189
0
votes
0 answers
Confused about non-computable real numbers and countability. Is Cantor diagonalization a computation?
Suppose I start with the set of computable real numbers between 0 and 1. Now these are countable.
So I follow Cantor's diagonalization argument to construct a real number B between 0 and 1 outside this set.
I enumerate the countable real numbers…
Ameet Sharma
- 2,957
0
votes
1 answer
Is the set {i | $\phi_i$ is total } recursively enumerable?
Is the set {i | $\phi_i$ is total } recursively enumerable?
and can you please tell me why ?
Bests
Norman
Norman
- 45
0
votes
0 answers
is SAT as set of satisfiable formulas in FOL recursive or recursive enumerable ?
Can somebody help to understand whether SAT as the set of satisfiable formulas of first-order classical logic. Is SAT recursive, r.e. or none of them?
Thank you so much
Norman
- 45
0
votes
0 answers
Prove the inverse of a 1-1 1-place partial recursive function is partial recursive.
I'm working through exercises in recursion theory and one such exercise is to prove the inverse of a 1-1 1-place partial recursive function $\psi$ is partial recursive, which was given with somewhat of a warning as to its difficulty. I've figured…
Physical Mathematics
- 4,453
0
votes
1 answer
Determine type of set
Given complement to set $M$ is recursively enumerable and recursive set $R$. What will be the type of the subset of M, elements of which are in R ?
I think they will be also recursively enumerable, but I'm not quite sure about it.
Kevin
- 35
0
votes
0 answers
If $f(x)$ is defined nowhere, and $z(x)$ is zero everywhere, then what is $f(x)z(x)$?
Let $f(x)=\mu y(id^2_1(x+1,y)=0)$ and $g(x)=f(x)z(x)$ where $id^2_1(x,y)=x$ and $z(x)=0$. Then $f(x)$ is defined nowhere and $z(x)=0$ everywhere. Then what is the value of $g$? Is it undefined or just zero?
fbg
- 861
0
votes
1 answer
On Cardinalities of $\mathcal{RE}$ and $\mathcal{P}(\mathbb{N})$
We denote $\mathcal{RE}$ as the universe set of recursively enumerable sets. A set is recursively enumerable iff its semi-charactersitic function is computable (one can write its semi-verifier). The question is, can we build a bijection between…
MeadowMuffins
- 171