Questions tagged [recursively-enumerable]
The recursively-enumerable tag has no usage guidance.
19
questions
0
votes
2
answers
37
views
Unlimited use subset sum
Given a finite set of integers $Z$ and a number $z$, I would like to check if there exists a subset $A=\left\{ a_1,...,a_{\left| A\right|}\right\}\subseteq{Z}$ and a set of $\left| A\right|$ numbers $...
- 113
1
vote
0
answers
21
views
Reduction from $\mathsf{ALL}_{\mathsf{TM}}$ to it's complement
I'd like to know if there's a reduction $\mathsf{ALL}_{\mathsf{TM}}\leq_{m}\overline{\mathsf{ALL}_{\mathsf{TM}}}$ where of course $\mathsf{ALL}_{\mathsf{TM}}=\left\{ \left\langle M\right\rangle \mid\...
- 141
0
votes
0
answers
31
views
Equivalence for Turing Machines is not Recognizable - Reduction DOUBT
I have a big doubt on this video about $EQ_{TM}$, especially on minute 5:11.
Why is he saying that to reduce $ A_{TM}\lt_{m}\overline{EQ_{TM}} $ we need to create a machine M that rejects every input?
...
- 3
1
vote
1
answer
66
views
Is Enumerator a variant of Turing machine that starts with empty string and builds according to the description of language
My understanding is an "Enumerator" is a Turing Machine that: instead of taking an input string, then going through a series of transitions and "halting" or "not halting" ...
- 305
0
votes
0
answers
28
views
Show that Language L = { <M> | M is a TM and {b}* ∩ L(M) ≠ ∅ } is recursively enumerable?
I'm not sure how to show that the language L = {M | M is a TM and {b}* ∩ L(M) ≠ ∅ } is recursively enumerable. I understand that if there is a DTM that accepts every word of the given alphabet, it is ...
- 1
0
votes
1
answer
89
views
Is the infinite union of decidable languages decidable?
I am currently struggling with figuring out the following problem:
Given decidable languages L1, L2, L3, L4, ...
Is the infinite union of Languages L1, ...... decidable? I have an intution that it is ...
- 103
2
votes
2
answers
81
views
Alternate definition of recursively enumerable languages
Exercise 9.2.3(c) of the book by Hoffman, Motwani, Ullman states
In fact a definition of the RE-but-not-recursive languages is that they can be enumerated but not in numerical order
How do we show ...
- 141
0
votes
1
answer
38
views
Recursive enumerable class or its complement?
If K = {<<M>> | L(M) has at least 1 word}, then does K belong to the class of recursive enumerable (RE) languages or its complement?
I'm a bit confused, ...
- 1
1
vote
0
answers
33
views
acceptance of non-recursively enumerable language by the Turing machine
I'd like to know if there's a non-recursively computable language that can be accepted by the Turing machine.
From the following definition of the recursively enumerable language:
and from the fact ...
0
votes
1
answer
201
views
Is the set of Turing machines that halt on infinitely many inputs not recursively enumerable?
Consider this "generalized halting problem":
$$
GHP = \{<M>| \mbox{ there are infinitely many inputs that $M$ halts on}\}.
$$
I'd like to prove that $GHP\notin RE$, but it doesn't seem ...
- 3
0
votes
1
answer
55
views
Let $L$ be a finite language. Show that then $L^+$ is recursively enumerable. Suggest an enumeration procedure for $L^+$
I am solving basic questions about Recursive and Recursively-Enumerable languages. I know that base on the below theorem, to prove that a language is RE we should define an Enumeration Procedure for ...
0
votes
0
answers
157
views
Prove that neither given language nor its complement is recursively enumerable
Let $L = \{\langle M, n\rangle \mid\,\, n \geq 5000$ and $M$ is Turing machine that halts for every input and leaves at least $n$ non-blank symbols on the tape when stopping $\}$.
I believe neither ...
1
vote
1
answer
92
views
Exact formulation of definition of $NP$, in relation to $R$
One definition for $P$ is the set of all languages that have a deterministic turing machine $M$ s.t. if $x\in A$ the machine accepts in polynomial time and otherwise it rejects, also in polynomial ...
- 113
2
votes
2
answers
74
views
Is the problem of "DFA-TM-INCLUSION" recursively enumerable?
Consider the following problem:
Input: A Turing Machine M and a DFA D.
Question: Is $L(D) \subseteq L(M)$?
Of course, this problem is not decidable. Because it is known that judging whether a word ...
- 23
1
vote
0
answers
33
views
How to show a language is not recursive, without using reductions?
I would like to show a language is in not recursive (not in the family $R$) without using a reduction from a language that is known to be non-recursive. In other words, its as if I am discovering the ...
- 113
1
vote
1
answer
73
views
What are some examples of non-enumerable languages whose complement isn't either?
What are some examples of non-enumerable languages whose complement isn't either? I.e., a language L such that L is not Turning-recognizable and L’ is not Turing-recognizable either.
Update: Found ...
- 181
1
vote
1
answer
119
views
On the language of Turing machines that accepts 1 but does not accept 0
I need to find the find the minimal
class $\mathcal{L}$ belongs to where
$$\mathcal{L} = \{\langle M \rangle: M \text{ is a TM that accepts 1 but does not accept 0}\}.$$
I think I can prove that $\...
- 55
0
votes
0
answers
84
views
Prove that a subset of $\Sigma^{*}$ is recursively enumerable if and only if it is the range of a partially computable function?
I was assigned the following question for my course on Computing Theory:
Take $\Sigma = \{0, 1\}$. Prove that $ S\subset \Sigma^{*}$ is recursively enumerable if and only if $S$ is the range of a ...
1
vote
2
answers
75
views
What is known about $S$ if $\{\langle M\rangle : L(M)\in S \}$ is recursive or recursively enumerable
For $L_S=\{\langle M\rangle : L(M)\in S \}$ what is known about $S$ in case of:
$L_S\in RE$
$L_S\in R$
- 373