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
2
votes
1 answer
bijective projection N <-> algorithms
I thought I'd might be interesting to do some "automated algorithm/turing-automata finding" (I had the busy beaver in mind). I thought about trying many in a specific language (brainfuck or smallfuck) in order to find a programm with an output as…
Fritz
- 121
2
votes
0 answers
Kreisel's proof that for every $\Pi^1_1$ closed set $F$, its perfect kernel $F_p$ is $\Sigma_2^1$
I'm trying to read Kreisel's paper "Analysis of the Cantor-Bendixson Theorem by Means of the Analytic Hierarchy" 1959.
From what is written in the paper, I'm missing something simple. Here is the fragment (in italic) I'm struggling with.
THEOREM…
Dariusz
- 51
- 4
2
votes
0 answers
Many-one equivalence of sets that differ finitely
Consider two sets of natural numbers, $A$ and $B$. Suppose that they differ finitely, i.e., their symmetric difference $(A-B)\cup (B-A)$ is a finite set. Is it true that $A$ and $B$ are many-one equivalent?
According to Odifreddi (Exercise III.2.2.…
ijon
- 85
- 5
2
votes
1 answer
Is there a computable enumeration of a set of all computable functions $\mathbb{N} \to \mathbb{N}\cup\{\infty\}$?
Consider the set $F$ of all functions from natural numbers to natural numbers (possibly with undefined points) which are computable (implementable in python). Does there exist an enumeration of them $F=\{f_i\}_{i\in\mathbb{N}}$ such the function…
Serge Seredenko
- 380
2
votes
1 answer
Example of a non-recursive approximable number
A real number $r$ is recursive approximable if there is a computable sequence of rational numbers converging to it. It is a weaker condition than computability, because we don't have control on the speed of convergence. For example, Chaitin's…
QuinnLesquimau
- 2,053
2
votes
0 answers
Effective countability of a class defined recursively using a finite number of base elements and a finite number of closure operators
I've been working my way through Rebecca Weber's Computability Theory for fun for a while now, but have been stuck on Exercise 3.4.4 for a few days now, and can't seem to get the proof to go all the way through. The problem states:
(i) Show that if…
willard5991
- 21
2
votes
1 answer
Is the integral of computable functions computable?
For each $n$, let $f_n$ be a computable function which takes an infinite binary sequence $\omega\in 2^\mathbb{N}$ as its input. $2^\mathbb{N}$ has the standard measure (for a finite string $x=x_1x_2\ldots x_n$, the set $\Omega_x$ of all $\omega$…
Anton V.
- 603
2
votes
0 answers
Condition for a set not being simple
Suppose that for $A\subset \omega$ there is a partial recursive function $\psi$ such that when the domain of the $e$th p.r. function ($W_e$) does not meet $A$, $\psi(e)\downarrow \notin A\cup W_e$. Apparently this implies that $A$ is not simple, but…
tmp2016
- 21
- 2
2
votes
2 answers
Prove domain of partial computable function exists
Prove that there is an n such that $W_n$ = {$2n, . . . , 2n + n^2$}
Now I don't know where to start with this question, how can I go about answering it? Would I construct a computable function that has that domain? What is that domain? I'm not sure…
straykiwi
- 135
- 1
- 7
2
votes
1 answer
A surjection on the partially computable functions that is not acceptable
This is exercise 1.7.9 from Soare.
Define $$\psi_{\langle p + 1, q \rangle}(0) = p $$
$$\psi_{\langle p, q \rangle}(x) \simeq \phi_q(x) \textrm{ if }x > 0 $$
and let $\psi_{\langle 0, q\rangle}(0)$ be undefined.
I am to prove this is a surjection on…
user388557
- 2,544
2
votes
1 answer
Proving a class of relations is closed under an operation
Given a class of functions $\mathcal{A}$ is closed under substitution and the operation $(\mu y)_{\leq z}$, where
$$
(\mu y)_{\leq z}f(y, \vec x) = \begin{cases} \min\{y : y \leq z \land f(y, \vec x) = 0\}\\
0 …
user66888
- 65
2
votes
1 answer
Something confusing in the proof of existence of simple sets in Soarse's book.
In Soares's book he tries to prove that there's a simple set and I understand it well but there's something confuses me when he proves that the complement of $A$ is infinite he says that $\mathrm{card}(\text{complement of $A$ restricted to $2e$})\ge…
Student
- 109
2
votes
1 answer
If the halting set is Turing-reducible to a c.e. set B, is B m-equivalent to the halting set?
Say you have a c.e set $B$. Then $B$ is $m$-reducible to the halting set $K$. If I know additionally that $K \leq_T B$, can I infer $K \equiv_m B$?
Intuitively, I would say yes, as the Turing degree of $K$ i.e. $0’$ is the largest c.e. Turing degree…
tim6her
- 105
2
votes
1 answer
Prove $B = \{ \varphi_n(n) | n \in \mathsf{K} \}$ to be recursive
The set $B$ is the range of universal function given the domain $\mathsf{K}$, where $\mathsf{K} = \{ n | \varphi_n(n) \textit{ halts} \}$. How can we prove such claim?
MeadowMuffins
- 171
2
votes
2 answers
Examples of Many-one reductions.
I'm trying to wrap my head around many-one reductions for an assignment in Mathematical Logic.
The assignment is to show
$A$ r.e $\Leftrightarrow$ $A\leq_m K$ where $K=\{x\in\mathbb{N}\ |\ x\in W_x\}$
($W_x$ is the domain of the (Turnip-)program…
Hashmush
- 153