We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [semi-decidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
29
votes
2answers
4k 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
1k 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
4k 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 ...
7
votes
1answer
4k views

Why is the halting problem semi-decidable?

This is what is know about halting problem and semi-decidability :- 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. A ...
3
votes
2answers
503 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
941 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
4k 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
2k 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 ...
13
votes
3answers
1k 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, ...
3
votes
1answer
6k 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) ...
3
votes
2answers
8k 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
836 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 ...
3
votes
1answer
378 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
109 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
1answer
210 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
92 views

Prove the languages |L<M>| = 2 and |L<M>| $\not=$ 2 to be non-Turing recognizable or non-recursively enumerable

I am trying to prove the non-recursively enumerable property of two languages. $L_2 = \{\langle M \rangle: |L\langle M \rangle| = 2\}$ and $L_{\not=2} = \{\langle M \rangle: |L\langle M \rangle| \not=...
1
vote
1answer
380 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
562 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
511 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
2answers
2k 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 ...
0
votes
0answers
142 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-...