# Questions tagged [undecidability]

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

780 questions
Filter by
Sorted by
Tagged with
183 views

### What is a list of "reasonable but undecidable" theorems?

There are some theorems that go along the lines of "all reasonable properties of <math subject> are computationally undecidable." Here are two examples: Rice's Theorem: "all ...
118 views

### How would I prove that nondeterministic Turing machines are undecidable?

How would I go about proving that the language: $$A_{NTM }= \{\langle N, w\rangle | N \text{ is a nondeterministic TM and } N \text{ accepts }w\}$$ is undecidable? I looked at the proof for $A_{TM}$ ...
337 views

### Decidability of a problem concerning polynomials

I have come across the following interesting problem: let $p,q$ be polynomials over the field of real numbers, and let us suppose that their coefficients are all integer (that is, there is a finite ...
151 views

### is it decidable whether a grammar in Chomsky normal form has useless rules?

Given a context-free grammar in Chomsky normal form, is it decidable whether that grammar has any useless rules? By "useless", I mean a rule that can be omitted from the grammar without ...
356 views

### Undecidability of "is this CFG prefix-free?"

I'm having difficulty proving undecidability of "is this CFG prefix-free?". (this proof is given as problem 5.32b in Sipser 3rd edition). Another thread has the very different question "...
521 views

### Decidability of dependent typing on primitive recursive languages

With a dependent type system in a normal functional language type checking may never halt. This is partially because dependent typing removes the isolation between types, and code. My question is this:...
78 views

172 views

### How to decide whether a language is decidable when not involving turing machines?

For instance, consider L = {k : the binary expansion of sqrt(2) contains k consecutive 1s}. Obviously Rice Theorem would not work. I also tried the method of how it is to PCP undecidable but still no ...
134 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?
109 views

### Is a 'discrete language' well-defined?

Are the following well-defined formal languages (in these cases: subsets of {0,1}*) ? An argument w is a member of L under the following rules... Example1: If more than half of w's digits are 1's --...
53 views

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