# Questions tagged [semi-decidability]

The tag has no usage guidance.

163 questions
Filter by
Sorted by
Tagged with
54 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 ...
412 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 ...
466 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 ...
512 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 ...
366 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-...
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?...
847 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 ...
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 ...
164 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 ...
507 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 ...
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 ...
339 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 ...
585 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 ...
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 ...
132 views

### Suppose $L_1, L_2, …, L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$. How do I show that each $L_i$ are recursive?

Suppose $L_1, L_2, ..., L_k$ are recursively enumerable languages forming a partition of $\Sigma^*$. How do I show that each $L_i$ are recursive ? I see that for $x \in \Sigma^*$, $x$ belongs to ...
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, ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
51 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'...
882 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 ...
143 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 ...
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 ...
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 ...
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
172 views

50 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....
291 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 ...
738 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 ...
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 ...
82 views

### Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

Define the language $\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$ where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$. Prove that $R$ is co-...
81 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:...
65 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}\,$?
632 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 ...
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/...
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 , ...
916 views

### Function is recursive iff its graph is recursively enumerable

So I understand that a function is recursive if there exist a Turing Machine that accepts it and halts on every input, since function is defined everywhere. But how to prove that function is recursive ...
### 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 ...