Проблема остановки
Доказательство. Может, я чего-то не понимаю, но мне это доказательство напоминает анекдот про японскую бензопилу и сибирских мужиков. Из того, что бензопиле не по силам железный лом, не следует, что она невозможна. Из того, что от гипотетической программы можно добиться неопределённого поведения, не следует, что данная программа невозможна. На ноль вот тоже делить нельзя, и что, из этого следует, что делить вообще ни на что нельзя, такая операция над числами запрещена? И обратите внимание: к неопределённому поведению склоняют один алгоритм, а отрицают на этой почве другой.
Мне все такого типа доказательства и парадоксы, сводящиеся к циклическим ссылкам и вытягиванию оттуда противоречий, сильно не нравятся. Скажем, парадокс лжеца. "Я лгу" - это истинное высказывание или ложное? Правильный ответ: это вообще не высказывание. Ну, допустим, ты лжёшь - а о чём ты лжёшь? Корректное высказывание должно иметь вид "Я лгу, что А" или "Я истинно говорю, что Б". А "Я лгу" - это не высказывание. Так же, как "множество всех множеств" или "множество, включающее себя в качестве своего элемента" - это не множество.