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
2 answers
Let A, B be infinite recursive sets with infinite complements. Show that A≡B.
My question is from Hartley Rogers' textbook (1967).
Here's how I'm thinking about this so far. I know given infinite recursive sets A, B with infinite complements by theorem II of the current chapter (5) that both A & ~A (complement of A) and B &…
لويس العرب
- 690
1
vote
1 answer
Is the proof of the uncomputability of the following function correct?
Let the following function be given:
$f(x) = \begin{cases} 1 & \mbox{if } \forall n \Phi_x(n+1) \uparrow \mbox{ or } \Phi_x(n+2) \uparrow \\
\uparrow & \mbox{otherwise}
\end{cases}$
Define an auxiliary function $h$ as follows:
$h(x,y) =…
trojan
- 79
1
vote
1 answer
two Creative and Productive sets
I am studying CUTLAND "Computability-An introduction to recursive function theory" book.
In this book two sets are introduced:
$$
Z = \{x| \phi_x(x)=0\}
$$
$$
R=\{x|\phi_x=0\}
$$
the set $ \ Z $ is a creative set and the set $ \ R $ is a…
1
vote
1 answer
A non-r.e. language whose complement is not r.e.
What's an example of a language that is not recursively enumerable and whose complement is also not recursively enumerable?
MJD
- 65,394
- 39
- 298
- 580
1
vote
2 answers
Enumerable and not enumerable sets
I am i bit stuck on this problem. Is it possible that sets A and B are not enumerable, but set $$A \cdot B =\{x \cdot y \mid x \in A, y \in B\}$$ is enumerable? Defenition of emumerable set so, set is enumerable if there is an algorithm, that may…
ratkke
- 111
1
vote
1 answer
Infinite regular sets
Would it be true that for all infinite regular subsets, each one contains subsets that are not c.e/r.e (countably enumerable/recursively enumerable)?
Intuitively this seems true because of sets that are uncountable.
Heplar
- 41
1
vote
1 answer
Computability and the Halting Problem
This is a branch of another problem that I had asked earlier (and was answered). Found here
Let the "merge" of two languages L1,L2⊂{0,1}* be:
L1⊥L2 = {x0 | x∈L1}∪{y1|y∈L2}
Given the diagonal halting problem H, and its complement H', is H$\bot$H' c.e…
Heplar
- 41
1
vote
0 answers
Showing the weakness of the least modulus on a delta 2 approximation
I am working through Turing computability by Soare, and have been stumped on an exercise asking you to show the weakness of the least function for a $\Delta_2$-approximation.
Let $A$ be a set, and $\{A_s\}_{s \in \omega}$ be the corresponding…
Konrad Wozniak
- 11
- 2
1
vote
1 answer
Why do we have a constant function as part of primitive recursive functions?
Currently taking a class on computability theory and started learning about primitive recursive functions. The constant function described as follows:
$C^n_a(x_1,...,x_n) = a$
First of all, why do we have a function of this sort to begin with?…
Clever7-
- 21
- 4
1
vote
1 answer
Example of a primitive recursive function whose range is properly general recursive
I know that not every recursive function from $\mathbb{N}$ to $\mathbb{N}$ has a range which is a recursive set. I wonder, is there a primitive recursive function $f$ such that the range of $f$ is a general recursive set, but not a primitive…
user107952
- 20,508
1
vote
1 answer
Certain language feature and its relation to Recursion Theorem
I am trying to get a better sense of what recursion theorem entails (or doesn't entail). I understand the basic statement of the theorem (or at least I would think I do) but I have difficulty seeing its applications. And it doesn't seem to me that…
SSequence
- 1,022
1
vote
1 answer
Why doesn't Cohen's definition for the $\mu$ operator result in non-computable functions?
I am reading Paul Cohen's Set Theory and the Continuum Hypothesis. Cohen defines the $\mu$ operator as{}^1
$\mu_y f(y,x_1,...,x_n) \equiv g$
where
i) $g(x_1,...,x_n) \equiv 0 \text{ if for any } \overline{x}_1,...\overline{x}_n \forall y…
panofsteel
- 703
1
vote
1 answer
Partially correct algorithm for a decidable problem
$D$ is decision problem whose inputs are the natural numbers.
Suppose $A$ is an algorithm to solve $D$ in which we know that it is:
partially correct for all inputs
halts on all inputs >= 1000.
Can I deduce that $D$ is decidable?
On the one hand,…
chrisg
- 13
1
vote
0 answers
Can the semi-characteristic function of $\{x \mid \varphi_x(x)\downarrow\}$ be extended to a total function?
The semi-characteristic function of $K = \{x \mid \varphi_x(x)\downarrow\}$, that is the set of all indices $x$ such that the $x$-th computable function converges on the input $x$, is the following:
$$ \chi'_K(x) = \begin{cases} 1 & x \in K \\…
mell_o_tron
- 528
1
vote
1 answer
Example of a partial computable function that cannot be extended to a total computable function
Today in my Computability Theory class the professor introduced the following non-recursive class: $$EXT = \{x : \varphi_x \text{ can be extended to a total computable function}\}$$
(Where by $\varphi_i$ I indicate the $i$-th computable function)
He…
mell_o_tron
- 528