Проблема остановки: различия между версиями

Напишем алгоритм Диагонализатор, который принимает на вход число <math>N</math>, передает пару аргументов <math>(N, N)</math> Анализатору и возвращает результат его работы. Другими словами, Диагонализатор останавливается в том и только в том случае, если не останавливается алгоритм с номером <math>N</math>, получив на вход число <math>N</math>. Пусть <math>K</math> — это порядковый номер Диагонализатора в множестве <math>S</math>. Запустим Диагонализатор, передав ему это число <math>K</math>. Диагонализатор остановится в том и только том случае, если алгоритм с номером <math>K</math> (то есть, он сам) не останавливается, получив на вход число <math>K</math> (какое мы ему и передали). Из этого противоречия следует, что наше предположение неверно: Анализатор не существует, что и требовалось доказать.