Структуры данных и модели вычислений
команда повторяется раз, общее
Итак, предположение о вычислимости функции привело к противоречию.
Рис. 12.2.
На рис. 12. 2 команда повторяется раз, общее количество команд в программе , в ячейке
вычисляется .
Рассмотрим произвольную инъективную нумерацию программ, то есть нумерацию, ставящую в соответствие каждой программе ее номер , причем разным программам ставятся в соответствие разные номера. Программу назовем самоприменимой относительно ячейки , если она, получив в ячейке свой номер, а в остальных ячейках — нули, через конечное число шагов завершает вычисления.
Рассмотрим функцию , определяемую следующим образом:
- , если является номером некоторой самоприменимой относительно ячейки программы,
- , в противном случае.
Докажем, что функция не вычислима никакой программой. Предположим, что вычисляется программой , которая, получив в ячейке число , остановится через конечное число шагов и в ячейке оставит . Рассмотрим программу , изображенную на рис. 12.3.
Рис. 12.3.
Если самоприменима относительно ячейки , то , поэтому, когда проработает программа , в ячейке
будет записана 1 и остальная часть программы — будет работать без остановки. Следовательно, — не самоприменима относительно .
Если же не самоприменима относительно ячейки , то , следовательно, когда проработает программа , в ячейке будет записан 0 и тогда остальная часть программы — сразу же завершит работу. Следовательно, — самоприменима относительно .
Итак, предположение о вычислимости функции в любом случае приводит к противоречию.
