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
Primitive recursive functions and mutual recursion
Let $g$ and $g'$ be primitive recursive, of arity 2, and let $a,a'\in\mathbb{N}$. Define $f$ and $f'$ by the following formulae:
$f(0)=a$
$f'(0)=a'$
$f(n+1)=g(n,f'(n))$
$f'(n+1)=g'(n,f(n))$.
How would you show these ($f$ and $f'$) are primitive…
FPP
- 2,103
1
vote
0 answers
Non-computable infinite subsets
Is there a computably enumerable set $A$ such that every infinite subset of $A$
is noncomputable?
I think that it's a set $K = \{n\ \ |\ \ U(n,n) \text{ is defined}\}$ (which is noncomputable, $U(n,x)$ is universal computable function).
But I…
L. Antz
- 11
1
vote
1 answer
decidable intersect undecidable
Hello I'm kind of having trouble with computability, so my question is
I need to define af language A and B such that A is decidable and B is undecidable
when I do $A\cap B $ is decidable.
also oppositely i need to define a language A which is…
qazobi
- 11
1
vote
1 answer
Is image of recursive set under recursive function recursive?
Given $A$ - recursive set and function $f$ which is also recursive. Is $f(A)$ recursive?
I think that it isn't recursive, but how to prove it?
John Malick
- 123
1
vote
0 answers
Decidability of the set of axioms of Algebraically Closed Fields
The set of axioms of $ACF_p$ is infinite. Why is it decidable? Is there a way to decide given a number whether it is a code of some axiom of $ACF_p$
user280486
1
vote
0 answers
Using Church's thesis to show a certain simple function is computable.
I am not quite sure how to apply Church's thesis to the following problem to do with register machines:
The function $E(e)$ is defined so that on input of a godel number $e$, the function returns the Gödel number of a program that performs: "First…
Tim Hodgkin
- 127
1
vote
2 answers
Can we make witnesses for membership of $\Sigma_2$ sets unique?
A $\Sigma_2$ set $A$ is one for which there is a computable relation $R(x, s, t)$ s.t. $x \in A \iff \exists s \forall t \colon R(x, s, t)$.
Can we use $R$ to produce another computable relation $Q$ determining membership of $A$ in the same fashion,…
G. H. Faust
- 1,766
1
vote
1 answer
Does any non-admissible numbering form a PCA?
Given a numbering $\varphi_0, \varphi_1, \dotsc$ of the unary partial recursive functions, define a PAS as $\mathbb N$ with application $x \cdot y \simeq \varphi_x(y)$. If the numbering is admissible then this PAS is a PCA.
Is there any…
Anders Lundstedt
- 152
1
vote
1 answer
Let $G(x,y)=2^x(2y+1)-1$ and show that $G$ is computable
Show that $G$ is a computable bijection and that the functions $G(G_1(z))$,$G_2(z))=z$ for all $z$ is computable. To show that it is computable, do we show that the above function $G$ is primitive recursive? I don't understand the second equation…
user270452
- 67
1
vote
2 answers
Finding a total function not in a computable sequence of functions
Suppose $f(x,y)$ is a total computable function. For each $m$, let $g_m$ be the computable function given by $g_m(y) = f(m,y)$.
Construct a total computable function h such that for each $m$, $h \not= g_m$.
My work:
Is this a really simple question…
John Lee
- 13
1
vote
1 answer
strongly hh-immune sets
I'm trying to do exercise X.2.16 from Soare's Recursively Enumerable Sets and Degrees, but I have no idea how ro solve it. Any hints would be appreciated.
An infinite set is strongly hh-immune or ssh-immune if there is no uniformly r.e. sequence $\{…
Leo163
- 2,647
1
vote
1 answer
Example for 2 disjoint languages that cannot be separated by a decidable language
Question:
Let A, B be languages such that A ∩ B = ∅.
Say that a language C separates A and B if: A ⊆ C and B ⊆ $C^c$.
Describe two languages A, B ∈ RE, that cannot be separated by any C, such
that C ∈ R.
R is the class of decidable languages and RE…
jreing
- 3,297
0
votes
1 answer
infinitely long input for a turing machine
I have a question about Turing machines. Is it allowed to give them infinitely long input? Can I give a Turing machine for example all of natural numbers as input?
Adam
- 3,422
- 1
- 33
- 50
0
votes
1 answer
TOTAL is not Recursively Enumerable
$\overline{HALT}=$ { (M, w) : M does not halt on w }
$TOTAL=$ { M : M halts on every input }
The following is the proof from Hopcoft that TOTAL is not R.E.
Let R(x) be the following machine:
1) Simulate M on w for n steps
2) IF M halts after n…
user137481
- 2,605
0
votes
3 answers
Recursive Set in Partial Computable Function Problem
Suppose $A, B, C$ are disjoint set such as shown on this figure. $f_1(x), f_2(x), f_3(x)$ is partially computable function.
why $A,B,C$ is recursive set?
user153695
- 217