|
|
Пишет clement (![[info]](http://lj.rossia.org/img/userinfo.gif){kind=small} clement)@ 2003-04-12 16:07:00 |
 |
|
 |
|
|
|
|
|
|
 |
|
 |
Проблема остановки и Стефен Вольфрам
http://mathworld.wolfram.com/HaltingPro
Halting 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/UniversalT
BUT, the halting problem for universal Turing machines is known to be undecidable! So, how can a 2-state machine be universal?!
http://mathworld.wolfram.com/HaltingPro
Halting 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/UniversalT
BUT, the halting problem for universal Turing machines is known to be undecidable! So, how can a 2-state machine be universal?!
