Questions tagged [semi-decidability]
Questions about which problems are semi-decidable, also known as recognizable or recursively enumerable.
184
questions
1
vote
1answer
10 views
Showing semidecidability without using diagonalization
All the methods I know which shows a given language $L$ is $RE$ but note $REC$ deep down boils down to the cantor's diagonalization arguement in one way or the other, and most commonly it boils down ...
0
votes
0answers
22 views
Determine if a language is Decidable or semi decidable
Let L = {<M> | M accepts at most two single-letter strings}
Here <M> is an encoding of a Turing machine M = (....) as a string.
Need to determine without using rice theorem. whether this ...
0
votes
0answers
20 views
Can you build a solver for a language from a solver for its complement?
If you have a solver for an L in NP do you have enough information to build a solver for co-L in Co-NP? Meaning, is there a procedure that can take you from a solver for one to a solver for another?
1
vote
1answer
57 views
How to show ambiguous context-free grammars in Chomsky normal form is Turing recognizable?
So this question has two questions and i have to use the answer from 1 to answer question 2. Assuming that my answer for 1 is good. I need help with 2. ( Correct me if wrong please.)
Question 1 :
Show ...
2
votes
1answer
53 views
Can you build a solver from a verifier?
Given code to just an NP-verifier, where the certificate/witness is required to be of size polynomial in the instance, for a language L, can you, from that data alone, construct code for a solver, or ...
0
votes
1answer
52 views
Is $\{w~|~\forall x \in T(M_v):|w|>|x|~\}$ decidable?
I want to ask if $\{w|\forall x\in T(M_v):|w|>|x|\}$ is decidable if v is a Index of a random but fixed Turing Machine with $|T(M_v)|<\infty$.
My idea:
It is co-semi-decidable since as soon as i ...
0
votes
0answers
31 views
Decidability for $ \exists w´, w´´\in L:$ so that |w´´| - |w´| is prime
I tried to decide wheter the given Language $ L = \{ \langle M \rangle | M \space is \space TM \space and \space \exists \space w´,w´´\in L(M):|w´´|-|w´| \space is \space prime \} $ is recursive or ...
1
vote
0answers
38 views
k-limited solution for PCP
So there's following problem, that has been bugging me for the last few days:
A solution of a PCP $ i_{1},\dots,i_{n}$ with the cards $(x_{1} ,y_{1}),\dots,(x_{m}, y_{m})$ is considered as $k$-...
1
vote
0answers
38 views
How to show that these two disjoint sets $A$ and $B$ exist
I came across this problem which asks to show the existence of two disjoint Turing-recognizable sets $A$ and $B$ such that no decidable set $C$ can separate them...
In this case, a set $C$ is said to ...
-1
votes
1answer
14 views
Is the Languague which contains all TMs which write the blank symbol at firs by the given input w decidable?
Consider the problem of determining whether a Turing machine M on an input w writes the blank symbol at first. Is this decidable ?
0
votes
1answer
57 views
Show that for every language there exists a harder language
I came across this problem that I could not figure out... For every language $A$, there is supposed to be a language $B$ such that:
$$
A \leq_T B
$$
but:
$$
B \not \leq_T A
$$
If it is $A \leq_TB$ and ...
0
votes
1answer
37 views
Is $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} (un-)decidable?
I have to prove that the language $L_2:=${$<M>$|$L(M)=\overline{A_TM}$} is (un-)decidable. In a previous assignment we proved that $L_1:=${$<M>$|$L(M)=A_TM$} is undecidable.
I would say ...
-1
votes
1answer
47 views
Decide if a string is a member of a language that represents $P$?
For some enumeration of the complexity class P (such as this as an example: How does an enumerator for machines for languages work?), for each string 𝑝 in the enumeration, does there exist some other ...
0
votes
1answer
58 views
How to prove semi-decidable = verifiable?
A language L is verifiable iff there is a two-place predicate R ⊆ Σ∗ × Σ∗ such that R is computable, and such that for all x ∈ Σ∗: x ∈ L ⇔ there exists y such that R(x, y)
A language is semi-...
0
votes
1answer
49 views
Semi-decidability of the language $\overline{L_{\epsilon}}$
Firstly consider the problem: given $L_H = \{R(M)w : M \in TM_0, w\in L(M)\}$ where $R(M)$ are encoded transitions of $M \in TM_0$. Assume for contradiction $\overline{L_{H}}$ is semi-decidable, then ...
0
votes
1answer
105 views
“problematic” non-halting inputs for Turing machines
Let us start this question out, by defining for a Turing machine, the set of words it doesn't halt on.
Define: $P(M)=\{w\in\Sigma^*|M$ doesn't halt on $w \}$
We know that the $HALT$ problem is $RE\...
1
vote
1answer
107 views
Check if language is decidable
I would like to determine if the following language is decidable or not.
L = { w $\in$ $\Sigma^*$ | $T(M_w)$ is recognized by a Turing machine with at most 42 states}.
I know that every finite ...
1
vote
1answer
25 views
Is reaching in less lines semi-decidable?
Assuming we have two programs $p_1$ and $p_2$ and two line numbers $n_1$ and $n_2$. Does $p_1$ reach $n_1$ in less computational steps than $p_2$ reaches $n_2$? By reduction from Halting, this is ...
-1
votes
2answers
124 views
Is determining if a Turing Machine stops for at least one entry decidable?
I can't find how to prove the decibility with a reduction.
EDIT:
I've tried the reduction from the halting problem and the aceptance problem. Stopping for at least one entry has infinite inputs (you ...
-1
votes
1answer
54 views
Prove that a language is decidable
I need some help to prove that the language is decidable.
$K$ = {$N$ : $N$ is a DFA (Sigma = {a, b, c}) and $L$($N$) contains at least one word in which there is no a}.
It tried to make an algorithm ...
1
vote
1answer
53 views
Union of halting-like problem and non-halting-like problem
I came across the following problem:
Define languages $L_0$ and $L_1$ as follows :
$L_0=\{⟨M,w,0⟩∣M\text{ halts on }w\}$
$L_1=\{⟨M,w,1⟩∣M\text{ does not halt on }w\}$
Here $⟨M,w,i⟩$ is a triplet, ...
1
vote
0answers
21 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
36 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
150 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'...
2
votes
1answer
1k 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
341 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
2answers
93 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
84 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
65 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
79 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
651 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
1k 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
89 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
250 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
149 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
58 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
70 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
74 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
71 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 ...
2
votes
1answer
2k 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
133 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
437 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
150 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}$ $\...
-2
votes
3answers
236 views
Does undecidability violate Turing completeness? Shouldn't “complete” include “decidability”/convergence? [closed]
Does undecidability violate Turing completeness? Shouldn't "complete" include "decidability"?
The halting problem:
The halting problem is a decision problem about properties of computer
programs ...
1
vote
1answer
149 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
122 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
128 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 ...
2
votes
2answers
327 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
152 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 ...
