Questions tagged [semi-decidability]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3
votes
2answers
497 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 ...
1
vote
1answer
966 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 ...
0
votes
1answer
311 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 ...
1
vote
1answer
534 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 ...
2
votes
1answer
112 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 ...
1
vote
1answer
127 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 ...
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, ...
1
vote
1answer
114 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
375 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
60 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
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 ...
1
vote
0answers
34 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 ...
3
votes
1answer
46 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
702 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
vote
1answer
131 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 ...
2
votes
1answer
200 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 ...
0
votes
2answers
167 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
39 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
0
votes
1answer
137 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 \...
2
votes
2answers
362 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 ...
1
vote
1answer
218 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
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....
2
votes
1answer
269 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
693 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 ...
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 ...
5
votes
2answers
80 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-...
-1
votes
2answers
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:...
1
vote
1answer
63 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
578 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 ...
-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/...
-2
votes
1answer
894 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
2answers
817 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 ...
4
votes
3answers
213 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
240 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$, ..., $...
6
votes
2answers
8k views

How to prove that a language is not recursively enumerable

How does one prove that some arbitrary language $L$ is not recursively enumerable? I know I can prove that the language $L$ is recursively enumerable by constructing a Turing machine $M$ that accepts ...
2
votes
1answer
102 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 ...
3
votes
2answers
413 views

The Hindley-Milner type system plus polymorphic recursion is undecidable or semidecidable?

I have often read that Hindley-Milner extended to allow polymorphic recursion is undecidable. However is the term used what is actually meant? Or do people actually mean semidecidable when they ...
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 ...
-1
votes
2answers
472 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
106 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
429 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
141 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
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
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?
6
votes
2answers
2k 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, ...
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
249 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 ...
4
votes
4answers
188 views

Is the set of programs that compute some function other than $h$ recursively enumerable?

Let $h$ be a total computable function. Is $S = \{x \mid f_x \neq h\}$ recursively enumerable? Originally this was an exercise that restricted $h$ to: $h(x) = x + 1$ . However, it can be formulated ...
1
vote
1answer
378 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 ...