Share Your Experience: Take the 2024 Developer Survey

# Questions tagged [recursively-enumerable]

The tag has no usage guidance.

25 questions
Filter by
Sorted by
Tagged with
27 views

### Good book on (Quantum) Complexity and Computability Theories to start learning the theorem $MIP^* = RE$ as an operator algebraist

I am looking for some greatest references that could help me understand the theorem $MIP^* = RE$ ($MIP*=RE$) step by step. The paper (The Connes Embedding Problem: A guided tour) covers various ...
88 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 ...
273 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 ...
• 101
45 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 ...
• 119
1 vote
93 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?
68 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
1 vote
32 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 ...
• 11
1 vote
53 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.
• 53
94 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 ...
• 74
80 views

• 161
1 vote
312 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" ...
33 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 ...
482 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
147 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 ...
• 150
49 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 vote
84 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 ...
366 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
133 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 ...
1 vote
164 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 ...
112 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
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 ...