Questions tagged [semi-decidability]
Questions about which problems are semi-decidable, also known as recognizable or recursively enumerable.
190
questions
1
vote
2answers
223 views
is there a constructive proof of the existence of a language which isn't recursive (without invoking infinities)?
My understanding is that a language cannot be decided if the language is actually infinite (not generated by any machine). However, actual infinites make me squirm. Is there any reason to believe in ...
3
votes
1answer
56 views
Characterization of computationally universal functions
Is it correct to state that $u$ is a universal function if and only if
$$
\forall f : \text{RE} \quad
\exists g : \text{R} \quad
\exists h : \text{R} \quad
f = h \circ u \circ g
$$
where RE is the set ...
2
votes
2answers
189 views
Showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable
How would you go about showing that the language L={⟨M,w⟩ | M moves its head in every step while computing w} is decidable or undecidable?
Intuitively speaking I think it is indeed undecidable because ...
0
votes
1answer
35 views
Understanding the union of an undecidable language with a finite or decidable language
I'm trying to prove that the language $L \cup A$ is undecidable, when the language $L$ is undecidable and the language $A$ is finite or decidable.
This is confusing me because if $L$ were to be a semi-...
0
votes
1answer
27 views
Some questions regarding decidability and semi-decidability of $A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$
I have found two interesting questions regarding the quotient of languages, described as:
$A/B = \{ w \text{ | }\exists z \in B, wz \in A\}$
The first one is:
Let $A$ and $B$ be regular languages, ...
0
votes
1answer
69 views
How this language belong to R?
Consider the following language $$L= \{ \langle M\rangle | \text{ $M$ is a TM, and $L(M)\in coRE$} \}$$
I don't understand why the language $L$ is in $R$, intuitively, I think this is not true. ...
-1
votes
1answer
42 views
How to show a language is Partially Decidable?
I am trying to solve some questions on partial decidability of languages and I am getting confused in how to construct proper arguments through the idea of Universal Turing Machine.
I am not posting ...
1
vote
1answer
25 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
1answer
173 views
Determine if a language is Decidable or semi decidable
Consider the language $L = \{\langle M \rangle: \text{ $M$ accepts at most two single-letter words}\}$, where $\langle M\rangle$ is the encoding of Turing machine $M$.
We need to determine, without ...
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
65 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
58 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
54 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 ...
1
vote
0answers
40 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
39 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
40 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
15 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
97 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
40 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
54 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
68 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
59 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
109 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
125 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
27 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
169 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
59 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
83 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, ...
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
237 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
2k 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
412 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
117 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
106 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
70 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
94 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
848 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
2k 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
99 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
301 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
194 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
61 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
117 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
76 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
94 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
3k 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
160 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
509 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
207 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
275 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 ...
