# Questions tagged [recursively-enumerable]

The tag has no usage guidance.

26 questions
Filter by
Sorted by
Tagged with
45 views

### Computability- relationship between R, coRE and RE

I am trying to think of a question that discusses the relationship between RE, coRE and R. Namely- is it true that for all For every language 𝐿1∉ RE there exists a language 𝐿2∉ coRE such that 𝐿1∪𝐿...
• 31
126 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 ...
• 211
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 ...
49 views

• 55
1 vote
33 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
91 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 ...
1 vote
36 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
80 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$
81 views

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 $... 0 votes 1 answer 503 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 0 votes 1 answer 387 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 136 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 ...
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
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, ...
93 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 ...
326 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
95 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 ...
• 80