View article

We prove a number of natural problems are undecidable. We do this by coding the halting problem into them. These problems include Conway’s generalization of the Collatz function, word problems in formal languages, the Entscheidungsproblem, word problems in semigroups and groups, and we finish with a proof of the undecidability of Hilbert’s 10th Problem for exponential Diophantine equations.