Структуры данных и модели вычислений



         

Примеры неразрешимости - часть 2


Итак, предположение о вычислимости функции привело к противоречию.


Рис. 12.2. 

На рис. 12.2 команда повторяется раз, общее количество команд в программе , в ячейке

вычисляется .

Рассмотрим произвольную инъективную нумерацию программ, то есть нумерацию, ставящую в соответствие каждой программе ее номер , причем разным программам ставятся в соответствие разные номера. Программу назовем самоприменимой относительно ячейки , если она, получив в ячейке свой номер, а в остальных ячейках — нули, через конечное число шагов завершает вычисления.

Рассмотрим функцию , определяемую следующим образом:

  • , если является номером некоторой самоприменимой относительно ячейки программы,
  • , в противном случае.

Докажем, что функция не вычислима никакой программой. Предположим, что вычисляется программой , которая, получив в ячейке число , остановится через конечное число шагов и в ячейке оставит . Рассмотрим программу , изображенную на рис. 12.3.


Рис. 12.3. 

Если самоприменима относительно ячейки , то , поэтому, когда проработает программа , в ячейке

будет записана 1 и остальная часть программы — будет работать без остановки. Следовательно, — не самоприменима относительно .

Если же не самоприменима относительно ячейки , то , следовательно, когда проработает программа , в ячейке будет записан 0 и тогда остальная часть программы — сразу же завершит работу. Следовательно, — самоприменима относительно .

Итак, предположение о вычислимости функции в любом случае приводит к противоречию.




Содержание  Назад  Вперед