Questions tagged [semi-decidability]

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

Filter by
Sorted by
Tagged with
0
votes
1answer
401 views

Is this language semidecidable?

I recently started self studying about algorithms and decision problem, so I don't have a firm grasp on this particular area. In this context I found myself thinking about the following . If $L_1$ is ...
2
votes
1answer
142 views

How to show that the set of TMs that accept languages of size two is recognizable?

I know how to show $\overline{Lx}$ is unrecognizable. I know how to show Lx is undecidable. I would like the mapping reduction function that shows that Lx is recognizable or unrecognizable. For ...
-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 , ...
1
vote
1answer
685 views

Does applying a homomorphism to the intersection of two CSLs yield RE languages?

For each language $L \in L(RE)$ there are a homomorphism $h$ and two context-free languages $L_1$ and $L_2$ such that $L = h(L_1 \cap L_2)$. I understand that this is because context-free languages ...
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, ...
1
vote
1answer
134 views

Problem in Papadimitriou's “Computational Complexity” seems odd

I am studying (on my own, this is not homework) Papadimitriou's "Computational Complexity" textbook, 1st edition. On page 66, we have: 3.4.1. Problem: For each of the following problems involving ...
0
votes
1answer
552 views

Is the superset and subset of a semi-decidable language also semi-decidable? [duplicate]

Given three languages $L_1, L_2, L_3$ with $L_1$ and $L_3$ being semi-decidable and $L_1 \subseteq L_2, L_2 \subseteq L_3$. Can I deduce from these properties, that $L_2$ is also semi-decidable and ...
0
votes
1answer
66 views

Showing that the set of DTMs that run forever is not Turing-recognizable

The language A, that is all DTMS that run forever on input. Would this not just be the HALT problem? Therefore no reduction or proof is necessary, other then stating that? ANSWER FOUND: I think i ...
3
votes
1answer
1k views

Symmetric Difference of Turing Recognizable and Finite Languages

Let A be a Turing Recognizable Language and B a finite Language. I want to prove that their symmetric difference is Turing Recognizable. My reasoning: B is finite, therefore the finite number of ...
1
vote
1answer
4k views

A and B are Turing recognizable, is A - B Turing recognizable?

If A and B are Turing recognizable, is A - B Turing recognizable? I think that A - B would be Turing recognizable because they're both in the space of Turing recognizability. For example, if A is ...
1
vote
0answers
35 views

Proving that pairs of words in resp. not in a TMs language are neither semi- nor co-semi-decidable [closed]

I have a homework assignment in which I am required to determine if $$L = \{ \langle M,x,y \rangle : x\in L(M),y\notin L(M) \}$$ is in $$R,RE-R,coRE-R \text{ or } \overline{RE \cup coRE}$$ Now, my ...
2
votes
1answer
260 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
1k views

Using Generalized Rice's Theorem to Prove Decidability

I have a Turing Machine M with a binary alphabet {1,2} that accepts a language L(M) that has infinitely many strings that start with 1 and finitely many strings that start with 2. I'm trying to ...
3
votes
1answer
72 views

Why is it true that the relation R and its negation are not semi decidable?

An example given for a relation R where its negation and itself are not semi-decidable was: $R(x,y)$ holds iff $y = 0$ then $R_{HALT}(x)$ holds, otherwise $y = 1$ and $R_{HALT}(x)$ does not hold. It'...
1
vote
3answers
1k views

Language is recursive, hence recursively enumerable

I was going through a book of proof and I read: If L is recursive, L is r.e. And the proof goes: Let L be recursive, hence there is a TM that decides it Convert an halt state to a normal state ...
-1
votes
1answer
68 views

Equivalence of Recursively Enumerability (RE) definitions

Let A be a subset of N n Definition1 of RE DEF1_RE = A is RE iff there is a TM M st M(x) = 1 iff x belongs to A, 0/undefined otherwise Definition2 of RE DEF2_RE = A is RE iff there is a recursive/...
1
vote
1answer
200 views

Type of undecidability in Rice Theorem

Rice theorem says every non-trivial property of languages of Turing machines is undecidable. As David Richerby said in here : Undecidable means not decidable. Undecidable problems may or may not ...
0
votes
2answers
228 views

How to find out if a piecewise function is partially computable?

I know exactly what a partially computable function is, but I've seen a few functions that I really can not understand why they are not partially computable. As an example in Davis book page 78, he ...
0
votes
1answer
44 views

P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q [closed]

My problem: Define two sets P and Q of words (that is, two problems) such that: P is undecidable and not semidecidable, Q is undecidable and semidecidable and P ⊂ Q
2
votes
2answers
518 views

will this be decidable or partially decidable?

$A=\{\langle M \rangle \mid M \text{ is a turing machine and }|L(M)|\geq3\}$ Since Recursive enumerable languages are turing enumerable, so listing of all strings of the language in finite time is ...
0
votes
1answer
258 views

True or False: If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable

Question: Is the following statement true or false? If $A \subseteq \{0,1\}^* \Rightarrow A^*$ is semi-decidable I thought that since every language is automatically of type 0, it follows that $A \...
-1
votes
2answers
84 views

Relation between sets and partially computable functions

I encountered this problem. Let $A$ , $B$ , $C$ be disjoint sets $(A\cap B = B\cap C = A\cap C = \emptyset)$. The $f_1, f_2$ and $f_3$ are partially computable functions that are defined as follow:...
1
vote
1answer
263 views

Is $T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$ recognizable?

$$T=\{\langle M\rangle \mid |L(M)| =1 \text{ or } |L(M)| >2\}$$ I started with Rice's theorem (come up with an example where $|L(M)| = 2$) to see that $T$ was undecidable. Then I figured out $\bar{...
0
votes
0answers
54 views

Are all Turing machines recognizable? [duplicate]

Is the language of the set of descriptions of all Turing machines recognizable? I'm thinking not, but I can't quite define why. A language is Turing-recognizable if some Turing machine recognizes it....
2
votes
1answer
437 views

Is w ∈ L(M ) ⟹ ww ∈ L(M) co-semi-decidable?

Consider the following langugage: $\qquad L = \{ \langle M \rangle \mid M \text{ TM}, w \in L(M) \implies ww \in L(M)\}$. I've been asked to decide whether this language is in R/RE/CO-RE. I've ...
2
votes
1answer
1k views

Proving Infinite Turing Machine Language (with finite subset) is Recursively Enumerable

I'm trying to answer this question: Let $S$ be the strings $\langle P \rangle$ accepted by the Turing Machine $P$ with input alphabet $\{a,b\}$, where $P$ accepts an infinite number of strings ...
1
vote
1answer
66 views

Decidability language, intersection

I have two langages $ A, B \in \mathrm{coRE}$. How can I prove that $ A \triangle B= ( A - B) \cup (B - A)$ is also in $\mathrm{coRE}\,$?
4
votes
1answer
790 views

Is the difference of a non-recursive and recursive set recursive?

I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$? $B-A$ is obviously recursively ...
4
votes
3answers
244 views

Is $AlwaysHalt$ recursively enumerable?

I was doing some complexity theory exercices and I came over this one: $AlwaysHalt = \{R(M) | M$ halts with all $x \in \{0,1\}^*\}$ Is $AlwaysHalt$ recursively enumerable? I would say YES and ...
2
votes
2answers
327 views

Is it possible to obtain a total function by composition of partial functions?

This statement is Theorem 1.1 (page 39) of Computability, Complexity and languages by Martin Davis: If function $h$ is obtained from the (partially) computable functions $f$, $g_1$, $g_2$, ..., $...
2
votes
1answer
135 views

Is there a class of formal grammars that generate Recursive Languages only?

Is there a class of formal grammars that generate Recursive Languages only? (ie with which it is not possible to generate non recursive languages.) If so what kind of production rules/restrictions do ...
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 ...
0
votes
2answers
786 views

Extension of Rice's theorem

How can one prove that every nontrivial property of pairs of semi-decidable sets is undecidable? (This is an extension of Rice's theorem that "Every nontrivial property of the r.e. sets is undecidable"...
1
vote
1answer
113 views

Clarification of Hopcroft's proof that “deciding whether a program halts on all inputs” is not R.E

$DoesNotHaltOn\_w=\{(M, w) : M$ does not halt on input w$\}$ $AlwaysHalt =\{ M : M$ halts on all inputs x $\}$ Hopcroft gives the following proof that $AlwaysHalt$ is not R.E. 1) Given an input ...
1
vote
1answer
524 views

Examples for incomparable semi-decidable but undecidable languages

In Schönig and Pruim's Gems of Theoretical Computer Science, the following statement is made: 'Post's Problem', as it has come to be known, is the question of whether there exist undecidable, ...
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-...
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
1answer
1k views

Is there C++ code that takes infinite time to compile?

Is C++ as a formal language recursively enumerable? If yes, is there any invalid C++ code that takes "infinite" time to compile?
1
vote
1answer
316 views

Proving that context-freeness of $L(M)$ is not semi-decidable using Rice's theorem

This is a question from an exam I did today: Given $M$, a turing machine, we need to decide the following: 1) $M$ halts on every input 2) The language of $M$ is CFL My question is, can I ...
7
votes
2answers
4k views

Is it possible for a language and its complement to both be unrecognizable?

Given some unrecognizable language $L$, is it possible for its complement $\overline{L}$ to also be unrecognizable? If some other language $S$ and its complement $\overline{S}$ are both recognizable, ...
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
467 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 ...
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 ...

1 2 3
4