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
0
votes
1 answer
Uncomputability of $a
Is it possible to prove the existence of two real numbers $a, b$ that have the property that it is uncomputable whether or not $a
Jostein Trondal
- 378
0
votes
1 answer
Program with no intermediary states
Every program P which built of function sequence (order counts): $F_1,..,F_n$, where $F_i$ returns $R_i$ and $F_{i+1}$ takes $R_i$ as an argument, can be shown as $F_1(F_2(F_3(...(F_n))))$, i.e. we do not need to store intermediary program states.…
tesgoe
- 131
- 8
0
votes
1 answer
Using diagonal argument to prove that H(x)=μyT(x,x,y) has no total computable extension
Hello everyone just like the title says I want to prove that $H(x) = \mu y T(x,x,y)$ has no total computable extension such that if we had a function $BIG(x)$ that is both total and agrees with $H(x)$ whenever $H(x)$ is defined, then $BIG(x)$ is not…
InsigMath
- 2,073
- 2
- 18
- 27
0
votes
1 answer
Prove that there exists an index for a specific computable function
How can I prove that there exists an index $x$ s.t. the $x$-th computable function(0) $= x^2$
Thank you
herbert
- 33
0
votes
1 answer
A universal function exists for the polynomials
Problem: Consider polynomials with natural coefficients of $n$ natural variables. Prove a computable universal function exists for this class. Prove that any such function is not a polynomial.
Attempt: Consider an ordering of the monomials. The…
superAnnoyingUser
- 4,379
0
votes
1 answer
The representation of the step function is primitive recusrsive
I've been trying to construct a proof that Unlimited Register Machine (URM) computable functions are partial recursive, which follows from the universal function theorem. I could not prove that the representation of the step function is primitive…
superAnnoyingUser
- 4,379
0
votes
1 answer
Mapping natural numbers to rationals
I'm prepping for an exam, and I came across this:
$$x_K = \sum_{n\in K} 2^{-n}$$
(K is the Halting problem)
Does there exist a computable function $f_x$ : N$\mapsto$Q where these conditions are satisfied?
(i) For all m$\in$N, 0$\leqq$f(t)
(ii)…
Heplar
- 41
0
votes
1 answer
Basic reductions
I'm trying to learn about reductions and I came across this example in my book:
Let the "merge" of two languages L1,L2$\subset${0,1}* be:
L1$\bot$L2 = {x0 | x$\in$L1}$\cup${y1|y$\in$L2}
I think that either original language is many-one reducible to…
Heplar
- 41
0
votes
1 answer
Suppose $f(x)$ is a total computable function. Use minimlization to show that there is a computable function $g(y)$
Suppose $f(x)$ is a total computable function. Use minimalization to show that there is a computable function $g(y)$ with $dom$ $g = im$ $f$ and $f(g(y))=y$ for all $y \in dom$ $g$
I know this then means that $f(g(y))=y$ for all $y \in im$ $f$ but I…
Jim
- 1
0
votes
1 answer
Futamura Projections- Compatibility - Interpreter and Compiler
I've just learnt a week ago in my compatibility class about fotomora. These are three rules/tricks you can do with interpreter and compiler.
I'm looking for a bit more information about the subject and I can't find anything in google.
Do anyone…
SyndicatorBBB
- 967
0
votes
0 answers
What does it mean for a set to be a member of $\aleph$?
I've seen the following two definitions in my slides:
$S \subseteq \aleph$ is semi-decidable iff there exists a partially computable function g where
$S = \{x \in \aleph\ |\ g(x)\downarrow \}$
$S \subseteq \aleph$ is re iff $S = \phi$ or there…
Clever7-
- 21
- 4
0
votes
1 answer
solvable and enumerable sets
Are the following sets solvable (respectively,enumerable)?
a) The set {$xy$ | $x ∈ A$, $y ∈ B$}, where $A$ and $B$ are solvable (enumerable).
b) The set $A ⊆ B$, where $B$ is solvable (enumerable).
As for $a$, I want to say that if $A$ and $B$…
Quark
- 85
0
votes
1 answer
Difference definable vs. computable
Is it true that a computable number or function is always definable, while the other way around is not?
It seems so based on the following link: just want to…
Mike
- 33
0
votes
0 answers
Proving the Computability of the Function $\beta$ Analogous to Another Function
I am studying a Theory of Computability.
Before the theorem I should provide you with the definition of limited sum and product, respectfully:
$\alpha(x,y)=\sum_{z
sonj4
- 43
0
votes
0 answers
Proof that the computing time function of a total TM is primitive recursive.
This is exercise 4.8.6 from Hils and Loeser's A First Journey through Logic: Prove that for every Turing machine $\mathcal M$ which computes a total function, the graph of the computing time function $T_{\mathcal M}$ is primitive recursive.
Earlier…
Addem
- 5,656