The decidability tag has no wiki summary.
2
votes
1answer
140 views
Is meta-undecidability possible?
There are problems that are decidable, there are some that are undecidable, there is semidecidability, etc.
In this case I wonder whether a problem can be meta-undecidable. This means (at least in my ...
4
votes
0answers
99 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)\}$ ...
16
votes
3answers
546 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 ...
-1
votes
0answers
62 views
Undecidability of whether a given TM has only mechanically detectable loops or always halts [migrated]
This might be a bit of an abstruse question, but it's something I've been trying to prove.
I'm trying to show that it is undecidable whether a given Turing Machine is a member of the set of all ...
7
votes
1answer
714 views
Do natural generalizations of P versus NP exist?
Accepted Answer
Scott Aaronson's answer has been "accepted" (mainly because it's the only answer!)
One-sentence summary of answer Plausibly natural generalizations of the P versus NP question ...
1
vote
0answers
83 views
Non-uniform CFG ambiguity decidability
The uniform version (the version which we normally see) of deciding whether a CFG (Context Free Grammar) is ambiguous is undecidable. But here I'd like to know something about the non-uniform version ...
7
votes
1answer
310 views
Does every Turing-recognizable undecidable language have a NP-complete subset?
Does every Turing-recognizable undecidable language have a NP-complete subset?
The question could be seen as a stronger version of the fact that every infinite Turing-recognizable language has an ...
14
votes
2answers
217 views
Is it possible to decide $\beta$-equivalence within System F (or another normalizing typed λ-calculus)?
I know that's impossible to decide $\beta$-equivalence for untyped lambda calculus. Quoting Barendregt, H. P. The Lambda Calculus: Its Syntax and Semantics. North Holland, Amsterdam (1984).:
If A ...
3
votes
3answers
193 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 ...
5
votes
1answer
205 views
Random walk returning probability
Consider a two-dimensional random walk, but this time the probabilities are not $1/4$, but some values $p_1, p_2, p_3, p_4$ with $\sum_{i=1}^4 p_i=1$. For example, from $(0,0)$, it goes to $(1,0)$ ...
9
votes
3answers
922 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 ...
