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
4 answers
properties of recursively enumerable sets
$A \times B$ is an r.e.(recursively enumerable) set, I want to show that $A$ (or $B$) is r.e. ($A$ and $B$ are nonempty)
I need to find a formula. I've got an idea that I should use the symbolic definition of an r.e. set. That is, writing a…
Gigili
- 5,503
- 8
- 41
- 62
3
votes
2 answers
Is Turing-completeness decidable?
This may be a silly question, but is there an algorithm that decides whether any given model of computation is Turing complete?
goblin GONE
- 67,744
3
votes
1 answer
Non repeating complete list of partial recursive functions
Is it possible to list all partial recursive functions such that every function appears only once in the enumeration. More precisely, does there exist (total) recursive function $f:\mathbb{N} \rightarrow \mathbb{N}$ such that for any two different…
SSequence
- 1,022
3
votes
1 answer
Proving that a separating set is not computable
Let $X =$ {$d$ : $\psi_d(0)=0\}$ and $Y$ = { $d$ : $\psi_d(0) = 1$ }. Show that if $S\subseteq \mathbb{N}$ has the property $X \subseteq S$ and $Y \cap S = \emptyset$ then $S$ is not recursive.
So I was thinking if I could find some function $f$…
Rex
- 167
3
votes
1 answer
Reducing the complexity of a turing machine algorithm
i'm trying to solve this question:
Given a turing machine that is decidable by at most 50 * n^4 steps, can we build a dif algorithm that can decide it in n^4 steps?
Me and my friends thought about it, and we coulnd't get it right.
Some points we had…
Adibe7
- 131
3
votes
2 answers
Undecidable languages and mapping reducibility
I am using Sipser terminology here.
Can anyone give examples of languages A and B such that we can prove B is undecidable using A in a proof by contradiction but we A is not $\leq_m$ B.
An example of this is $E_{TM}$ as defined on page 89 of…
starflyer
- 550
3
votes
1 answer
Difference in 1-1 vs many-1 Reducibility
Let B be many-one reducible to A i.e. $B \leq_m A$ if there is a computable function $f$ s.t. for all $x\in \mathbb{N}$:
$$
x \in B \iff f(x) \in A
$$
If the function $f$ is one-one (injective) then B is said to be one-one reducible to A i.e. $B…
gowrath
- 3,573
- 13
- 31
3
votes
1 answer
Show that $f(x,y)=\lfloor x/y \rfloor$ is primitive recursive
So, I want to show that the aforementioned function is primitive recursive.
Here's my idea: let $k$ be the smallest number such that $ky > x$. Clearly then $f(x,y) = k -1$.
I then have the following procedure for computing $f$ in mind
for k = 0:x
…
wet
- 605
3
votes
2 answers
Recursive functions
I want to show that the domain of any partially defined recursive function is equal to the range of some ( totally defined ) recursive function.
I haven't understood which is the difference between a partially defined recursive function and a…
Evinda
- 1,460
3
votes
1 answer
The emptiness problem for "lunatic" and "crazy" Turing machines
Crazy Turing Machine is the same as Turing machine with one stripe , except of the fact that after each ten steps the head jumps back to the beginning of the stripe.
Lunatic Turing Machine is the same as Turing machine with one stripe , except of…
Jozef
- 7,100
3
votes
1 answer
Computable function and decidable sets: For a computable $g$ and decidable set $A$ , Does $g(A), g^{-1}(A)$ necessarily decidable?
I'm trying to solve the following exercise from an old exam:
For a computable function $G: \mathbb{N} \to \mathbb{N} $, and a set of numbers $A$, we define $g^{-1}(A)=\{x|g(x) \in A\} $ and $g(A)=\{g(x)| x\in A\}$. If $A$ is a decidable group…
Jozef
- 7,100
3
votes
2 answers
Is the set of all Turing machines whose language includes the set of all even length strings recursively enumerable?
Is the set of all Turing machines whose language includes the set of all even length strings recursively enumerable?
My intuition tells me the answer should be no, but I can't prove it.
I know that it should be non-recursive because the property…
student
- 31
3
votes
0 answers
Having trouble with the basic interpretation of "s-m-n theorem"
The s-m-n theorem
Suppose that $f(x,y)$ is a computable function (not necessarily total). Then for each fixed value $a$ of $x$, $f$ gives rise to a unary computable function $g_a$, where
$$g_a(y)\cong f(a,y)$$
Since $g_a$ is computable, it has an…
user270452
- 67
3
votes
1 answer
Infinite finitely branching recursive tree with no path whose graph is $\Delta^0_2$
I am trying to construct an example of a infinite, finitely branching, recursive tree $T$ such that none of its paths has a graph which is $\Delta^0_2$. I denote the set of paths of $T$ by $[T]$. I have shown that if the tree $T$ is recursively…
CWcx
- 608
3
votes
2 answers
Is there a Turing Machine that can distinguish the Halting problem among others?
Can there be a Turing machine, that given two oracles, if one of them is the Halting problem, then this machine can output the Halting problem itself?
Clearly, if the first oracle is always the Halting problem, then such machine exists, just copy…
