# Questions tagged [semi-decidability]

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

193 questions
Filter by
Sorted by
Tagged with
1answer
29 views

### Decidability of languages with dfa/turing-machines

For any alphabet and any natural number k, a language of strings at least k is decidable. So my question is having some alphabet (let's say (0,1)) and some number let's say k=5 then my language has ...
1answer
58 views

### How to prove (un)decidability

Let's say we have a string s , a code size limit of b bytes and a time limit t, the question is then whether or not it is possible to construct an algorithm that prints the string within the time ...
3answers
187 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 ...
1answer
259 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 ...
1answer
26 views

### TM with double-infinity tape semi-decides the same languages as classical TM

Show that a Turingmachine with tapes that are infinite in both directions semi-decides the same languages as a classical TM. Apart from the entry-word, the tapes are filled with empty spaces and the ...
1answer
176 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 ...
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 ...
1answer
197 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 ...
4answers
944 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 ...
1answer
57 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 ...
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. ...
1answer
48 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-...
2answers
202 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 ...
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, ...
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 ...
1answer
244 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'...
1answer
53 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 ...
1answer
68 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 ...
0answers
21 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?
1answer
62 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 ...
1answer
64 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 ...
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 ...
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 ...
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$-...
1answer
62 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 ...
0answers
41 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 ...
1answer
143 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 ...
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 ?
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 ...
1answer
42 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 ...
1answer
58 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 ...
1answer
89 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-...
1answer
112 views

1answer
358 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 ...