# Questions tagged [undecidability]

Questions about problems which cannot be solved by any Turing machine.

689 questions
Filter by
Sorted by
Tagged with
16 views

### CFG that generates $1^*$ is decidable

I read somewhere that the problem which asks whether or not a $CFG$ $G$ generates $1^*$ is decidable. The proof goes like this: $1^* \cap G$ is context free since it is the intersection of a regular ...
34 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 ...
25 views

### Is the emptiness of intersection of two CFLs decidable? [duplicate]

Consider $L = \{\langle L_1, L_2\rangle\mid L_1, L_2 \in \text{CFL} \text{ and } L_1 \cap L_2 = \emptyset \}$. How to prove that $L \notin R$? $L_1, L_2$ encoded in chomsky-normal-form.
11 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 ?
19 views

45 views

### Decidability of equality, and soundness of expressions involving elementary arithmetic and exponentials

Let's have expressions that are composed of elements of $\mathbb N$ and a limited set of binary operations {$+,\times,-,/$} and functions {$\exp, \ln$}. The expressions are always well-formed and form ...
30 views

### Is the undecidability of a given problem undecidable?

Given an input problem P, can you construct an algorithm A to compute whether or not P is decidable or undecidable? In other words, is the undecidabiliy of a problem undecidable? My initial guess is ...
2k views

### Halting problem theory vs. practice

It is often asserted that the halting problem is undecidable. And proving it is indeed trivial. But that only applies to an arbitrary program. Has there been any study regarding classes of programs ...
36 views

Let TOT be the set of all Turing Machines that halt on all inputs. Find a computable set B of ordered triples such that: TOT = {e : ($\forall$x)($\exists$y)[(e, x, y) $\in$ B] This definition means ...
43 views

### How could you “solve” the halting problem if, hypothetically, the busy beaver numbers were “small”?

I read that if BB(n) did not grow faster than all computable sequences of integers, you could solve the halting problem and contradict Turing's theorem. I'm trying to figure out how you could ...
49 views

### What does “Every CFL is decidable” exactly mean?

I am trying to prove the fact that every CFL is decidable, however I can't come to terms with what the statement exactly means. I know that generation of a particular string by a given CFG is a ...
17 views

### Mapping reduction from $A_{TM}$ to $INFINITE_{TM}$ same as to $ALL_{TM}$?

I was trying to solve a problem with a mapping reduction from $A_{TM}$ to $INFINITE_{TM}$, and came across a solution that was 100% identical to another solution I saw for $A_{TM} \leq_M ALL_{TM}$. ...
77 views

### Turing machine on input w tries to move its head past the left end of the tape

Consider the language $$L = \{ \langle M,w \rangle \mid \text{M on input w tries to move its head past the left end of the tape}\}.$$ Prove whether L is decidable or not. I tried to prove ...
61 views

### Turing machines moving left at least once

Is the following language decidable? $$L = \{ \langle M,w \rangle \mid \text{M moves its head left at least once when run on w}\}.$$ I feel like this is a decidable language. But I don't know ...
61 views

### Is there a language that cannot be polynomially reduced to?

Is there a language A that cannot be polynomially reduced to by some language B? Or is it always possible to reduce a language B to A?
74 views

### Difference between regular grammar and CFG in generating computation histories and $\Sigma^*$

I would like to ask for intuition to understand the difference between a CFG generating $\Sigma^*$ and a regular grammar generating $\Sigma^*$.. I got the examples here from Sipser. Let $ALL_{CFG}$ ...
19 views

### Is it semidecidable to test whether a Turing decidable language is empty?

I'm not sure how to go about solving this. I tried this: Suppose L is a Turing decidable language. Turing Machine M1 is a decider of L and M2 is a decider of the complement L We construct a TM U ...
43 views

### Is it decidable for a NPDA to halt?

I know that it is decidable for an NPDA to accept a string $w$, i.e. a TM can receive as input the description of an NPDA along with a string and test if the NPDA accepts the string. But are there ...
31 views

### Is it decidable to know the number of positions used by a Turing machine for a fixed input?

I'm having trouble proving if the following language is recursive, recursively enumerable, or not r.e. at all: the set of all encodings of Turing machines $M$ such that the number of positions in the ...
29 views

### How does a PDA compare two configurations of accepting histories?

In Michael Sipser's book, they prove that ALL_CFG is undecidable using accepting computation histories and PDAs. My question is how exactly (with details of implementation) a PDA goes on to compare ...
36 views

255 views

### show that in every infinite computably enumerable set, there exists an infinite decidable set

I came across this problem: Show that in every infinite computably enumerable set, there exists an infinite decidable set. As an attempt to solve the problem, I could only think of a proof by ...
350 views

### Why doesn't the recursion theorem prove there is an undecidable finite set?

I created something similar to Sipser's proof for the undecidability of $A_{TM}$ (theorem 6.5), "proving" the undecidability of a set that must be finite. Presumably, it's wrong, but I can't ...