solution for the halting problem is here

[109]

вот, нашёл. в смысле - не сам нашёл, а на интернете.

запускаем, значит, исследуемую программу на машине, которая делает первый шаг за секунду, второй за полсекунды, третий за четверть, ну и так далее. если через две секунды программа всё ещё работает, то она non-halting.

Comments

[thedeemon.livejournal.com]

Про Cray-3 говорили, что он выполняет бесконечный цикл менее чем за 2 секунды. Оптимизация. :)