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
3
votes
0 answers
Computability of determining whether an expression equals zero
Suppose we are given an expression composed of integers,$ +, *, -, /,$ elementary functions $(exp, sin, cos, tan)$ and their inverses (and for simplicity, assume each argument to these functions is in the range where it is defined and real valued,…
stewbasic
- 6,131
3
votes
1 answer
Is there an incomplete Turing degree that is not r.e.?
$\exists A \in \mathcal{P}(\mathbb{N}). (A \lt_T 0' \land \neg \exists B \in \Sigma_1. A \equiv_T B)$?
In words: does there exist a subset of natural numbers that is Turing reducible to the halting set but is not Turing equivalent to any computably…
Dávid Natingga
- 2,889
- 2
- 27
- 41
3
votes
1 answer
Prove a set is not recursive / recursively enumerable
I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$?
$B-A$ is obviously recursively enumerable (to generate its elements, I can…
user137041
2
votes
2 answers
Definition of a computable (or recursive) set
I am new to computability theory, but I understand the usual definition of a "computable set" S when S is a subset of the natural numbers. Is there a notion of "computable set" that doesn't involve just subsets of the real numbers? In particular,…
dan
- 21
2
votes
0 answers
Decidability of a language
Let $C$ be a conjecture about natural numbers.
Let $$S = \{n\in N: n > m \text{ where $m$ is the first number found for which $C$ is false} \} $$
Is $S$ decidable?
If $C$ is true for all natural numbers then S is an empty language which is…
user137481
- 2,605
2
votes
0 answers
Computable models of ($\omega$, <) without computable isomorphism
I read somewhere that "it is easy" to construct a computable presentation for the model ($\omega$, <) so that any computable isomorphism between this construction and the usual presentation of $\mathbb{N}$ (with the usual order) would compute the…
user161363
- 21
2
votes
1 answer
Functions with and without distinction of cases
Consider computable functions $f: \mathbb{N} \rightarrow \mathbb{N}$, given as formulas. I assume that it is clear for at least some of them whether they contain a distinction of cases:
$$f(n) = n$$
obviously does not contain a distinction of cases…
Hans-Peter Stricker
- 18,159
2
votes
1 answer
Computability: why any m-degree a is denumerable?
The problem printed in Cutland 9-2.9-6 is wrong, it should be countable, not denumerable
m-degree is an equivalence class of the relation $\equiv_m$(many-one equivalent).
Question:
Why any m-degree a is denumerable?
My thoughts:
Denote m-degree of…
Eric Xu
- 179
2
votes
1 answer
Problem from Cutland's Computability
Is it true that if $$ A \equiv_m \bar{A} $$ then A is recursive?
I think it is true but I can't prove it.
Appreciate your help!
Eric Xu
- 179
2
votes
0 answers
Clarification of the argument for the set of total recursive functions not being recursively enumerable?
I read that the set of partial recursive functions is recursively enumerable while the set of total recursive functions is not. Isn't the set of total recursive functions a proper subset of the set of partial recursive functions?
The argument for…
user135963
2
votes
1 answer
Decidability of a set
A pair of twin primes is defined as (p, p+2) where both p and p + 2 are prime.
Given $S = \{i\in Z^+ | i\, is\, one\, of\, a\, pair\, of\, twin\, primes\}$
Is S decidable?
My understanding is that S(language) is decidable if there exists some method…
EggHead
- 667
2
votes
1 answer
if I find a bijection, rather than it is computable or not even computable, then the set would be denumerable or not?
In "Computability: an introduction to recursive function theory", by Cutland, there is a theorem as follows:
Theorem 2.4 $\mathcal{C}_n$ is denumerable.
where $\mathcal{C}_n$ represents the set of all $n$-ary computable functions. It constructs a…
Ali Shakiba
- 583
- 7
- 18
2
votes
1 answer
Looking for Wald Theorem
From the paper "What is a Random Sequence?" by Sergio B. Volchan, Math. Monthly 109, january 2002
Definition 3.1 An infinite binary sequence $x=x_1 x_2 \dots$ is random if it is collective; i.e., if it has the following two properties:
I. Let $f_n…
Immanuel Weihnachten
- 1,876
2
votes
2 answers
Construction of a universal prefix-free Turing machine
How can one construct a universal prefix-free Turing machine (TM)? By a universal prefix-free TM, I mean a prefix-free TM $U$ (that is, a TM whose domain is prefix-free) such that for every prefix-free partial recursive function $f$, there feasibly…
Pteromys
- 7,220
2
votes
1 answer
A computable universal function for any countable set of computable functions exists.
Assume $\{f_i:\mathbb N^k\to\mathbb N\}^\infty$ is a countable set of computable functions. Prove that a computable universal function exists for this class.
This more general question stems from the special case of the polynomials. I have reduced…
superAnnoyingUser
- 4,379