Questions tagged [semi-decidability]
The semi-decidability tag has no usage guidance.
-3
votes
3answers
74 views
Does undecidability violate Turing completeness? Shouldn't “complete” include “decidability”?
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
31 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
54 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
24 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
87 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
25 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!
0
votes
0answers
11 views
How to know if a lanugae is undecidable or semi-decidable
I recently learnt about undecidable languages and semi-decidable languages. But I am still quite confused on how I can determine if a language is semi-decidable. Is there any standard theorem or axiom ...
3
votes
1answer
47 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 ...
0
votes
1answer
35 views
Need help understanding what co-recursively enumerable means
Lets say I have a set: $ L = \{\langle G \rangle | L(G) = \sum^{\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
35 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
0answers
17 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
0answers
17 views
Non-Turing-recognizable Language [duplicate]
I have been stuck on this problem for a while:
Show that $L=\{\langle M \rangle : L(M) \text{ contains an even number of strings} \}$ is not Turing-recognizable.
I know that by Rice Theorem, this ...
0
votes
1answer
36 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
17 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
343 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$\}$
...
0
votes
3answers
137 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
38 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
54 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
170 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 ...
-3
votes
1answer
32 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
359 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
24 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
469 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
61 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
151 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
19 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
45 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
35 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
59 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
98 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 ...
1
vote
1answer
333 views
If a problem is “not semi-decidable” and “not decidable” can we say it is “undecidable”?
I was under impression that when a Language (or problem) is not semi-decidable and not decidable then we can say it's undecidable and I think it makes sense also based on diagram.
However, in my ...
0
votes
0answers
61 views
Decidability of {(M,w); M terminates on input w and tape of M is empty after computation}
I am currently trying to prove whether the above language is decidable, partially decidable or fully undecidable. I am certain that this language is partially decidable and reducible to the halting ...
0
votes
0answers
108 views
Turing machine accepts two different strings
I am having hard time to proving this problem
$C=\{\langle M \rangle \mid M \text{ is a Turing Machine , } L(M) \text { only contains two different strings}\}$
some ideas that i have tried are :
i ...
0
votes
0answers
47 views
Prove whether this language is (partially) decidable [duplicate]
I'm currently working on a few turing machine exercises and I can't understand how I can prove whether the below is at least partially decidable:
$\{M \mid L(M) = \{x \mid |x| = 10\}\;\}$ where $|x|$ ...
3
votes
2answers
417 views
Showing that the language $L = \{\langle M, w \rangle\ |\ M$ moves left at least three times while computing $w \}$ is decidable or undecidable
How would you go about showing that the language $L = \{\langle M, w \rangle\ |\ M$ moves left at least three times while computing $w \}$ is decidable or undecidable?
Intuitively my thoughts are ...
1
vote
2answers
86 views
Enumerable disjoint subsets whose union is equal to the union of the sets
I'm given that two sets, $A$ and $B$ are enumerable. I have to show that there exist subsets $A \supset C$ and $B \supset D$ ($C$ and $D$ also enumerable) such that $C$ and $D$ are disjoint and $A\cup ...
12
votes
3answers
2k views
Are there any countable sets that are not computably enumerable?
A set is countable if it has a bijection with the natural numbers, and is computably enumerable (c.e.) if there exists an algorithm that enumerates its members.
Any non-finite computably enumerable ...
3
votes
1answer
241 views
The Church-Turing-Thesis in proofs
Currently I'm trying to understand a proof of the statement:
"A language is semi-decidable if and only if some enumerator enumerates it."
that we did in my lecture. One direction of the proof goes ...
1
vote
0answers
35 views
The set of words accepted by TMs simultaneously is finite is non semi-decidable
Consider $L = \{(M_1,M_2):\text{the set of words accepted by both TM at the same time is finite}\}$. I want to determine if this language is decidable, semi-decidable or not semi-decidable.
My ...
2
votes
1answer
92 views
Semi decidability proof
I'm studying for my theory of computation exam and came accross the following question:
Construct an appropriate Turing machine for the following language and prove or disprove it's semi-decidability:...
7
votes
1answer
3k views
Why is the halting problem semi-decidable?
This is what is know about halting problem and semi-decidability :-
Halting problem says that for a given input x and a machine H, we can't say whether the machine H halts or not on input x.
A ...
1
vote
1answer
113 views
Unrecognizable languages relationship to NP-hard languages
I would like to know if there exists an NP-hard language which is also a member of co-RE\R?
I think it depends if P=NP or not, but i'm not sure.
Can I simply assume NP-hard is in R?
Can you direct ...
0
votes
1answer
300 views
Is it decidable whether a Turing Machine will visit every non-end state from input x?
L = {w#x | w,x ∈{0,1}∗ and Turing Machine Mw with input x visits every non-end state at least once}
I believe this problem is undecidable.
My proof would consist of me reducing L to a Halting ...
2
votes
1answer
248 views
Deciding on decidability of a problem and reducing it to halting problem if not decidable
Given are two following languages:
$L_1 = \{ w\#x \hspace{1mm} | \hspace{1mm} w,x \in \{0, 1\}^* \text{ where } M_w \text{ with input } x \text{ visits each of its states at least once} \}$
$L_2 = ...
1
vote
1answer
424 views
which of the following languages are Recursively Enumerable?
Which of the following languages are recursively enumerable?
A={⟨M⟩∣ TM M accepts at most 2 distinct inputs}
B={⟨M⟩∣ TM M accepts more than 2 distinct inputs}
For first language I think that we can ...
1
vote
1answer
80 views
Recognizability of $\left\{ \left\langle M\right\rangle |M\text{ is a TM and }A_{TM}\leq\mathcal{L}\left(M\right)\right\} $
Determine whether the following language is decidable, recognizable but not decidable, co-recognizable but not decidable or neither recognizable nor co-recognizable. Prove your answer.
$$L=\left\{ \...
0
votes
0answers
96 views
Why is $L=\{\langle M \rangle \mid |L(M)| \geq k\}$ not recognizable?
Here $M$ denotes a turing machine.
By set theory, $L = \overline{E_{TM}} \cap \overline{L_0} \cap \overline{L_1}$ where $L_i=\{\langle M \rangle \mid |L(M)|=i\}$. And I know that $\overline{E_{TM}}$ ...
2
votes
1answer
337 views
Are recursively enumerable languages closed under shuffle?
For languages $L_1, L_2$ over some alphabet $\Sigma$, we define
$$ \textit{Shuffle}(L_1, L_2) = \{a_1b_1a_2b_2 \cdots a_nb_n : n \geq 1 \wedge a_1, \ldots , a_n \in L_1 \setminus \{ \varepsilon \} \...
0
votes
2answers
117 views
Show that RE is closed against right-quotient
I have a problem that I have no idea how to approach. I've been looking at using mapping reductions, but I can't find a way to apply it.
Assume some alphabet $\Sigma$ and two languages $A, B \...
0
votes
1answer
173 views
cardinality of recursive/r.e/not r.e languages? [duplicate]
I was just looking into properties of languages and wondered about the cardinality of them
are all recursive languages countable or can they also be uncountable
(can u have a recursive language which ...
