Questions tagged [recursively-enumerable]
The recursively-enumerable tag has no usage guidance.
25
questions
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 ...
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 ...
- 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 ...
- 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?
- 23
-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
- 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 ...
- 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.
- 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 ...
- 23
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 $...
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\...
- 141
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?
...
- 3
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" ...
- 305
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 ...
- 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 ...
- 103
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 ...
- 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, ...
- 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 ...
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 ...
- 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 ...
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 ...
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 ...
- 23
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 ...
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 ...
- 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 $\...
- 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$
- 373