# Tag Info

98

The Matrix Mortality Problem for 2x2 matrices. I.e., given a finite list of 2x2 integer matrices M1,...,Mk, can the Mi's be multiplied in any order (with arbitrarily many repetitions) to produce the all-0 matrix? (The 3x3 case is known to be undecidable. The 1x1 case, of course, is decidable.)

61

UPDATE: The problem I mentioned here is now known to be undecidable! http://arxiv.org/abs/1605.05274 Moreover, the paper was inspired by reading this very answer. :) Programmers in your math-major audience may be surprised to learn that the question "is this type implicitly convertible to that type?" is not known to be decidable in any of Java 5, C# 4 and ...

50

Hilbert's tenth problem over rationals: "Does this polynomial equation have a rational solution?"

31

The problem of given a linear recurrence along with its initial values, does it take the value 0? Two reference: http://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/ http://www.cs.ox.ac.uk/joel.ouaknine/publications/positivity12.pdf

30

A fairly natural and studied variation is the Tape-Reversal Bounded Turing machine (the number of tape-reversals are bounded); see for example: Juris Hartmanis: Tape-Reversal Bounded Turing Machine Computations. J. Comput. Syst. Sci. 2(2): 117-135 (1968) Edit: [this variation is more artificial] the halting problem is decidable for a Non-erasing Turing ...

25

A simple problem whose decidability is unknown is the following (I think it is still open): Infinite chess: Input: A finite list of chess pieces and their starting positions on a $Z \times Z$ chessboard; Question: Can White force mate? If we add the constraint that White must mate in $n$ moves ($n$ is part of the input), then it becomes decidable: see Dan ...

23

According to the introduction of [1], The complexity of determining if a single polyomino tiles the plane remains open [2,3], and There is an undecidability proof for sets of 5 polyominoes [4]. [1] Stefan Langerman, Andrew Winslow. A Quasilinear-Time Algorithm for Tiling the Plane Isohedrally with a Polyomino. ArXiv e-prints, 2015. arXiv:1507.02762 [cs.CG] ...

21

No, it's not possible. Consider the following two inhabitants of the type $(A \to B) \to (A \to B)$. $$\begin{array}{l} M = \lambda f.\;f \\ N = \lambda f.\;\lambda a.\; f\;a \end{array}$$ These are distinct $\beta$-normal forms, but cannot be distinguished by a lambda-term, since $N$ is an $\eta$-expansion of $M$, and $\eta$-expansion preserves ...

21

No. Turing-recognizable undecidable languages can be unary (define $x \not\in L$ unless $x = 0000\ldots 0$, so the only difficult strings are composed solely of 0's). Mahaney's theorem says that no unary language can be NP-complete unless P=NP.

20

Collatz Problem is simple-to-describe problem whose decidability is open. It involves a simple recurrence of elementary arithmetic operations. $f(n)=\mathsf{\{}$ $n/2$ for even integer, $3n+1$ for odd integer The problem is deciding whether iterating this function always return to 1 for a given positive integer $n_0$. Interestingly, a generalization ...

19

It is unknown whether or not it is decidable to determine if a given shape can tile the plane, even for polyomino tiles.                     (Image from Wikipedia.)

18

Considering how parameter passing to subroutines and a huge part of memory management in mainstream computer languages is stack based, an obvious and natural variation is to restrict the unbounded memory of a Turing machine to be a stack. Such a model has nice properties, in addition to halting being decidable (well known for PDAs): The notion of a PDA ...

17

The decidability of conjunctive query containment has been open for over twenty years. Resolving this would be a breakthrough in database theory. Query containment takes as input two queries $Q_1$ and $Q_2$ and asks whether $Q_1$ applied to any database $I$ yields at least as many answers as $Q_2$ when applied to the same database $I$. In conjunctive ...

17

Post's Correspondence problem with a fixed number of tiles of between 3 and 6. While it is not really simple to describe, it does have a very "playful" description, and I find it suitable for intuition-level talks.

17

Your question is equivalent to whether $A_1, \dotsc, A_k$ generate a nilpotent algebra, which in turn is equivalent to each of the $A_i$ being nilpotent. Hence not only is it decidable, but in $\tilde O(n^{2 \omega})$ time where $\omega$ is the exponent of matrix multiplication. Let $\mathcal{A}$ be the associative algebra generated by the $A_i$: that is, ...

15

John, while your kind comments are appreciated, I confess that I don't understand how your question relates to the simple point I was making in the quoted remark. All I was saying was that we do know various separations between complexity classes, like P≠EXP, MAEXP⊄P/poly, NEXP⊄ACC, etc. So, if you believe that a particular separation, like P&...

15

Probably you already got these in your bag :-) Two way one counter machine over unary alphabet (Minsky61). Two way weak counter machines (the counter has no effect on the computation but the machine halts if counter reaches zero) [1]. Quantum one counter automata [2]. With binary alphabets, the emptiness remains undecidable for: One way machines with one ...

15

Visibly pushdown automata (or nested word automata, if you prefer working with nested words instead of finite words) extend the expressive power of deterministic finite automata: the class of regular languages is strictly contained within the class of visibly pushdown languages. For deterministic visibly pushdown automata, the language inclusion problem can ...

14

If infinite words are in your scope, you can generalize DFA (with parity condition) to the so-called Good-for-Games automata (GFG), that still have polynomial containment. A NFA is GFG if there is a strategy $\sigma:A^*\times Q\times A\to \Delta$, that given the prefix read so far and the current state and letter, chooses a transition to go to the next ...

14

An extended comment: a recent paper by Demaine & al. proves that one tile is enough to simulate an arbitrary computation: Erik D. Demaine, Martin L. Demaine, Sándor P. Fekete, Matthew J. Patitz, Robert T. Schweller, Andrew Winslow, Damien Woods; One Tile to Rule Them All: Simulating Any Turing Machine, Tile Assembly System, or Tiling System with a ...

13

The Generalized star-height problem : "how many nesting of Kleene stars do I need to represent this regular language, with a regular expression with complementation allowed ?" We don't even know if the algorithm that always returns 1 (except 0 for star-free languages, which is a decidable case) is correct.

12

The answer by Mamadou Moustapha Kanté (who did his PhD under supervision of Bruno Courcelle) to a similar question cites A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order Ideals (1997) by B. Courcelle, R. Downey, and M. Fellows for a non-computability result (for MSOL-definable graph classes, i.e. classes defined by a ...

11

Another possible answer to Neel's perfectly correct one: Suppose that there is a combinator $E$, well-typed in system F such that the above condition holds. The type of $E$ is: $$E : \forall \alpha.\alpha\rightarrow \alpha\rightarrow {\bf bool}$$ It turns out that there is a theorem for free that expresses that such a term is necessarily constant:  \...

11

(I am retiring as no longer relevant the portion of the answer that just explained why there are no undecidable instances of a problem/no polytime algorithms with uncomputable time bound) Now the question has changed to a question about TMs whose running time is provable in some logical theory. For any (powerful enough) logical theory $T$, there exists a ...

11

A problem from Automata Theory. Input: A DFA $D$ over a binary input alphabet. Question: Does there exist a bit string $x$ such that $D$ accepts $x$ and $x$ represents a prime number in binary? In other words, is $L(D) \cap Primes$ non-empty? Comments: I originally heard this problem from a stackexchange answer by Jeffrey Shallit. If you know of any ...

11

A Non deterministic XOR automaton (NXA) fits your question. A NXA $M$ is essentially an NFA, but a word $w\in \Sigma^*$ is said to be in $L(M)$ if it is accepted by an odd number of paths (Xor relation) instead of being accepted if there exists an accepting path for it (Or relation). NXAs are used for creating small representations of regular languages as ...

9

Hardy, in his classical book Orders of infinity, considered the class of logarithmic-exponential functions. This is a rather general class of functions, which is the minimal set of functions containing $\mathbb{R}$ and $x$, closed under addition, multiplication and division (unless it has infinitely many zeroes), closed under $\exp$ and $\log|\cdot|$ (same ...

9

Regularity is decidable for DCFL, but it is undecidable for general Context-Free Languages. Regarding DCFL, I have two references (from Hopcroft+Ullman 79): A regularity test for pushdown machines, R.E. Stearns, Information and Control, 1967 (full text by clicking on the page) Regularity and Related Problems for Deterministic Pushdown Automata, Leslie G. ...

9

Given a finite automaton A over the alphabet {0,1}, does A accept the base-2 representation of at least one prime number? This is currently not known to be either decidable or undecidable. (By contrast, the same problem with "prime" replaced by "composite" is decidable.)

9

Alas, your problem is undecidable. The approach I stumbled upon (which might be overwrought, so anyone who has a more expedient approach should step up!) first uses a diagonal argument to demonstrate that there is a unary CSL $X$ which isn't regular (in contrast to the positive result for unary CFLs), and then reduces from the halting problem for Turing ...

Only top voted, non community-wiki answers of a minimum length are eligible