Questions tagged [recursively-enumerable]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0 votes
0 answers
32 views

recursively enumerable and linear bounded automaton

I have a question about linear bounded automaton. Is it false that every recursively enumerable language is recognized by a LBA ? Because LBA has limited tape size so not all recursively enumerable ...
MathJunior's user avatar
0 votes
0 answers
67 views

Turing machine for a^n b^m c^n d^m

The state diagram for the initial part of this turing machine given as: Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back ...
Tanuj's user avatar
  • 101
0 votes
1 answer
39 views

Computability = Enumerating a sequence in the particular order?

In the paper "Computability by Probabilistic Machines" by K. de Leeuw, E. F. Moore, C. E. Shannon, and N. Shapiro (in Claude E. Shannon: Collected Papers , IEEE, 1993, pp.742-771), a ...
Ma Joad's user avatar
  • 101
1 vote
1 answer
35 views

function is computable iff its graph is recursively enumerable?

How do I show that a (possibly partial) function is computable iff its graph is recursively enumerable?
empty-search's user avatar
-1 votes
1 answer
47 views

Need help with a proof: L is recursively enumerable if and only if L is Turing recognizable

I am unable to understand this proof L is recursively enumerable if and only if L is Turing recognizable If anyone can prove this, that would be great help
Henry's user avatar
  • 1
1 vote
0 answers
28 views

Non-Deterministic Turing Machine That Accepts RE-R language

As far as I know for Non-Deterministic Turing Machine (NTM) there are 4 kind of branches: An input is accepted if there is at least one node in the tree that is an accept. An input is rejected if all ...
Yuval's user avatar
  • 11
1 vote
1 answer
42 views

P NP R RE closures

I wrote the following table for all the closures in those classes. is anything there incorrect? also, would appreciate help with coNP and coRE closures. couldn't find much information about it online.
Skynet's user avatar
  • 53
0 votes
0 answers
23 views

Proving a language is recursively enumerable

Prove that the following language is recursively enumerable: L = {<M,x> | Turing machine M enters the same configuration twice on input x} I have tried to construct a TM that maintains the ...
revision's user avatar
0 votes
2 answers
65 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 $...
Benicio Agüero's user avatar
1 vote
0 answers
24 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\...
Ariel Yael's user avatar
0 votes
0 answers
46 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? ...
Nicola 's user avatar
1 vote
1 answer
209 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" ...
Pratik Hadawale's user avatar
0 votes
0 answers
32 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 ...
Ashman's user avatar
  • 1
0 votes
1 answer
258 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 ...
Druckermann's user avatar
2 votes
2 answers
117 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 ...
muser's user avatar
  • 140
0 votes
1 answer
46 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, ...
Ccret's user avatar
  • 1
1 vote
0 answers
67 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 ...
obolenskaya00's user avatar
0 votes
1 answer
291 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 ...
N O's user avatar
  • 3
0 votes
1 answer
102 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 ...
Aylin Naebzadeh's user avatar
1 vote
1 answer
128 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 ...
Benicio Agüero's user avatar
2 votes
2 answers
97 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 ...
Audra Jacot's user avatar
1 vote
0 answers
35 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 ...
Benicio Agüero's user avatar
2 votes
1 answer
108 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 ...
HappyFace's user avatar
  • 191
1 vote
1 answer
163 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 $\...
Saar BK's user avatar
  • 55
1 vote
2 answers
78 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$
ChaosPredictor's user avatar