Questions tagged [semi-decidability]

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

Filter by
Sorted by
Tagged with
30
votes
2answers
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....
2
votes
1answer
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 ...
2
votes
2answers
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 ...
8
votes
1answer
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. ...
3
votes
2answers
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 ...
2
votes
1answer
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) ...
-1
votes
1answer
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 ...
-2
votes
1answer
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 , ...
4
votes
1answer
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? ...
2
votes
2answers
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 ...
14
votes
3answers
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, ...
5
votes
2answers
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 ...
1
vote
1answer
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 ...
4
votes
1answer
445 views

Show that a language is RE or recursive

Consider these 2 languages: $L_{\ge5} = \left \{ \left< M \right> : M \text{ accepts at least 5 strings} \right\} $ $L_{<5} = \left \{ \left< M \right> : M \text{ accepts fewer ...
2
votes
1answer
259 views

What is the meaning of undecidability in Rice Theorem?

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable? As an example the following language is ...
2
votes
1answer
112 views

Completeness problem of TM

$L = \{ \langle M \rangle \mid L(M) = \Sigma^∗ \}$ Is above problem R.E ? I found an explanation in one of the websites and I have doubt in few lines of paragraph. The explanation was Now, given a ...
2
votes
2answers
200 views

Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable

How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable? Intuitively speaking I think it is indeed undecidable because ...
2
votes
1answer
62 views

Can you build a solver from a verifier?

Given code to just an NP-verifier, where the certificate/witness is required to be of size polynomial in the instance, for a language L, can you, from that data alone, construct code for a solver, or ...
1
vote
1answer
679 views

Closure of Turing-recognizable languages under homomorphism

I've proven that the Turing-recognizable languages are closed under concatenation and I need to show that they are closed under homomorphism. But what's really the difference? Doesn't closure under ...
1
vote
1answer
464 views

Is the set of Gödel numbers of computable constant functions recursively enumerable?

I've been working on the following exercise: $S = \{ x | f_x \text{ is constant} \}$. Is $S$ recursively enumerable? Here, $fx$ is the function computed by the $\text{x-th TM}$. So it is a ...
1
vote
1answer
663 views

If a problem is “not semi-decidable” and “not decidable” can we say it is “undecidable”?

I was under impression that when a Language (or problem) is not semi-decidable and not decidable then we can say it's undecidable and I think it makes sense also based on diagram. However, in my ...
0
votes
1answer
89 views

How to prove semi-decidable = verifiable?

A language L is verifiable iff there is a two-place predicate R ⊆ Σ∗ × Σ∗ such that R is computable, and such that for all x ∈ Σ∗: x ∈ L ⇔ there exists y such that R(x, y) A language is semi-...
0
votes
0answers
143 views

Can we recognize wheter a Turing machine is a decider? [duplicate]

Let $L=\{ \langle M \rangle \mid M \text{ is a Turing Machine which halts on all inputs}\}$. Is this a Turing-recognizable language? I guess that it is neither Turing-recognizable, nor co-Turing-...
0
votes
2answers
3k views

Can languages with infinite strings be recursively enumerable?

I am not 100% sure about the definition of recursively enumarable languages. Yes I know how are they defined: There has to exist a Turing machine that accepts all wrods of the language and halts but ...