Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow ДИСКРЕТНЫЙ АНАЛИЗ. ФОРМАЛЬНЫЕ СИСТЕМЫ И АЛГОРИТМЫ
Посмотреть оригинал

Функция трудолюбия Радо

Приведём пример невычислимой функции, для которой доказательство невычислимости не использует проблему остановки.

Определение 4.35. Функция Радо R(n) определяется следующим образом: R(n) — максимальное количество единиц в результате работы на пустом входе машины Тьюринга с п состояниями и алфавитом {1,Л} при условии, что МТ останавливается на пустом входе.

Другими словами, между машинами Тьюринга с п состояниями происходит соревнование: какая из них напишет больше всего единиц на изначально пустую ленту и остановится. Функция Радо равна результату победителя в этом соревновании.

Теорема 4.36. Функция Радо невычислима.

Доказательство. Очевидно, что R(n) неубывающая функция. При этом R(n) растёт достаточно быстро.

Рассмотрим МТ

(О ^ г < п). Выполняя такты работы этой машины, мы увидим, что из начальной конфигурации qo она переходит в конфигурацию IH43I, затем в ПП^з, затем в 1111111 r/e> 1 и т. д.. Останавливается такая машина в конфигурации

Таким образом, R(3n + 1) ^ 4п.

Предположим, что R(n) вычислима. Тогда при достаточно больших п выполняется неравенство

при некоторой константе С. Действительно, нужно запустить после описанной выше машины такую машину, которая переводит головку на самую левую единицу и запускает МТ, вычисляющую функцию R. Полученное соединение машин будет иметь С + Зп + 1 состояний и оставлять на ленте 7?(4п) единиц.

Осталось заметить, что при достаточно больших п выполнено неравенство С + Зп + 1 ^ 4п. Поэтому неравенство (4.23) противоречит монотонности функции R. ?

 
Посмотреть оригинал
< Предыдущая   СОДЕРЖАНИЕ   Следующая >
 

Популярные страницы