**Authors:** Thanin Quartz, Ivan O. Shevchenko, Hans De Sterck, Jun Liu The matrix mortality problem asks whether a given finite family of matrices can be multiplied, in any order and with possible repetition, to get the zero matrix. It is one of the most basic decision problems about matrix products, and it arises naturally in the study of switched linear systems and of finite automata. Mortality is trivially decidable in dimension one and has been known to be undecidable for integer matrices in dimensions three and higher since 1970; only the problem in dimension $2$ is left open. We resolve this problem by proving that mortality is undecidable for families of 5,799 distinct $2\times2$ integer matrices. All but one of the matrices are fixed and nonsingular, with determinants $\pm p$ for a single fixed prime $p$. The input affects only the remaining rank-one matrix, which encodes this input into its kernel. Our proof encodes the computation of a fixed universal machine into products of $2\times2$ matrices. We represent each configuration of the computation by a single rational number, which we identify with a line through the origin in $\mathbb{Q}^2$, and each nonsingular matrix carries out a small piece of one computation step. The main difficulty is that the matrices may be multiplied in any order, so we design them to check their own work: a "wrong'' step puts a factor of a prime number $p$ into the denominator of the rational number corresponding to the current computation step, where no later matrix can remove it. As a result, products of these matrices can go from one encoded configuration to another only by following a valid computation. The rank-one matrix then turns the question of whether the machine halts into the question of whether some product equals zero. A companion formalization in the Lean proof assistant verifies the complete reduction.

jackdk: > The only reason I can think of is that a simpler interface was chosen to make it easier for users to follow. Type inference for higher rank types is undecidable. GHC is pretty good nowadays with `ImpredicativeTypes` but it is still complicated, and you will probably run into unexpected limitations. For example the `DeepSubsumption` extension is a slight change to the type system which had bigger real world implications than anticipated. See the simplify subsumption proposal for examples. And a clear limitation is that you can’t do things like `[Application]` (putting applications in a list) if `Application` is a newtype with a `forall` in it, unless you also enable the `ImpredicativeTypes` extension.

Incompleteness and Computability is an open textbook on recursive function theory, Gödel's incompleteness theorem, models of arithmetic, second-order logic, and the lambda calculus.