Questions tagged [recursively-enumerable]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
1 answer
34 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
70 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 ...
  • 121
0 votes
1 answer
36 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
29 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
151 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
37 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
108 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
74 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
70 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
63 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 ...
  • 161
1 vote
1 answer
100 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
71 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$