Podcast #128: We chat with Kent C Dodds about why he loves React and discuss what life was like in the dark days before Git. Listen now.

Questions tagged [semi-decidability]

The tag has no usage guidance.

20 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3
votes
1answer
111 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
40 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
0answers
163 views

How to prove a Language is neither a Computably enumerable nor Co-Computably enumerable?

What would be the general approach for that? And what are the things that generally overlooked while proving such things? For example, I have a Language, L ={e:$L(M_e)$ such that it accepts only 'a ...
1
vote
2answers
71 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 ...
1
vote
0answers
42 views

The set of words accepted by TMs simultaneously is finite is non semi-decidable

Consider $L = \{(M_1,M_2):\text{the set of words accepted by both TM at the same time is finite}\}$. I want to determine if this language is decidable, semi-decidable or not semi-decidable. My ...
1
vote
0answers
478 views

Showing that $H'$ is not semi-decidable

I have an introductory class in computability theory and I'm currently working on my first exercises. I'm wondering if I'm on the right track with proving undecidable languages. Could you please have ...
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!
0
votes
0answers
31 views

How to know if a lanugae is undecidable or semi-decidable

I recently learnt about undecidable languages and semi-decidable languages. But I am still quite confused on how I can determine if a language is semi-decidable. Is there any standard theorem or axiom ...
0
votes
0answers
31 views

How to prove that for a decidable problem the problem and the compliment of the problem are semi-decidable?

Given a decidable problem, how would I go about proofing that the problem and the complement of the problem have to be semi-decidable?
0
votes
0answers
248 views

Decidability of intersection of two languages of same type

Given two context-sensitive languages, $L_1$ and $L_2$ is the problem of "whether $L_1 \cap L_2$ also belongs to CSL" decidable? I have the same question for the case when $L_1$ and $L_2$ belongs to ...
0
votes
0answers
38 views

Is the language below not decidable , if yes , it is then R.E ?

I am given a Turing machine M as input and i have to find out if this language below decidable and if not is it then in this case recursively enumerable . $$L=\\\{<M> \mid \text{ is ...
0
votes
0answers
169 views

Turing machine accepts two different strings

I am having hard time to proving this problem $C=\{\langle M \rangle \mid M \text{ is a Turing Machine , } L(M) \text { only contains two different strings}\}$ some ideas that i have tried are : i ...
0
votes
0answers
85 views

Decidability of {(M,w); M terminates on input w and tape of M is empty after computation}

I am currently trying to prove whether the above language is decidable, partially decidable or fully undecidable. I am certain that this language is partially decidable and reducible to the halting ...
0
votes
0answers
113 views

Why is $L=\{\langle M \rangle \mid |L(M)| \geq k\}$ not recognizable?

Here $M$ denotes a turing machine. By set theory, $L = \overline{E_{TM}} \cap \overline{L_0} \cap \overline{L_1}$ where $L_i=\{\langle M \rangle \mid |L(M)|=i\}$. And I know that $\overline{E_{TM}}$ ...
0
votes
0answers
53 views

Is undecidability of TMs' properties a statistical statement?

We know (by Rice's theorem) that is it not possible to decide a non-trivial property of a given TM. We could say therefore that we cannot be sure at 100 percent that a given TM has a certain non-...
0
votes
0answers
64 views

how to prove that the property 'doesn't halt for some input' is not semidecidable

I am taking a computer theory class and one of the exercises is to prove that the property "doesn't halt for some input" is not semidecidable. This property is the negation of the property "halts for ...
0
votes
0answers
47 views

Decidability of $\{p|∃y : \operatorname{Dom}(φ p ) ⊇ \operatorname{Dom}(φ y )\}$

I need to classify the set $$\{p|∃y : \operatorname{Dom}(φ p ) ⊇ \operatorname{Dom}(φ y )\}$$ as decidable, semidecidable or not semidecidable. I don't know how to start. Any ideas? Dom (φp) it's ...
0
votes
0answers
94 views

Are there any RE-complete languages w.r.t. polynomial reduction?

I need to decide if there exists $L\in RE$ so that for every $L'\in RE$ we have $L' \leqslant_p L $, meaning a polynomial-time reduction. I've tried to use $L=A_{TM}$ (the accepting problem), but got ...
-1
votes
2answers
81 views

Relation between sets and partially computable functions

I encountered this problem. Let $A$ , $B$ , $C$ be disjoint sets $(A\cap B = B\cap C = A\cap C = \emptyset)$. The $f_1, f_2$ and $f_3$ are partially computable functions that are defined as follow:...
-2
votes
1answer
34 views

Show that $L = L_\phi \cup L_{\{\sum^*\}} \notin RE$ with Rice theorem

Show that $L = L_\phi \cup L_{\{\sum^*\}} \notin RE$ with Rice theorem. Well I did show that with reduction, by using $HP'$. Simply by creating a function from $f(\langle M \rangle, x) = (M')$ Thus,...