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
4
votes
1 answer
Non-computable Number Example
The following is a quote from Denis' answer in another thread where the context centers on creating a noncomputable real number. It's old and I'm new here so I can't comment on the answer itself, thus I'm asking the question here (note, you…
AplanisTophet
- 413
- 2
- 12
4
votes
3 answers
Recursively enumerable set? Any hints?
I don't mean to be pulling answers out of you, but I'm stuck. Any advice on the right direction would be appreciated.
I have the following set
$X$ ={$n$ where $n$ is a number of a turing machine $M$ that does not halt when given $n$ as input}
My gut…
pauliwago
- 635
4
votes
1 answer
Weak and strong computability of real numbers
Let me adopt the following definitions:
A real number $x$ is weakly computable if it satisfies one of equivalent definitions given here.
A real number $x$ is strongly computable if the binary expansion of $x$ is a computable string (we don't need…
Wojowu
- 26,600
4
votes
3 answers
Are there problems that can't be expressed as languages?
OK, so I was told in CSTheory that I should be asking here. So my question is the following:
I've taken my first course on Language Theory and we saw the "standard" classification of languages. We saw that many problems can be expressed as a…
ivotron
- 143
4
votes
1 answer
(Semi-)Decidability of Turing-completeness of cellular automata
This is a follow-up to the question Undecidability in Conway’s Game of Life I posted at mathoverflow.
For some cellular automata it can be proven that they can simulate a Turing machine, normally by explicit construction. For some of them it can be…
Hans-Peter Stricker
- 18,159
3
votes
1 answer
Binary representation of real numbers without dots
How can I represent a real number using only 0's and 1's? I do not want to use any extra symbol like '.' to separate the integer part and the mantissa.
MatteoBianchetti
- 436
- 3
- 10
3
votes
1 answer
Bijection between computable reals and rationals?
This wikipedia article
http://en.m.wikipedia.org/wiki/Computable_number#Properties
suggests that there is such a bijection. How does it look like? And how to map computable transcedentals like pi to a rational?
cristian
- 39
3
votes
1 answer
Proof that $\{ e \ | \ \forall p$ prime$: \varphi_e (p) \downarrow \}$ is not $\Delta_2$
This is a problem I've come across in my exam studies, and neither me nor my friend in the same course have been able to solve, so it would be good to see how it's done before the exam in a couple of days.
If we let $D = \{ e \ | \ \forall p$…
G. H. Faust
- 1,766
3
votes
1 answer
Are computable functions closed under "less than"?
Suppose f and g are functions from N to N, f is computable, and f>=g. Is g also computable?
user107952
- 20,508
3
votes
3 answers
noncomputable functions
I know that there exist functions such that no computer program can, given arbitrary input, produce the correct function value. There is nothing, however which would prohibit us from knowing the function value for certain specific inputs.
Suppose we…
Adam
- 3,422
- 1
- 33
- 50
3
votes
1 answer
Understanding of pumping lemma
It seems like I missed something in pumping lemma. Please, help me out
Let's take the simple example from Sipser's book
Prove that language $L = \{0^n1^n | n>=0 \}$ is nonregular. Following the pumping lemma, we choose $s$ to be the string $0^p1^p$,…
com
- 5,612
3
votes
1 answer
Primitive recursive functions with a restriction on the arity of projections
The set of primitive recursive function is defined inductively, starting with a countably infinite set consisting of the constant zero, the successor and all projections $P^n_i$, with $n \ge 1$ and $1 \le i \le n$. It seems very natural to include…
Luca Bressan
- 6,845
3
votes
1 answer
Showing the Rec is $\Sigma_3^0$-complete
In Soare's Computability Theory and Applications, he gives a very quick proof that the following set is $\Sigma_3^0$-complete:
$$\text{Rec} := \{e \mid W_e \text{ is recursive}\}$$
It's fairly straightforward to show that Rec is $\Sigma_3^0$. To…
Alex Kocurek
- 2,991
3
votes
2 answers
Is the function, calculating square root of natural number -- computable?
My question is about domain of the term "computable".
Consider Turing machine, that calculates square roots of natural numbers.
If it gets
4
then it prints out
2
.
and stops.
If it gets
9
then in prints out
3
.
ans stops.
And if it gets…
Dims
- 1,149
3
votes
0 answers
How to alternatively prove: If $A \neq \varnothing$ is domain of $\mu$-recursive $\Omega$, then $A$ is recursively enumerable
I am looking for an alternative yet rigorous proof to a theorem about recursively enumerable sets.
Let $A \subseteq \mathbb{N}_0$ for the purposes of this question. Here is the version of recursive enumerability I am using:
Definition. A set $A$…
Linear Christmas
- 1,285