Структуры данных и модели вычислений
Примеры неразрешимости
Функцию назовем вычислимойна абаке, если существует программа , которая, получив в некоторой, заранее обусловленной ячейке значение аргумента , а в остальных ячейках — нули, через конечное число шагов остановится, и в ячейке будет находиться .
Проблема построения невычислимой функции известна как "проблема усердного бобра". Пусть — абак-программа и
— номер некоторой ячейки. Определим величину следующим образом. Если в начальный момент все ячейки содержат число 0 и программа через конечное число шагов останавливается, то равно числу в момент остановки. Если же программа работает бесконечно, то считаем . Величину назовем -продуктивностью программы .
Обозначим через множество всех абак-программ, состоящих из команд. Определим функцию как максимум по всем программам из и ячейкам . Очевидно, эта функция определена при всех натуральных значениях аргумента и строго монотонна.
Лемма.
Для любого натурального числа выполняется неравенство
Для доказательства достаточно рассмотреть программу, которая сначала запишет в ячейку , затем прибавит к ней раз 1, скопирует содержимое ячейки в ячейку и добавит к ней содержимое ячейки . Очевидно, после выполнения такой программы в ячейке будет число , а подсчет числа команд показывает, что их будет . Наличие такой программы (рис. 12.1) доказывает требуемое неравенство.
Рис. 12.1.
Предположим теперь, что вычислима некоторой программой , состоящей из команд, которая, получив
в ячейке , поместит ответ в ячейку .
Тогда для каждого натурального можно построить программу, вычисляющую , состоящую из команд. Эта программа сначала запишет в ячейку , затем прибавит к ней раз единицу, затем с помощью программы в ячейке вычислит , скопирует в и, наконец, опять с помощью программы вычислит .
Наличие такой программы (рис. 12.2) означало бы, что при любом натуральном выполняется неравенство
Поскольку функция монотонна, получаем
Сопоставляя это неравенство с неравенством в утверждении леммы, получим
что приводит к противоречию, например, при .
