313
правок
Изменения
Нет описания правки
В данном конспекте будет рассмотрена функция, которая используется в этой задаче для подсчета числа шагов для завершения программы при определенном числе состояний.
{{Определение
|definition =
<b><tex>BB(n)</tex></b> (англ. ''busy beaver fuction'') {{---}} функция от натурального аргумента <tex>n</tex> (busy beaver fuction), равная максимальному числу шагов, которое может совершить программа длиной <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_np_n()</tex>: k = {десятичная запись числа n}; f m = f(k); '''for ''' i = 1 '''to f ''' m + 1 do /* шаг программы */;
Каждая такая программа делает как минимум <tex>f(n) + 1</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>
== См. также ==
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D0%B5_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8 [Вычислимые функции]]* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0 [Машина Тьюринга]]
==Источники информации==
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 2-е изд. : Пер. с англ. — Москва, Издательский дом «Вильямс», 2002. — 528 с. : ISBN 5-8459-0261-4 (рус.)
* [http://en.wikipedia.org/wiki/Busy_beaver#The_busy_beaver_function Английская Википедия {{---}} Busy_beaverBusy beaver]
* [http://is.ifmo.ru/works/_bobri.pdf Федотов П.В., Царев Ф.Н., Шалыто А.А. {{---}} Задача поиска усердных бобров и ее решения]
[[Категория: Теория формальных языков]]
[[Категория: Теория вычислимости]]
[[Категория: Разрешимые и перечислимые языки]]