# Questions tagged [decidability]

The tag has no usage guidance.

67 questions
Filter by
Sorted by
Tagged with
3k views

### What are the conditions necessary for a programming language to have no undefined behavior?

For context, yesterday I posted Does the first incompleteness theorem imply that any Turing complete programming language must have undefined behavior?. Part of what prompted me to ask that question ...
126 views

### Is the Turing machine the only framework to analyse limits of computation?

In Theory of Computation lessons, the limits of computation are usually analyzed within the framework of Turing machines, so if something isn't solvable with Turing Machine, then we consider this ...
• 359
2k views

### A language is Turing recognizable iff it is a projection of a decidable language

I was wondering how to prove that a language $C$ is Turing-recognizable iff a decidable language $D$ exists such that $C = \{x \mid \exists y \;(\langle x, y\rangle \in D)\}$. I do not know how to ...
• 129
107 views

### Effectively decidable vs. noneffectively (or ineffectively) decidable

The introduction of https://www.sciencedirect.com/science/article/pii/0001870882900482 starts with the following sentence: The word problem for commutative semigroups is effectively decidable. I ...
73 views

### Decidability of {M | M accepts some x in less than |x| steps}

Is this language decidable? {M | M accepts some x in less than |x| steps} It feels like it should be undecidable but I can't think of a good proof that isn't similar to that of Rice's theorem (which I ...
957 views

• 449
1 vote
426 views

### For any two languages A and B there exists J such that both A and B are Turing reducible to J

Here is the my attempt: Proof : Suppose $J = \{aa' \mid a \in A\} \cup \{bb' \mid b \in B\}$ such that $a'$ and $b'$ are the symbols that do not belong to any $w \in A \cup B$ and $a,b$ are strings. ...
1 vote
42 views

### If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?

I was learning about decidability when I thought of this question: If P is partially decidable, is ¬P decidable, partially decidable or undecidable? I think it is Undecidable since if ¬P holds then P ...
1 vote
1k views

### Prove that { $\langle M \rangle$ : $M$ is a TM and $L(M)$ is decidable} is undecidable

So I want to prove that $$\big\{\langle M \rangle : \text{ M is a TM and } L(M) \text{ is decidable} \big\}$$ is undecidable. To do so I want to reduce it from$\ \overline{A_{TM}}$ with a function ...
• 41
1 vote
162 views

### L is a recognizable undecidable language ,M is a Turing machine that recognizes L, does M reject or infinitely loop for s belonging to L-complement?

If $L$ is a decidable language, $M$ is a Turing machine that determines $L$. For $\forall s \in L$, M accepts, and for $\forall s \in \overline{L}$, M rejects However, my question is that If $L$ is a ...
• 315
1 vote
92 views

### Is it computable to find the cardinality of intersection of two recursively enumerable sets?

I am well aware that recursively enumerable sets (which are subsets of $\mathbb N$) are closed under intersection. What is more interesting is whether or not the cardinality of the intersection is ...
• 121
1 vote
256 views

### Decidability for intersection of context free and regular languages

I am wondering if the following are decidable or undecidable and why. L is a CFL and R is a regular language. How does the complement of the context-free language change the decidability of the ...
1 vote
78 views

### Decidability of $\{⟨G⟩ \mid \text{$G$is CFG and$L(G) ⊈ \Sigma^+$}\}$

I want to prove that the following language is decidable: $$\mathit{SEQ}_{\mathit{CFG}} = \{⟨G⟩ \mid \text{G is CFG and L(G) ⊈ L}\}, \text{ where } L = \Sigma^* - \{\epsilon\}$$ So, I think about ...
• 75
1 vote
36 views

### Why we can reduce $A_{TM}$ to $ALL_{CFG}$, but we can not reduce $A_{TM}$ to $E_{CFG}$

If a $PDA$ can be constructed to check whether a string is not a computation history for a Turing Machine. Like in the proof of $ALL_{CFG}$ is not decidable. Then we can construct a $PDA$ that accepts ...
1 vote
50 views

### Reduction from $ALL$ to $DECIDE$

Let $DECIDE=${$<M> :\ M\ halts\ on \ all \ inputs$} and I wish to show its unrecognizable using a reduction from $ALL=${$<M> :L(M)=\Sigma ^*$} using a deterministic turing machine $R$ ...
• 355
1 vote
35 views

### How much is decidability compromised within this restriction of the fixpoint combinator?

Though purely functional programming languages, such as Haskell, is commonly thought to have no side-effects, there is a caveat: Recursive calls may hang. I considered this to be undesirable, and ...
• 367
1 vote
55 views

### Turing-reducibility for guaranteed decider

The following exercise is taken from Theoretical Computer Science by Atiba. Use Rice's theorem to demonstrate that every decidable language is Turing reducible to some language that is already ...
• 11
1 vote
339 views

### A decidable language that can't be decided by a circuit ensemble of linear size

Let Size(O(n)) be the set of languages the can be decided by a circuit ensemble (a sequence of circuits C_i for every natural i s.t input size is i) such that every circuit's size is linear (in input ...
1 vote
55 views

• 355
114 views

### Mapping Reduction from HALT?

I've been given a task to determine whether L={〈M〉|M is a TM that loops on the input c (a constant)} is decidable. I can prove co-L is recognizable so I figured a reduction from HALT to co-L would ...
111 views

### $L =$ { $\langle M \rangle$ | $M$ moves left on at least one input }

Is $L =$ { $\langle M \rangle$ | $M$ moves left on at least one input } decidable? What would the proof look like? Intuitively, I would say it's undecidable: We cannot predict if a given TM ever ...
• 11