# Questions tagged [decidability]

The tag has no usage guidance.

10 questions
Filter by
Sorted by
Tagged with
10k views

### A simple decision problem whose decidability is not known

I am preparing for a talk aimed at undergraduate math majors, and as part of it, I am considering discussing the concept of decidability. I want to give an example of a problem that we do not ...
• 11.8k
973 views

### Is it possible to compute whether two functions are extensional equal?

If you have two functions implementing a different sorting algorithm, is it then possible to infer by source code that they both have the same external properties? Meaning that they both will have a ...
798 views

### What notable automaton models have polynomially-decidable containment?

I'm trying to solve a particular problem, and I thought I might be able to solve it using automata theory. I'm wondering, what models of automata have containment decidable in polynomial time? i.e. if ...
• 2,724
1k views

### Does P contain incomprehensible languages? (TCS community wiki)

Answer: not known Many thanks to all who helped refine this question and the definitions associated to it. The definitions of this wiki provided the starting point for the more recent TCS wiki "...
2k views

### Is it decidable to determine if a given shape can tile the plane?

I know that it is undecidable to determine if a set of tiles can tile the plane, a result of Berger using Wang tiles. My question is whether it is also known to be undecidable to determine if a single ...
• 3,703
974 views

### Checking if all products of a set of matrices eventually equal zero

I am interested in the following problem: given integer matrices $A_1,A_2, \ldots, A_k$ decide if every infinite product of these matrices eventually equals the zero matrix. This means exactly what ...
• 775
359 views

### Deciding if a language induced by a Presburger formula is context-free

Is the following problem decidable? Given $n$ and a Presburger arithmetic formula $\phi(x_1,x_2,\dots,x_n)$, determine whether the language $\{a_1^{i_1} \dots a_n^{i_n}:\phi(i_1,i_2,\dots,i_n)\}$ ...
• 1,251
1k views

### Decidability of transcendental numbers

I have a question, whose answer is probably well known, but I can't seem to find anything meaningful after a bit of searching, so I would appreciate some help. My question is whether it is known that ...
• 348
### What is known about $CFL \cap coCFL$?
CFL is the class of context-free languages; co-CFL the languages whose complements are context-free. So CFL $\neq$ co-CFL. Are there any nice characterizations or other basic facts about CFL $\cap$ ...
A set of numbers $S=\{x_1,...,x_n\}$ is said to be algebraically dependent if there exists a (multivariate) polynomial $p$ with coefficients in $\mathbb Q$ whose roots contain $x_1,...,x_n$ (or a ...