функция Радо, или Busy Beaver
Это небольшое Добавление к предыдущим постам, в которых шла речь об алгоритмических проблемах и теоремах Гёделя.
Существует ещё один весьма простой подход к доказательству существования алгоритмически неразрешимых проблем, который имеет смысл изложить. Речь пойдёт о так называемой функции Радо, которую сейчас чаще принято называть Busy Beaver (я благодарю archernikov за замечание по поводу терминологии). Точнее было бы говорить не об одной такой функции, а о целом классе функций, которые определяются сходным образом. Эти функции легко описываются, и каждая из них невычислима, то есть нельзя написать компьютерную программу для её вычисления. Отсюда не только следует существование алгоритмически неразрешимых проблем, но также очень легко вытекает алгоритмическая неразрешимость проблемы остановки.
Чаще всего для определения функции Радо используются машины Тьюринга, но можно вместо этого брать за основу любой алгоритмический язык. Предпочтительнее всего рассматривать язык не слишком низкого и не слишком высокого уровня. Скажем, вместо ассемблера или C++ уместнее рассматривать тот алгоритмический "псевдоязык", который был использован в предыдущих записях. Мы будем считать, что команды программы разделены при помощи точки с запятой, а метки вводятся по необходимости. Как и ранее, мы будем рассматривать программы без параметров (без процедуры ввода) и программы с одним входным параметром -- натуральным числом. Вместо процедуры вывода мы берём специальную ячейку памяти, в которой будет храниться ответ, и соответствующая переменная будет обозначена через s. Удобно также считать, что перед началом работы программы значения всех переменных равны нулю.
Функцию Радо мы определим так. Пусть n -- натуральное число. Рассмотрим все программы без параметров, написанные на нашем языке, имеющие длину (количество символов) не более n. Среди них какие-то останавливаются за конечное время. Те программы, которые работают бесконечно долго, мы рассматривать не будем, а среди остальных устроим "конкурс по трудолюбию". Победят те машины (их может быть несколько) , у которых в момент остановки значение переменной s будет наибольшим. Это рекордное значение зависит от n. Мы будем обозначать его через R(n). Это и есть функция Радо.
Сразу заметим, что если бы проблема остановки была разрешима алгоритмически, то мы имели бы очень простой алгоритм вычисления R(n) по заданному n. А именно, надо было бы рассмотреть все тексты длиной не более n, отобрать из них те, которые являются программами без параметров. Далее осуществить эффективный отбор тех из них, которым не суждено остановиться. Эти программы надо исключить, а все оставшиеся прогнать пошагово до момента остановки. После чего останется выявить победителей, выясняя, у каких машин значение переменной s наибольшее.
Таким образом, нам достаточно показать невычислимость функции R(n), и этим будет дано ещё одно доказательство неразрешимости проблемы остановки.
Для начала приведём такой пример. Рассмотрим программу без параметров из одной команды -- [s:=9999999] (текст программы заключён в квадратные скобки, которые не считаются). Данная программа имеет длину 10. Отсюда следует, что R(10) составляет по крайней мере 10^7-1. Ясно, что в длинных программах можно не просто записывать число из одних девяток во всю длину, а применять какие-то более хитрые способы.
Итак, пусть некто претендует на умение вычислять алгоритмически функцию Радо R(n). Это значит, что он располагает соответствующей программой BB вида input(n);[...] состоящей из K символов. Здесь K -- некая конкретная константа, которая нам дана. Напишем теперь такую программу -- n:=2*K+6;[...];s:=s+1 где K есть не переменная, а явная запись константы K. Вообще говоря, это требует порядка log K символов, но мы не будем "мелочиться", считая, что в самом худшем случае для написания константы K нам потребуется не более K символов (даже если писать число при помощи "палочек").
Длина написанной нами программы не превосходит 5+K+3+(K-9)+7 = 2K+6 (то, что стоит в квадратных скобках, имеет длину K-9). По предположению относительно BB, после её выполнения мы должны получить R(n)+1, где n=2K+6. Поскольку программа останавливается, она участвует в конкурсе. Её длина не более n=2K+6, а потому значение переменной s не должно превосходить рекордного, равного R(n). Это даёт противоречие с тем фактом, что программа BB с одним входом вычисляет функцию Радо.
В заключение также отметим, что R(n) -- очень быстро растущая функция. Начиная с некоторого значения n, она превысит любую фиксированную вычислимую функцию.
Все комментарии просьба оставлять в ветке "анонс": http://falcao.livejournal.com/25569.html
Существует ещё один весьма простой подход к доказательству существования алгоритмически неразрешимых проблем, который имеет смысл изложить. Речь пойдёт о так называемой функции Радо, которую сейчас чаще принято называть Busy Beaver (я благодарю archernikov за замечание по поводу терминологии). Точнее было бы говорить не об одной такой функции, а о целом классе функций, которые определяются сходным образом. Эти функции легко описываются, и каждая из них невычислима, то есть нельзя написать компьютерную программу для её вычисления. Отсюда не только следует существование алгоритмически неразрешимых проблем, но также очень легко вытекает алгоритмическая неразрешимость проблемы остановки.
Чаще всего для определения функции Радо используются машины Тьюринга, но можно вместо этого брать за основу любой алгоритмический язык. Предпочтительнее всего рассматривать язык не слишком низкого и не слишком высокого уровня. Скажем, вместо ассемблера или C++ уместнее рассматривать тот алгоритмический "псевдоязык", который был использован в предыдущих записях. Мы будем считать, что команды программы разделены при помощи точки с запятой, а метки вводятся по необходимости. Как и ранее, мы будем рассматривать программы без параметров (без процедуры ввода) и программы с одним входным параметром -- натуральным числом. Вместо процедуры вывода мы берём специальную ячейку памяти, в которой будет храниться ответ, и соответствующая переменная будет обозначена через s. Удобно также считать, что перед началом работы программы значения всех переменных равны нулю.
Функцию Радо мы определим так. Пусть n -- натуральное число. Рассмотрим все программы без параметров, написанные на нашем языке, имеющие длину (количество символов) не более n. Среди них какие-то останавливаются за конечное время. Те программы, которые работают бесконечно долго, мы рассматривать не будем, а среди остальных устроим "конкурс по трудолюбию". Победят те машины (их может быть несколько) , у которых в момент остановки значение переменной s будет наибольшим. Это рекордное значение зависит от n. Мы будем обозначать его через R(n). Это и есть функция Радо.
Сразу заметим, что если бы проблема остановки была разрешима алгоритмически, то мы имели бы очень простой алгоритм вычисления R(n) по заданному n. А именно, надо было бы рассмотреть все тексты длиной не более n, отобрать из них те, которые являются программами без параметров. Далее осуществить эффективный отбор тех из них, которым не суждено остановиться. Эти программы надо исключить, а все оставшиеся прогнать пошагово до момента остановки. После чего останется выявить победителей, выясняя, у каких машин значение переменной s наибольшее.
Таким образом, нам достаточно показать невычислимость функции R(n), и этим будет дано ещё одно доказательство неразрешимости проблемы остановки.
Для начала приведём такой пример. Рассмотрим программу без параметров из одной команды -- [s:=9999999] (текст программы заключён в квадратные скобки, которые не считаются). Данная программа имеет длину 10. Отсюда следует, что R(10) составляет по крайней мере 10^7-1. Ясно, что в длинных программах можно не просто записывать число из одних девяток во всю длину, а применять какие-то более хитрые способы.
Итак, пусть некто претендует на умение вычислять алгоритмически функцию Радо R(n). Это значит, что он располагает соответствующей программой BB вида input(n);[...] состоящей из K символов. Здесь K -- некая конкретная константа, которая нам дана. Напишем теперь такую программу -- n:=2*K+6;[...];s:=s+1 где K есть не переменная, а явная запись константы K. Вообще говоря, это требует порядка log K символов, но мы не будем "мелочиться", считая, что в самом худшем случае для написания константы K нам потребуется не более K символов (даже если писать число при помощи "палочек").
Длина написанной нами программы не превосходит 5+K+3+(K-9)+7 = 2K+6 (то, что стоит в квадратных скобках, имеет длину K-9). По предположению относительно BB, после её выполнения мы должны получить R(n)+1, где n=2K+6. Поскольку программа останавливается, она участвует в конкурсе. Её длина не более n=2K+6, а потому значение переменной s не должно превосходить рекордного, равного R(n). Это даёт противоречие с тем фактом, что программа BB с одним входом вычисляет функцию Радо.
В заключение также отметим, что R(n) -- очень быстро растущая функция. Начиная с некоторого значения n, она превысит любую фиксированную вычислимую функцию.
Все комментарии просьба оставлять в ветке "анонс": http://falcao.livejournal.com/25569.html