Questions tagged [semi-decidability]
The semi-decidability tag has no usage guidance.
163
questions
1
vote
0answers
20 views
Proving Problems are Undecidable/ Semi decidable? E.g. Halting Problem, Membership Problem? [duplicate]
I am having issues finding similarities in different cases where a problem such as the Halting Problem or the Accept-Λ problem is reduced to the Membership problem to prove that it is semi-decidable ...
0
votes
0answers
28 views
A TM that doesn't decide Σ*, and a TM that doesn't decide the empty set?
I was wondering if it was possible to create a TM that semi-decides (but doesn't decide) either of the following two languages:
$\emptyset$
$\Sigma^{*}$
I assume for 2, a one-state TM that just ...
0
votes
1answer
44 views
Proving a language is not Semidecidable
I have the language $L = \{ \langle M_1, M_2 \rangle : L(M_1) \subset L(M_2)\}$ and I'd like to prove that it is not Semidecidable. To do so, I need to use a reduction from $\neg H$. I cannot use Rice'...
1
vote
1answer
182 views
Is it decidable “Given a TM M, whether M ever writes a non blank symbol when started on the empty tape.”
I came across below problem in this pdf:
Given a TM M, whether M ever writes a non blank symbol when started on the empty tape.
Solution given is as follows:
Let the machine only writes blank ...
3
votes
3answers
158 views
Is it possible that the subtraction between two undecidable languages is regular?
If $L_1$ and $L_2$ are both non-decidable languages (Not decidable, so can be SD
or $\lnot$SD), is it possible that $L_1-L_2$ is regular and $L_1-L_2\neq\phi$, where $\phi$ is the empty set?
What's ...
2
votes
1answer
53 views
Is this language Recursively Enumerable or Not RE?
$L = \{\langle M, k\rangle : M\;\text{is a Turing Machine and } |\{w \in L(M) : w \in a^*b^*\}|
\geq k \}$
My Interpretation of language is that $L$ is a language which contains Turing machine ...
1
vote
1answer
51 views
How can I show that a language is Turing-recognizable and decidable?
I was wondering how I can show that the language $\{a^n b^n c^n \mid n \geq 0 \}$ is Turing-recognizable. Also, if it is Turing-decidable?
0
votes
1answer
53 views
Decidability of the language of all deterministic LBA where all states are reachable
I have a exam task with 3 parts. (b) is no problem. I got a solution for (a) but the way (c) is asked makes me wonder if I even understood (a)
(a) L := { < A > | A is a DFSA, where all states are ...
0
votes
1answer
50 views
Decidability of decision problems
Can somebody give intuition how to answer those questions? From one side I can say that most of them are undecidable because we can reduce the halting problem to them (or halting problem can appear ...
0
votes
1answer
177 views
Why is a subset of a undecidable language decidable?
I have problems with the understanding why a subset of a undecidable language is decidable. We've proved in the lecture that $HALT$$_T$$_M$$=${$<M,w>$|M is a TM and M halts on input w} is ...
3
votes
1answer
229 views
Which languages, decided by a turing machine are decidable?
How do I decide if a language is decidable and/or semi-decidable?
I have theses languages:
a) { < M > | L(M) ⊆ 0*}
b) { < M > | L(M) contains at least one word of even length}
c) {...
2
votes
1answer
30 views
Turing Machine equivalence in MinTM proof
The proof with contradiction that $MIN_{\mathrm{TM}}$ is not Turing-recognizable from Michael Sipser's textbook "Introduction to the Theory of Computation" (Theorem 6.7) is as follows:
$C=$ "On ...
0
votes
1answer
116 views
Is the halting problem undecidable or unrecognizable? [duplicate]
Is the Halting problem in the class of undecidable problems, or it is just in the set of unrecognizable problems?
I understand that if it is undecidable, then it is also unrecognizable. I have seen ...
1
vote
2answers
53 views
Is a language whose Turing Machine doesn't halt for some positive cases but for others does not recursive?
Say language $L$ is recursively enumerable, but not recursive.
Say $a$ and $b$ are symbols of the alphabet and $w$ a word.
Say we have the following language:
$L' = \{ aw | w \in L \} \cup \{ bw | w \...
1
vote
1answer
48 views
Is $ L = \{ a^n\ |\ a^n \not\in L_n \} $ Turing recognizable (recursively enumerable)?
Say $ \Sigma = \{a\} $, $M_1, M_2, ... $ is an enumeration of all TMs that recognize languages over $\Sigma$ and $L_1, L_2, ... $ are respectively the languages that are recognized by those TMs. We ...
1
vote
1answer
34 views
Recognizably turing machine question (reject / loop)
The definition of proving recognizability using dove tailing is below. However I'm wondering if we can also prove loop or reject in the same way?
Give a deterministic TM D that recognizes L such that ...
3
votes
1answer
64 views
Is the language of all TMs *not* accepting a given string, Enumerable?
Is the following language in RE?
$$L = \{\langle M\rangle : M\text{ is a TM that does not accept }010\}$$
I could use Rice's Theorem with the property $P = \{L : 010\text{ is not in }L\}$ to show ...
2
votes
1answer
43 views
How To Show That B is Semi-Decidable Given A
I am preparing for my Computational Theory final and ran into this exact problem :
B={ x | there exists a prefix of x that is in A}.
Show that B is semi-decidable. In other words, you need to ...
1
vote
1answer
780 views
Is it decidable whether a Turing machine M will reach state q on input s?
Given a turing machine $M$, one of its states $q$ and an input word $w$, will $M$ ever reach $q$ on $w$?
As we are not given anything about the word length, I assume that we have a finite length word....
2
votes
1answer
102 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
182 views
Prove Halting on all Inputs is not in RE simulation
I don't understand why when proving if Halting on all inputs problem si not in RE using the complement of the halting problem, I have to take a turing machine and simulate the machine M(the machine ...
1
vote
1answer
59 views
REC and RE under intersection
Would the intersection of a recursive language and a recursively enumarable language be recursive or recurisvely enumbarable or neither?
Assume $L_{3}$ is the intersection of some language $L_{1}$ $\...
-3
votes
3answers
126 views
Does undecidability violate Turing completeness? Shouldn't “complete” include “decidability”? [closed]
Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"?
That is, if one has a language that's Turing complete, but expresses infinite computation (i.e. may not ...
1
vote
1answer
103 views
How do I construct a NTM that accepts the language consisting of the coding of turing machines that halt on one input?
I currently have a problem with the following question:
Let $L = \{ \langle M \rangle \mid \exists w: \text{$M$ halts for $w$ in at most $|w|^3$ steps} \}$.
Construct an NTM (non-deterministic Turing ...
4
votes
1answer
88 views
Is Rice-Shapiro theorem bidirectional?
Rice-Shapiro theorem states that
version A
Let $\Gamma$ be a set of computably enumerable sets, and $I = \{e : W_e \in \Gamma\}$ its index set in some admissible enumeration of c.e sets. If $I$...
1
vote
1answer
96 views
Can the complement of an unrecognizable language be a recognizable language?
I know that complement of a language that is recursively enumerable, but not recursive, is definitely not recursively enumerable (or unrecognizable). So my question is what can be said about the ...
1
vote
2answers
195 views
Why are not all recursive languages undecidable?
I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know.
If ...
0
votes
0answers
28 views
A set that is not recursively enumerable and not (K'≤ A)
Is there a set A such that it's not recursively enumerable and not(K'≤ A) ?
where K' is complement of K= {n| φ n (n) halts}
Thanks!
3
votes
1answer
115 views
Efficient algorithm to determine if a lambda calculus term is equivalent to one without a given free variable
Consider the following problem: given a lambda calculus term $t$ and free variable $v$ determine whether $\phi(t,v)$, where $\phi(t,v) := \exists t'. t' \equiv t \land v \notin FV(t')$.
This problem ...
1
vote
2answers
73 views
Need help understanding what co-recursively enumerable means
Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \Sigma^{\star}\}$ and the question asks if it is co-RE. I know that if something is co-RE, it halts on every input not in L but may or may not ...
1
vote
1answer
46 views
Is the set of context free grammars that generate all words in co-RE?
Is $\{\langle G \rangle | L(G) = \sum^{\star}\}$ in co-RE? $\langle G \rangle$ is the encoding of a context free grammar. My intuition is that this is false.
0
votes
1answer
134 views
Whether language of all turing machines is decidable or undecidable or semi-decidable?
I recently came across this language:
$L=\{<TM>| \text{TM accepts recursively enumerable languages}\}$
It was asked in the question to find out whether language L is decidable or undecidable.
...
0
votes
1answer
257 views
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference
Prove/disprove that the class of decidable (resp. partially decidable) languages is closed under symmetric difference. A symmetric difference of sets A and B is the set (A \ B) ∪ (B \ A).
I know that ...
0
votes
1answer
181 views
Proving a set is semi-decidable
Let $S = \{ ⟨M,q⟩ | (\exists x) M $ reaches state $q$ when running $M$ on $x$$\}$, where ⟨M,q⟩ is coded TM M and state q.
To prove that $S$ is semi-decidable, I've tried to use the equivalence:
...
2
votes
1answer
618 views
Determining if given languages are regular or recursively enumerable
I came across following problem:
Suppose $L_1$ and $L_2$ are two languages, $M$ is a Turing machine
$L_1 =\{M|M$ accepts at most 2016 strings$\}$
$L_2=\{M|M$ accepts at least 2016 strings$\}$
...
1
vote
3answers
452 views
Proof that total computable functions are not enumerable
In an answer to this question, a sketch of the proof that total computable functions are not enumerable is made:
Because of diagonalization. If $(f_e:e \in N)$ was a computable enumeration of all ...
2
votes
1answer
51 views
When does an extendible 1:1 p.c. function have a 1:1 computable extension?
A partial computable function $\varphi_e$, defined on a c.e. set $W_e$, is called extendible if there exists some computable function $f$ which extends $\varphi_e$, i.e. $\varphi_e(W_e) = f(W_e)$.
My ...
2
votes
1answer
67 views
If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable?
If Q1 and Q2 are countably enumerable, then is Q1\Q2 countably enumerable?
I am reading a text where they claim that this is not the case and ask the reader to come up with a counter example.
Can ...
0
votes
1answer
608 views
Why is the intersection of these two Languages Recursively Enumerable, not Recursive?
I am only several days exposed to computational theory, so my understanding is quite slim: in a question, it says that for a regular language L1 and a recursively enumerable but not recursive language ...
-2
votes
1answer
35 views
Show that $L = L_\phi \cup L_{\{\sum^*\}} \notin RE$ with Rice theorem
Show that $L = L_\phi \cup L_{\{\sum^*\}} \notin RE$ with Rice theorem.
Well I did show that with reduction, by using $HP'$.
Simply by creating a function from $f(\langle M \rangle, x) = (M')$
Thus,...
1
vote
1answer
1k views
What is the difference between undecidable language and Turing Recognizable language?
I was wondering what is the difference difference undecidable language and Turing recognizable language. I've seen in some cases where they ask:
Prove that the language $ A_{TM} = \{ \ <M,w> | \...
0
votes
0answers
32 views
How to prove that for a decidable problem the problem and the compliment of the problem are semi-decidable?
Given a decidable problem, how would I go about proofing that the problem and the complement of the problem have to be semi-decidable?
1
vote
1answer
584 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 ...
0
votes
1answer
65 views
Does the language of TM's that repeat a configuration infinite times semi-decidable or not?
Let us define the following languages:
$$ {L_1 = \{\langle M\rangle : M \ \text{is a TM and $\exists w\in \Sigma^*$ s.t $M(w)$ repeats a configuration infinite times}\}} $$
$$ L_2 = \{\langle M\...
0
votes
0answers
267 views
Decidability of intersection of two languages of same type
Given two context-sensitive languages, $L_1$ and $L_2$ is the problem of "whether $L_1 \cap L_2$ also belongs to CSL" decidable?
I have the same question for the case when $L_1$ and $L_2$ belongs to ...
0
votes
0answers
26 views
Give an example of a language where both L and ¬L is not semidecidable? [duplicate]
I know ¬H is not semidecidable so I was thinking of creating a language that combines both H and ¬H. Therefore L would be undecidable for ¬H and ¬L would be undecidable for H. Is this a proper ...
0
votes
2answers
47 views
Function whose domain is strictly included in its range
Hi I'm doing some exercices on reductions and one of them is like this:
My problem rather than doing the reduction is understanding it. For the positive case I want that if Mx(x) never stops then p'...
0
votes
0answers
39 views
Is the language below not decidable , if yes , it is then R.E ?
I am given a Turing machine M as input and i have to find out if this language below decidable and if not is it then in this case recursively enumerable .
$$L=\\\{<M> \mid \text{ is ...
0
votes
1answer
89 views
Prove that an infinite set is semidecidible
I have been asked to prove that:
Being C an infinite set. Prove that C is semidecidable if and only if exists a total computable function that is injective and whose image is C.
I've read the ...
2
votes
1answer
110 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 ...
