Questions tagged [recursively-enumerable]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
2 answers
51 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 ...
user avatar
0 votes
0 answers
28 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 ...
user avatar
1 vote
1 answer
41 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 ...
user avatar
  • 161
1 vote
1 answer
51 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 $\...
user avatar
  • 55
0 votes
0 answers
49 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 ...
user avatar