The undecidability of the halting problem can be used to show the undecidability of many other problems in mathematics. The question of whether a given diophantine equation (polynomials over the integers) has a solution in the integers is undecidable; the word problem in group theory is undecidable; the identity of two elementary algebraic expressions in a formal language of “high-school algebra,” defined by Tarski, is undecidable; the mortality problem for 3 × 3 matrices (given a finite set of matrices, determine whether a finite product of them, repetitions allowed, is zero) is undecidable.
...more
