Questions tagged [semi-decidability]

Questions about which problems are semi-decidable, also known as recognizable or recursively enumerable.

Filter by
Sorted by
Tagged with
1
vote
0answers
31 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
vote
1answer
96 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
votes
1answer
11 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
25 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
25 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 ...
-2
votes
0answers
12 views

Unrestricted grammar for L={wc^id^j}

What is the unrestricted grammar describing this language?
0
votes
1answer
33 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 ...
3
votes
1answer
146 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 ...
2
votes
1answer
66 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 ...
0
votes
1answer
48 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
30 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
100 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
24 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 ...
0
votes
1answer
41 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
votes
2answers
45 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 ...
7
votes
1answer
5k views

Why is the halting problem semi-decidable?

This is what is known about the halting problem and semi-decidability :- The 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. ...
0
votes
1answer
90 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
3answers
193 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
2answers
83 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 ...
2
votes
2answers
77 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
44 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 ...
1
vote
1answer
670 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 ...
0
votes
0answers
32 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 ...
3
votes
3answers
255 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 ...
1
vote
1answer
66 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
376 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 ...
0
votes
1answer
58 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
70 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
345 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 ...
3
votes
1answer
931 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
81 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
182 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
90 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
56 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
48 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 ...
6
votes
2answers
10k 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 ...
3
votes
1answer
72 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 ...
3
votes
1answer
121 views

Complexity of the language of all TMs $M$ such that $L(M)$ is decidable

Let $$R = \{\langle M \rangle \mid L(M) \text{ is decidable}\}.$$ Is $R$ recursively enumerable or co-recursively enumerable?
5
votes
2answers
645 views

Definition of an immune set

I'm reading a theorem about existence of a simple set. The definition of an immune set can be found from here A set ${\displaystyle I\subseteq \mathbb {N} }$ is called immune if ${\displaystyle I}$ ...
2
votes
1answer
1k 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
127 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
325 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
90 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}$ $\...
0
votes
1answer
308 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. ...
1
vote
1answer
137 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
110 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
108 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
244 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!