Questions tagged [recursively-enumerable]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
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 $...
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\...
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? ...
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" ...
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 ...
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 ...
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 ...
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 ...
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$