# Questions tagged [semi-decidability]

The tag has no usage guidance.

163 questions
Filter by
Sorted by
Tagged with
1k views

### Does Every Recognizable language has a subset not Recognizable?

Does every Turing Recognizable language has a subset which is not turing recognizable? i can give some examples but can't prove in general
126 views

### Proof that {(M,w) | M accepts a prefix of w} is RE

Can someone help me go over that the following language can be recognized by a Turing Machine? $$L = \{\langle M,w\rangle \mid M \text{ accepts a prefix of } w\}$$ We can construct a universal ...
798 views

### Is Post's correspondence problem recognizable?

I want to know whether Post Correspondence Problem (PCP) is recognizable. I learnt how to demonstrate the undecidability of PCP. I thought to use the similar approach for recognizability too i.e. to ...
238 views

### Showing undecidability

I'm given the set $T = \{\langle M, w\rangle : M$ is a Turing Machine that accepts $w^\mathcal R$ whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the ...
229 views

Let $L_{NTF} = \{ \langle M \rangle \mid$ for every $x\in\Sigma^*$ the machine $M$ does not reach the $|x|+10$'th cell during its calculation on $x$. $\}$. I would like to prove or disprove $L_{... 2answers 106 views ### Is the following language decidable, enumerable or non-enumerable? $$L = \{\langle M_1 \rangle, \langle M_2 \rangle \mid \text{$$M_1$$ and $$M_2$$ are TMs and $$\forall X, M_1(X) = M_2(X)$$}\}$$ Is this language decidable, enumerable, or non-enumerable? And in ... 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 ... 1answer 2k views ### Reduction from ATM to ATM-complement Is there a reduction from ATM to ATM-complement? (ATM denotes the language$\{\langle M,w \rangle \mid \text{TM $M$ accepts $w$}\}$) I have been thinking about it too much and couldn't find the ... 2answers 53 views ### How to argue about semi-decidability of a problem? I have the following problem, and I try to prove that it is semi-decidable, but I have a hard time arguing about it. I know that if a problem$\mathcal{P}$is semi-decidable, then we can build a ... 2answers 405 views ### Undecidable language and Turing Machines I am reviewing some old papers for a final tomorrow, and there is a question that I'm not sure about. If a language A is Turing-Recognizable and Undecidable, what can be said of the Turing-Machine ... 0answers 460 views ### Is English Recursively enumerable? [closed] The title says it all. I've tried digging up debate on this issue to see a proof one way or the other but it doesn't look like anyone is able to say whether or not it is. Clearly there are recursive ... 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.... 2answers 362 views ### A non-mechanical way to get an infinite decidable subset of a Turing-recognizable language? There's a famous theorem that every infinite Turing-recognizable language has an infinite decidable subset. The standard proof of this result works by constructing an enumerator for the Turing-... 0answers 501 views ### Showing that$H'$is not semi-decidable I have an introductory class in computability theory and I'm currently working on my first exercises. I'm wondering if I'm on the right track with proving undecidable languages. Could you please have ... 2answers 311 views ### set of Kolmogorov-random strings is co-re given RC = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings. How can I show that RC is co-re I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random Strings?... 1answer 839 views ### Mapping reducibility vs. Turing reducibility Let$A$and$B$be two languages. If$A \le_{m} B$( reducible by mapping ) then I know that if$B$is decidable so is$A$and if$B$is recognizable so is$A$. And if$A \le_{T} B$, then if$B$is ... 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 ... 0answers 163 views ### How to prove a Language is neither a Computably enumerable nor Co-Computably enumerable? What would be the general approach for that? And what are the things that generally overlooked while proving such things? For example, I have a Language, L ={e:$L(M_e)$such that it accepts only 'a ... 2answers 506 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 ... 1answer 1k views ### Proving that a language of Turing machine descriptions is/is not Turing recognizable How to approach to solve this question and the likes of it? Let$L$be the set of strings$\langle M\rangle$such that$M$accepts all strings of even length and does not accept any strings of odd ... 1answer 336 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 ... 1answer 119 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 ... 1answer 998 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 , ... 1answer 583 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 ... 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, ... 1answer 123 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 ... 1answer 410 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 ... 1answer 61 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 ... 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 ... 1answer 3k 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 ... 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 ... 1answer 212 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 ... 1answer 730 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 ... 1answer 50 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'... 3answers 816 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 ... 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/... 1answer 142 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 ... 2answers 182 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 ... 1answer 40 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 2answers 389 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 ... 1answer 169 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 \...
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:...