Questions tagged [semi-decidability]

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

196 questions
Filter by
Sorted by
Tagged with
5k 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....
5k 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, ...
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. ...
4k 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, ...
12k 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 ...
3k 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 ...
609 views

A non-mechanical way to get an infinite decidable subset of a Turing-recognizable language?

There's a famous theorem that every infinite Turing-recognizable language has an infinite decidable subset. The standard proof of this result works by constructing an enumerator for the Turing-...
754 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}$ ...
83 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-recursively ...
11k views

Why is the class of recursively enumerable languages not closed under complementation?

I am having a hard time understanding closure properties of recrusively enumerable languages. I have read the explanation on this site but still unable to fully understand why they are not closed ...
386 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 ...
237 views

3k views

Is the Rice Theorem applicable for these problems?

I have 1 problem :--> L = { < M > | TM halts on no inputs } I have solved the above problems by reductions given in the book and even there are many links ...
1k 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 ...
248 views

Is $AlwaysHalt$ recursively enumerable?

I was doing some complexity theory exercices and I came over this one: $AlwaysHalt = \{R(M) | M$ halts with all $x \in \{0,1\}^*\}$ Is $AlwaysHalt$ recursively enumerable? I would say YES and ...
206 views

Is the set of programs that compute some function other than $h$ recursively enumerable?

Let $h$ be a total computable function. Is $S = \{x \mid f_x \neq h\}$ recursively enumerable? Originally this was an exercise that restricted $h$ to: $h(x) = x + 1$ . However, it can be formulated ...
1k views

Mapping reducibility vs. Turing reducibility

Let $A$ and $B$ be two languages. If $A \le_{m} B$ ( reducible by mapping ) then I know that if $B$ is decidable so is $A$ and if $B$ is recognizable so is $A$. And if $A \le_{T} B$, then if $B$ is ...
812 views

Is the difference of a non-recursive and recursive set recursive?

I have two sets B which is recursively enumerable and is not recursive, and A which is recursive. Is $A-B$ recursive and / or recursively enumerable? What about $B-A$? $B-A$ is obviously recursively ...
6k views

Can you recognize or decide if a Turing Machine has an infinite sized language?

That is, can you build a Turing Machine that, if given a Turing Machine as input, can decide (or at least recognize) if the inputted Turing Machine has an infinite number of strings in its language? ...
647 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 ...
656 views

Is the language of TMs that decide some language Turing-recognizable?

Is the language $\qquad L=\{ \langle \text{M} \rangle \; | \; \text{M is a Turing machine that decides some language} \}$ a Turing-recognizable language? I think it's not, as, even if I am able ...
3k views

Dovetailing in Turing Machines?

I was going through TM here and encountered a term "Dovetailing". What is exactly the dovetailing in Turing Machines? Can anyone mind to provide a good explaination with some examples?
421 views

set of Kolmogorov-random strings is co-re

given RC = {x : C(x) ≥ |x|} is a set of Kolmogorov-random strings. How can I show that RC is co-re I have been reading this paper What Can be Efficiently Reduced to the Kolmogorov-Random Strings?...
490 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 ...
842 views

Partial recursive function with no total recursive extension

We define a partial recursive function $f:\{0,1\}^* \longrightarrow \{0,1\}^*$ to be semi-good if we can define a total recursive function $g:\{0,1\}^* \longrightarrow \{0,1\}^*$ from $f$, such for ...
1k views

Is Post's correspondence problem recognizable?

I want to know whether Post Correspondence Problem (PCP) is recognizable. I learnt how to demonstrate the undecidability of PCP. I thought to use the similar approach for recognizability too i.e. to ...
324 views

The Church-Turing-Thesis in proofs

Currently I'm trying to understand a proof of the statement: "A language is semi-decidable if and only if some enumerator enumerates it." that we did in my lecture. One direction of the proof goes ...
1k views

Symmetric Difference of Turing Recognizable and Finite Languages

Let A be a Turing Recognizable Language and B a finite Language. I want to prove that their symmetric difference is Turing Recognizable. My reasoning: B is finite, therefore the finite number of ...
2k views

Is regularity of the language accepted by a given Turing machine a semi-decidable property?

Given is the definition of a general problem: $\{ \langle M, S\rangle \mid M \text{ is a } TM, L_M \in S\}$. In words: Given a TM M, does M decide a language that is an element of the given set of ...
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) {...
73 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'...
148 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 ...
62 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 ...
87 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 ...
1k 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 ...
143 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?
528 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 ...
190 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 ...
340 views

475 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 ...