313
правок
Изменения
Нет описания правки
'''Поиск усердных бобров''' (англ. ''busy beaver'') {{---}} известная задача в теории вычислимости. Под усердным бобром в теории вычислимости понимают [[Машина Тьюринга | машину Тьюринга]] с заданным числом состояний конечного автомата, которая будучи запущенной на пустой ленте, записывает на нее максимальное количество ненулевых символов и останавливается. В данном конспекте будет рассмотрена функция, которая используется в этой задаче для подсчета числа шагов для завершения программы при определенном числе состояний. {{Определение|definition =<b><tex>BB(n)</tex></b> {{---}} функция от натурального аргумента <tex>n</tex>, равная максимальному числу шагов, которое может совершить программа длиной <tex>n</tex> символов и затем остановиться.}}----{{Утверждение|statement= Функция <tex>BB(n)</tex> не убывает.|proof= Рассмотрим программу длины <tex>n</tex>, совершающую максимальное число шагов. Существует программа длины <tex>n + 1</tex>, которая делает столько же шагов: получается добавлением в предыдущую одного незначащего символа, например, пробельного. Значит, существует программа длины на один больше, которая делает не меньше шагов. Следовательно, <tex>BB</tex> не убывает.}}----{{Утверждение|statement=<tex>BB(n)</tex> растет быстрее любой всюду определенной неубывающей [[Вычислимые функции|вычислимой функции]] <tex>f(n) : N \rightarrow N </tex>, то есть для всех <tex>n</tex> кроме конечного числа выполнено <tex>BB(n) > f(n).</tex>|proof=Докажем, что для любой вычислимой функции <tex>f(n)</tex> функция <tex>BB(n)</tex> будет превышать ее значение (за исключением конечного множества значений числа <tex>n</tex>). <br> Пусть <tex>f(n)</tex> представлена своим кодом. Для каждого <tex>n</tex> определим программы вида: <tex>p_n()</tex>: k = десятичная запись числа n m = f(k) '''for''' i = 1 '''to''' m + 1 шаг программы Каждая такая программа делает как минимум <tex>f(n) + 1</tex> шагов.Так как мы рассматриваем <tex>n</tex> в десятичной записи, то длина <tex>p_n</tex> будет равна <tex> \lg n + const </tex>, где <tex>const</tex> {{---}} длина кода без десятичной записи <tex>n</tex>. Пусть <tex>n_0</tex> {{---}} решение уравнения <tex>\lg n + const = n</tex>. Тогда для всех натуральных <tex> n > \left \lceil n_0 \right \rceil </tex> будет выполнено неравенство: <tex> n > len(p_n) \Rightarrow BB(n) \geqslant BB(len(p_n)) > m = f(n) </tex>. Данный переход корректен, так как мы доказали, что <tex>BB(n)</tex> {{---}} монотонно возрастающая функция. Так как <tex>n_0</tex> конечно, то мы всегда можем найти такие значения <tex>n</tex>, при которых будет выполняться полученное неравенство. Отсюда следует, что утверждение доказано.}}'''Вывод:''' доказав предыдущее утверждение, мы проверили, что максимальное число шагов, которое может совершить программа и при этом остановиться, на самом деле растет с большей скоростью, чем любая вычислимая функция. Отсюда следует, что <tex>BB(n)</tex> невычислима.----{{Утверждение|id=proposalU. |statement=Функция [[Busy beaver]] невычислима.|proof= По [[Теорема о рекурсии | теореме о рекурсии]], программа может знать свой исходный код. Значит, в неё можно написать функцию <tex> \mathrm{getSrc()} </tex>, которая вернёт строку {{---}} исходный код программы. Предположим, что функция [[Busy beaver]] вычислима. Тогда напишем такую программу<code> <tex>p(){:}</tex> '''for''' i = 1..BB(<tex>|\mathrm{getSrc()}|</tex>) + 1 '''do''' smth</code> Такая программа всегда совершает больше шагов, чем функция <tex> BB </tex> от этой программы. А это невозможно, так <tex> BB(|p|) </tex> равна максимальному числу шагов как раз этой программы. Получили противоречие.}} == См. также ==* [[Вычислимые функции]]* [[Машина Тьюринга]] ==Источники информации==* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в разработкетеорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)* [http://en.wikipedia.org/wiki/Busy_beaver#The_busy_beaver_function Английская Википедия {{---}} Busy beaver]* [http://is.ifmo.ru/works/_bobri.pdf Федотов П.В., Царев Ф.Н., Шалыто А.А. {{---}}Задача поиска усердных бобров и ее решения] [[Категория: Теория формальных языков]][[Категория: Теория вычислимости]][[Категория: Разрешимые и перечислимые языки]]
