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
Understanding of recursive functions
Computability is often defined in terms of recursive functions, recursively enumerable sets, recursive sets. Is the reason behind this – the following:
a function that can be computed is a recursive function – ie. parts of such function can be…
Mooncer
- 165
0
votes
1 answer
If a set $\Sigma$ of alphabets is of cardinality $k$, does $\Sigma^n$ have cardinality of $k^n$?
As title says, if a set $\Sigma$ of alphabets is of cardinality $k$, does $\Sigma^n$ have cardinality of $k^n$? This seems to be the case because for each character of the string of length $n$, you have $k$ choices, so $k^n$. Is this right?
Compan
- 1
0
votes
1 answer
Proving that there exists a function $f: \mathbb{N} \rightarrow \mathbb{N}$ that is not URM-computable.
I'm trying to prove the statement given in the question title, and I'm unsure as to whether my approach is valid. A confirmation of my approach or a correction with a hint pointing me in the right direction would be most appreciated!
My…
Danny
- 1,486
0
votes
1 answer
how can we categorize m-complete languages of RE (recursive enumerable, re-complete)?
is there any hierarchy for many-one complete languages of re (re-complete languages)? how can we propose a categorization for these languages? depending on what measures?
armen
- 1
-1
votes
2 answers
How-to determine whether a given set is recursively enumerable?
I'm stuck with this problem I have to solve.
Set $A = \{ x | \Phi_{x}(x): defined \}$
Set $B$ is produced from set $A$ by taking out all even numbers.
Is set $B$ r.e.?
How does one prove that?
mmierins
- 139
-1
votes
1 answer
How can I create a mapping reduction from a decidable language to the halting problem and also prove it?
I have been tasked to create a mapping reduction from a decidable language to the Halting problem and also prove it. I'm absolutely stumped, any help is appreciated.
-1
votes
1 answer
Is the set {i | Dom(Φi) = ∅} recursive, recursive enumerable or none of them?
Is the set {i | Dom(Φi) = ∅} recursive, recursive enumerable or none of them?
We use Φk to denote the k-th computable function and Dom(Φk) for the set {x | Φk(x) ↓}.
Thank you for your help
Norman
- 45
-1
votes
1 answer
Can we tell whether two programs both halt on some number?
$\Phi_x$ is the $x$-th computable function (TM, Recursive function ...)
$\Phi_x \downarrow$ shows the function with index $x$ which converges
is the below function computable?
$F (x,y) = \begin{cases}
0 \quad \exists m \quad \Phi_x(m) \downarrow…
rosha
- 1
-1
votes
1 answer
Is the following statement true ? If $L$ is a decidable language and $L' \subseteq \; L$, then $L'$ is also decidable ? Prove your answer is correct
Is the following statement true ? If $L$ is a decidable language and $L' \subseteq \; L$, then $L'$ is also decidable ? Prove your answer is correct
I can't figure out this question. Any tips ?
Out Of Bounds
- 1,531
-2
votes
2 answers
Can this version of the halting problem be solved?
I think the halting problem is not a result regarding computability, but rather expressiveness or restrictiveness. It's like asking a computer to prove $0=1$ or color a planar graph using only $3$ colors. To accommodate this lack of expressiveness,…
Zirui Wang
- 1,417
-2
votes
1 answer
Can we tell if a program always returns 2 when it halts?
Is the following computable ?
Notation: We use $Φ_k$ to denote the k-th computable function
$$g(x) = \begin{cases}
1 & ∀z (Φ_x(z) = 2 ∨ Φ_x(z) ↑) \\
↑\ &otherwise
\end{cases}
$$
I really need your help.
Thanks
Norman
- 45
-2
votes
2 answers
Proove that Unions and intersections of recursively enumerable sets are also recursively enumerable
How do I prove that Unions and intersections of recursively enumerable sets
are also recursively enumerable?
Elsban
- 113
-5
votes
1 answer
Silly question: Computing with computable numbers...
Of course the point to this question, to the extent there is such a thing, is the answer below. Was about to post that as a "question"; instead, to make this a legal Q&A thing:
Question. Can one concoct a "computable" data type allowing "exact"…
David C. Ullrich
- 89,985