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
"P halts on n" as an elementary math statement
As a proof of "There is no computable enumerable list of axioms that prove all and only the true statements of elementary mathematics", just run the theorem-enumeration machine with inputs p and n (p a turing-machine program and n its input) and…
Eduard
- 304
1
vote
0 answers
Why exactly is the diagonal function on p.r. functions not itself p.r.?
1
The argument on this page strikes me as sound: however, after reading it, I found myself with the following question:
If the process of computing $F_n(k)$ is not p.r., then there must be some way in which the process uses unbounded minimization.…
nontology
- 19
1
vote
1 answer
How to prove that a given set is recursively enumerable?
I was given a set
$$
A = \{x \mid W_x \, \text{contains at least one prime number}\}
$$
where $W_x = \{y\mid \phi_x(y) \downarrow \}$ is the Dom of the function $\phi_x$
$\downarrow$ means that the function converges or halts.
Any hints on what to…
Dknot
- 515
1
vote
0 answers
How to prove quotient function and remainder function is representable in Robinson's Q?
I think such proof is quite standard however I can't make them as the case of addition and multiplication functions. (which can be done by first prove $\mathsf{Q}\vdash x+/*y=z$ then show such $x +/*y = z$ represents addition/multiplication in…
qwerty
- 305
- 1
- 7
1
vote
0 answers
How to prof that $L_1$ is not in $RE$ using $RICE-theorem$
I was given a question to prof that a language is not in $RE$ using $RICE-theorem$
The question:
$S$ - property of turning machine language
$L$ - language
$S \subseteq \{L : 7 \leq |L| \leq 10 \}$ is not an empty set.
prof that: The language $L_1 =…
JamseGoldman
- 21
1
vote
1 answer
Recursive function with code $n$, whose output is the number $n$ itself
There is a recursive function with code $n$, whose output is the
number $n$ itself. That is $\phi_n$ is the constant function with value
$n$.
I've been toying with the idea of using s-m-n theorem applied to a particular function and then…
Gigili
- 5,503
- 8
- 41
- 62
1
vote
2 answers
difference of 2 partial computable algorithms
I have 2 algorithms
Algorithm 1:
if( Condition1(input)==true )
print(input);
else
loop forever;
Algorithm 2:
if( Condition2(input)==true )
print(input);
else
loop forever;
for any arbitrary fully-computable condition 1 and 2.
We know…
a d
- 274
1
vote
1 answer
Primitive Recursion -- Definition by Cases
I would like to know if it is allowed to define bounded maximization by primitive recursion and definition by cases in the following way:
\begin{align*}
[\mathrm{max}\,R](x, 0) &= 0,\\
[\mathrm{max}\,R](x, y + 1) &= \left\{\begin{array}{l l}
y +…
gerald
- 53
1
vote
1 answer
Numbering the Grzegorczyk Hierarchy.
I would like to know if there is a (known and maybe published) way to numbering, in a Gödel style, the functions belonging to every class in the Grzegorczyk Hierarchy and how could it be done.
gibarian
- 145
1
vote
1 answer
Is this given set recursive, r.e. or none of them? Informal argument ok?
I am working on an exercise for my computability course.
The question is stated as:
Is the following set
$\{x|\text{ whenever } y
BassSultan
- 113
- 3
1
vote
1 answer
Extending a 1-reduction
Suppose $g: A \leq_1 B$, that $B$ is computably enumerable and that $A$ is infinite. I want to prove there is a $f: A \leq_1 B$ such that $f(A) = B$.
Suppose $B = W_e$, then $A$ is the domain of the p.c. function $\phi_e \circ g$, so $A$ is c.e.…
user388557
- 2,544
1
vote
0 answers
Numbering of prime enumerating functions
I have a trouble solving this problem. Let's define $I$ as a set of those $i \in N$ such that $\varphi_i$ is an injective total recursive function and its range consists of all primes. Are $I$ and its complement $I^C$ recursively enumerable? Thank…
tripleM
- 11
1
vote
1 answer
Example of decidable subset of $ \mathbb{N} $, so that set of prime factors of elements is undecidable
Let $ X $ be a decidable subset of $ \mathbb{N} $ and let $ Y = \{p\,|\,\text{p is prime and }\exists x \in X : p|x\} $.
I know that $ Y $ is recursively enumerable so I have to use universal function and related theorems about recursively…
ngtvx
- 63
1
vote
1 answer
Significance of the Halting problem on non-finite inputs
The Halting problem is decidable on machines with finite memory. One can enumerate all the states and continually check for a repeated state, albeit being inefficient. (https://en.wikipedia.org/wiki/Halting_problem#Common_pitfalls)
What I struggle…
user1318416
- 113
1
vote
0 answers
A general view on degree structures
The Turing degrees $D$ is defined to study those properties of the subsets of the natural numbers $\mathbb{N}$ which can be expressed in terms of relative computability. Formally, suppose $A$ and $B$ are subsets of $\mathbb{N}$, we say $A$ is…
Maryam Ajorlou
- 449