# Questions tagged [semi-decidability]

Questions about which problems are semi-decidable, also known as recognizable or recursively enumerable.

24 questions
Filter by
Sorted by
Tagged with
5k views

### Why are the total functions not enumerable?

We learned about the concept of enumerations of functions. In practice, they correspond to programming languages. In a passing remark, the professor mentioned that the class of all total functions (i....
2k views

### Is regularity of the language accepted by a given Turing machine a semi-decidable property?

Given is the definition of a general problem: $\{ \langle M, S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of ...
6k views

### Is the language TMs that accept finite languages Turing-recognizable?

I know that $L=\{ \langle M \rangle \mid |L(M)| < \infty \}$ is not decidable (by Rice's theorem or using reduction, I followed it from $L$ not being decidable ). But is $L$ recognizable? What I ...
5k views

### Why is the halting problem semi-decidable?

This is what is known about the halting problem and semi-decidability :- The halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x. ...
599 views

### Is the language of TMs that decide some language Turing-recognizable?

Is the language $\qquad L=\{ \langle \text{M} \rangle \; | \; \text{M is a Turing machine that decides some language} \}$ a Turing-recognizable language? I think it's not, as, even if I am able ...
8k views

### Can a semi-decidable problem be also decidable?

As far as I understand, a semi-decidable (recursively enumerable) problem could be: decidable (recursive) or undecidable (nonrecursively enumerable) ...
56 views

### Decide if a string is a member of a language that represents $P$?

For some enumeration of the complexity class P (such as this as an example: How does an enumerator for machines for languages work?), for each string 𝑝 in the enumeration, does there exist some other ...
1k views

### Is the set of TMs that accept exactly two strings (each) semi-(decidable)?

I have found this problem- let A be the set of encoding of all those Turing machines that accept exactly two strings and let A' be the complement of A. Comment on whether A and A' are recursive , ...
6k views

### Can you recognize or decide if a Turing Machine has an infinite sized language?

That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language? ...
3k views

### The language of machines that accepts all palindromes is not Turing recognizable

I have this question: $L = \{\langle M \rangle | M$ is TM that accepts every palindrome over its alphabet $\}$ Proof that $L$ is not Turing-recognizable by showing reduction from other non ...
2k views

### undecidable problem and its negation is undecidable

A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement. However, ...
11k views

### Why is the class of recursively enumerable languages not closed under complementation?

I am having a hard time understanding closure properties of recrusively enumerable languages. I have read the explanation on this site but still unable to fully understand why they are not closed ...
1k views

### which of the following languages are Recursively Enumerable?

Which of the following languages are recursively enumerable? A={⟨M⟩∣ TM M accepts at most 2 distinct inputs} B={⟨M⟩∣ TM M accepts more than 2 distinct inputs} For first language I think that we can ...