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
Are all infinite sets of indices of computable functions extensional?
Let $I$ be any set of indices of computable functions. Let $\Phi_i$ denote the $i-th$ computable function. A set of indices of computable functions is extensional if for all $i, j$:
$$\text{if } i \in I \wedge \Phi_i \backsimeq \Phi_j \text{ then }…
user3285532
- 15
1
vote
1 answer
How to prove that the set INF is not recursively enumerable
I've been given the set $INF=\{e\in\mathbb{N}:dom(\varphi_e)$ is infinite$\}$, where $\varphi_e$ denotes the $e$-th computable function.
I'm trying to prove that it is not recursively enumerable. I tried to follow the same strategy as with the…
Javi
- 6,263
1
vote
1 answer
Show that K and complement to K are "1-reducible" to EQ={⟨x,y⟩|φx≃φy}
Where $K = \{x | φ_x(x) \downarrow\}$, $φ_x$ is a $\mu$-recursive function computing $M_x$, $M_x$ is Turing machine with Godel's number $x$. Set $A$ is "1-reducible" to set $B$ ($A \leq_1 B$) when there exists invertible function $f = (\forall x…
Ondra
- 115
1
vote
0 answers
Showing that a function is primitive recursive
I am given three primitive recursive functions $f$,$g$ and $r$ and I am asked to show that the following functions are primitive recursive:
\begin{equation}
h(x) =
\begin{cases}
f(x) & \text{ if r(x) = 0} \\
g(x) & \text{if r(x)} \neq…
McNuggets666
- 1,583
1
vote
2 answers
The symmetric difference of two recursive (recursively enumerable) sets is recursive (recursively enumerable)
I want to prove it, but don't know how... (I've tried to resolve complement by defining characteristic function like this: $\chi_{\bar A} = 1 - \chi_A$) Any ideas please? :-)
kolage
- 133
1
vote
0 answers
Locate languages in the arithmetic hierarchy
I'm finding it difficult to locate the languages $L_1$ and $L_2$ in the arithmetic hierarchy. If anyone could explain which class they're in an why that would be great. Thanks in advance.
$L_1$ = {$$ : exist u s.t. $|u| > |v|$, accepted by the…
user3303941
- 51
1
vote
1 answer
Can human reasoning determine whether a program halts?
In this essay, Scott Aaronson describes Tibor Rado's "Busy Beaver" sequence, as follows.
... we can classify Turing machines by how many rules they have in the
tape head. ... for each fixed whole number N, ... there only finitely
many distinct…
Matthew
- 227
1
vote
1 answer
What does "Closed under finite differences" mean precisely?
I have some idea what would it mean, but I would like to have a precise definition. I've seen this term used here and there in computability theory, but I couldn't find a definition.
(My idea is that if a set A is in class C and there is B such that…
Zygro
- 115
1
vote
1 answer
Shewing that a problem reduces to the halting problem
Let $\phi_e$ be an enumeration of the partial recursive functions.
A total function $f : \omega \to \omega$ is large if $f(e) > \phi_e(0)$ whenever $\phi_e(0)$ is defined.
If $f$ is large then given an oracle for $f$ it is possible to solve the…
Dean Menezes
- 673
1
vote
1 answer
Prove that $A≤_m A\cap B$ [Cutland 9-1.7-5]
Suppose that $A$, $B$ are r.e. sets such that $A\cup B= \mathbb N$ and $A\cap B≠∅$ . Prove that $A≤_m A\cap B$.
The difficulty is that how to find a total computable function f such that for all x, $x\in A$ iff $f(x)\in A\cap B$.
Marvin
- 151
1
vote
0 answers
Computable Hilbert space
If $(H_{i},\|.\|,(e_{ij})_{j})$ be the computable Hilbert spaces for each $i \in \mathbb{N}$, what condition can be imposed on $H_{i}$'s so that the map $(i,j)\mapsto e_{ij}$ is $((\delta_{\mathbb{N}},\delta_{\mathbb{N}}),\delta_{H_{i}})$…
Poonam
- 11
1
vote
1 answer
Oracle machines that halt on every input
Suppose $x, y \subset \mathbb{N}$ and $x \leq_T y$; that is, there is some oracle machine $e$ such that $n \mapsto \{e\}^y(n)$ is the characteristic function of $x$. (In particular $n \mapsto \{e\}^y(n)$ is total.) Is it always possible to choose…
Danielle Ulrich
- 223
1
vote
1 answer
Unsolvability Degree in Turing's Proof 1
I have read that there is some debate over the exact origin of the Halting argument, which begins with Kleene and Davis in the 1950s [Copeland 2004]. Motivated by this I want to clarify the Degree of the problem actually proved unsolvable by Turing…
Roy Simpson
- 524
1
vote
1 answer
Finding a suitable function to use Kleene's recursion theorem
Problem. Suppose $g(x)$ is a partial recursive function such that for all $e$,
$$W_e = \varnothing \Longrightarrow g(e)\!\downarrow .$$
Prove that there is some $m$ such that
$$W_m = \{m\} \text{ and } g(m)\!\downarrow.$$
What I've tried so…
Random Jack
- 2,906
1
vote
2 answers
Show that function is recursive
Recursive functions: $\mathbb{N}_0^k \to \mathbb{N}_0$
Class of recursive functions:
The minimal subclass of the class of all the functions $f:
\mathbb{N}_0^k \to \mathbb{N}, k=1,2, \dots$ that contains the
$f(x)=c$ (constants)
$S(x)=x+1$…
Evinda
- 1,460