Проблема остановки и Стефен Вольфрам http://mathworld.wolfram.com/HaltingProblem.htmlHalting Problem
The determination of whether a Turing machine will come to a halt given a particular input program. The halting problem is solvable for machines with less than four states. However, the four-state case is open, and the five-state case is almost certainly unsolvable due to the fact that it includes machines iterating Collatz-like congruential functions, and such specific problems are currently open. The problem of whether a general Turing machine halts is undecidable, as first proved by Turing (Wolfram 2002, pp. 1137-1138).
Wolfram 2002 = Stephen Wolfram, A New Kind of Science.
A 2-state 5-color universal Turing machine, illustrated above, was discovered by Wolfram (2002, p. 707).
http://mathworld.wolfram.com/UniversalTuringMachine.htmlBUT, the halting problem for universal Turing machines is known to be undecidable! So, how can a 2-state machine be universal?!