# Questions tagged [semi-decidability]

The tag has no usage guidance.

163 questions
Filter by
Sorted by
Tagged with
4k views

### Why are the total functions not enumerable?

We learned about the concept of enumerations of functions. In practice, they correspond to programming languages. In a passing remark, the professor mentioned that the class of all total functions (i....
3k 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 ...
2k views

### undecidable problem and its negation is undecidable

A lot of "famous" undecidable problems are nonetheless at least semidecidable, with their complement being undecidable. One example above all can be the halting problem and its complement. However, ...
4k 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 ...
2k views

### Is it possible for a language and its complement to both be unrecognizable?

Given some unrecognizable language $L$, is it possible for its complement $\overline{L}$ to also be unrecognizable? If some other language $S$ and its complement $\overline{S}$ are both recognizable, ...
9k 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 ...
2k views

### Reduction from ATM to ATM-complement

Is there a reduction from ATM to ATM-complement? (ATM denotes the language $\{\langle M,w \rangle \mid \text{TM$M$accepts$w$}\}$) I have been thinking about it too much and couldn't find the ...
508 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 $I\subseteq \mathbb {N}$ is called immune if $I$ ...
81 views

### Show that the set of programs whose Kolmorgorov complexity is smaller than their length is recursively enumerable

Define the language $\qquad R = \{x \in \{0,1\}^\ast \mid C(x) \ge |x| \}$ where $C(x)$ is the Kolmorgorov Complexity of $x$ and $|x|$ denotes the length of $x$. Prove that $R$ is co-...
174 views

### Language of TMs that accept some x in less than 50 steps. Is it in co-RE?

L = {M | M is a TM and there exists an input that the TM M accepts in less than 50 steps} I need to find a minimal class it belongs to between R/ RE/ co-RE/ not in RE∪co-RE. I managed to show that ...
229 views

164 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) {...
51 views

### Why is it true that the relation R and its negation are not semi decidable?

An example given for a relation R where its negation and itself are not semi-decidable was: $R(x,y)$ holds iff $y = 0$ then $R_{HALT}(x)$ holds, otherwise $y = 1$ and $R_{HALT}(x)$ does not hold. It'...
63 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 ...
564 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 ...
120 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?
425 views

### The Hindley-Milner type system plus polymorphic recursion is undecidable or semidecidable?

I have often read that Hindley-Milner extended to allow polymorphic recursion is undecidable. However is the term used what is actually meant? Or do people actually mean semidecidable when they ...
113 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 ...
462 views

### Is English Recursively enumerable? [closed]

The title says it all. I've tried digging up debate on this issue to see a proof one way or the other but it doesn't look like anyone is able to say whether or not it is. Clearly there are recursive ...
This statement is Theorem 1.1 (page 39) of Computability, Complexity and languages by Martin Davis: If function $h$ is obtained from the (partially) computable functions $f$, $g_1$, $g_2$, ..., $... 2answers 4k views ### Is the language TMs that accept finite languages Turing-recognizable? I know that$L=\{ \langle M \rangle \mid |L(M)| < \infty \}$is not decidable (by Rice's theorem or using reduction, I followed it from$L$not being decidable ). But is$L$recognizable? What I ... 1answer 212 views ### What is the meaning of undecidability in Rice Theorem? Rice theorem says every non-trivial property of languages of Turing machines is undecidable. what is the meaning of undecidability here? is it semi-decidable? As an example the following language is ... 1answer 582 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$\}$... 1answer 51 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 ... 1answer 110 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 ... 2answers 390 views ### will this be decidable or partially decidable?$A=\{\langle M \rangle \mid M \text{ is a turing machine and }|L(M)|\geq3\}$Since Recursive enumerable languages are turing enumerable, so listing of all strings of the language in finite time is ... 1answer 289 views ### Is w ∈ L(M ) ⟹ ww ∈ L(M) co-semi-decidable? Consider the following langugage:$\qquad L = \{ \langle M \rangle \mid M \text{ TM}, w \in L(M) \implies ww \in L(M)\}$. I've been asked to decide whether this language is in R/RE/CO-RE. I've ... 1answer 104 views ### Is there a class of formal grammars that generate Recursive Languages only? Is there a class of formal grammars that generate Recursive Languages only? (ie with which it is not possible to generate non recursive languages.) If so what kind of production rules/restrictions do ... 1answer 1k views ### Is there C++ code that takes infinite time to compile? Is C++ as a formal language recursively enumerable? If yes, is there any invalid C++ code that takes "infinite" time to compile? 2answers 137 views ### Language of TMs such that one state is visited most often To be safe, let me start this question by giving the definition of a TM I will be using: A TM is some$M = (Q, \Sigma, \Gamma, q_0, \delta, q_F)$, where$Q$is the finite state set,$\Sigma \subset \...
I'm given the set $T = \{\langle M, w\rangle : M$ is a Turing Machine that accepts $w^\mathcal R$ whenever it accepts $w \}$ and I want to show it's undecidable but recognizable. (I'm using the ...