Busy beaver — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
 
(не показано 18 промежуточных версий 5 участников)
Строка 1: Строка 1:
[[Категория: Теория формальных языков]]
+
'''Поиск усердных бобров''' (англ. ''busy beaver'') {{---}} известная задача в теории вычислимости. Под усердным бобром в теории вычислимости понимают [[Машина Тьюринга | машину Тьюринга]] с заданным числом состояний конечного автомата, которая будучи запущенной на пустой ленте, записывает на нее максимальное количество ненулевых символов и останавливается.
 +
 
 +
В данном конспекте будет рассмотрена функция, которая используется в этой задаче для подсчета числа шагов для завершения программы при определенном числе состояний.
 
{{Определение
 
{{Определение
 
|definition =
 
|definition =
<b><tex>BB(n)</tex></b> {{---}} функция от натурального аргумента <tex>n</tex> (busy beaver fuction), равная максимальному числу шагов, которое может совершить программа длиной <tex>n</tex> символов и затем остановиться.
+
<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=
 
|statement=
<tex>BB(n)</tex> растет быстрее любой всюду определенной неубывающей вычислимой функции <tex>f(n) : N \rightarrow N </tex>, то есть для всех <tex>n</tex> кроме конечного числа выполнено <tex>BB(n) > f(n)</tex>
+
<tex>BB(n)</tex> растет быстрее любой всюду определенной неубывающей [[Вычислимые функции|вычислимой функции]] <tex>f(n) : N \rightarrow N </tex>, то есть для всех <tex>n</tex> кроме конечного числа выполнено <tex>BB(n) > f(n).</tex>
 
|proof=
 
|proof=
Пусть <tex>f(n)</tex> представлена своим кодом.
+
Докажем, что для любой вычислимой функции <tex>f(n)</tex> функция <tex>BB(n)</tex> будет превышать ее значение (за исключением конечного множества значений числа <tex>n</tex>). <br>
Для каждого <tex>n</tex> определим программы вида:
+
Пусть <tex>f(n)</tex> представлена своим кодом. Для каждого <tex>n</tex> определим программы вида:
   <tex>P_n</tex>():
+
   <tex>p_n()</tex>:
     k = {десятичная запись числа n}
+
     k = десятичная запись числа n
     f = f(k)
+
     m = f(k)
     for i = 1 to f + 1
+
     '''for''' i = 1 '''to''' m + 1  
       do smth
+
       шаг программы
  
 
Каждая такая программа делает как минимум <tex>f(n) + 1</tex> шагов.
 
Каждая такая программа делает как минимум <tex>f(n) + 1</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>BB(n)</tex>, будет выполнено: <tex> n > len(P_n) \Rightarrow BB(n) \geqslant BB(len(P_n)) > f = f(n) </tex>. Так как <tex>n_0</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(n)</tex> невычислима.
+
Такая программа всегда совершает больше шагов, чем функция <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 Федотов П.В., Царев Ф.Н., Шалыто А.А. {{---}} Задача поиска усердных бобров и ее решения]
 +
 
 +
[[Категория: Теория формальных языков]]
 +
[[Категория: Теория вычислимости]]
 +
[[Категория: Разрешимые и перечислимые языки]]

Текущая версия на 17:32, 2 января 2017

Поиск усердных бобров (англ. busy beaver) — известная задача в теории вычислимости. Под усердным бобром в теории вычислимости понимают машину Тьюринга с заданным числом состояний конечного автомата, которая будучи запущенной на пустой ленте, записывает на нее максимальное количество ненулевых символов и останавливается.

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

Определение:
[math]BB(n)[/math] — функция от натурального аргумента [math]n[/math], равная максимальному числу шагов, которое может совершить программа длиной [math]n[/math] символов и затем остановиться.

Утверждение:
Функция [math]BB(n)[/math] не убывает.
[math]\triangleright[/math]
Рассмотрим программу длины [math]n[/math], совершающую максимальное число шагов. Существует программа длины [math]n + 1[/math], которая делает столько же шагов: получается добавлением в предыдущую одного незначащего символа, например, пробельного. Значит, существует программа длины на один больше, которая делает не меньше шагов. Следовательно, [math]BB[/math] не убывает.
[math]\triangleleft[/math]

Утверждение:
[math]BB(n)[/math] растет быстрее любой всюду определенной неубывающей вычислимой функции [math]f(n) : N \rightarrow N [/math], то есть для всех [math]n[/math] кроме конечного числа выполнено [math]BB(n) \gt f(n).[/math]
[math]\triangleright[/math]

Докажем, что для любой вычислимой функции [math]f(n)[/math] функция [math]BB(n)[/math] будет превышать ее значение (за исключением конечного множества значений числа [math]n[/math]).
Пусть [math]f(n)[/math] представлена своим кодом. Для каждого [math]n[/math] определим программы вида:

 [math]p_n()[/math]:
   k = десятичная запись числа n
   m = f(k)
   for i = 1 to m + 1 
     шаг программы

Каждая такая программа делает как минимум [math]f(n) + 1[/math] шагов.

Так как мы рассматриваем [math]n[/math] в десятичной записи, то длина [math]p_n[/math] будет равна [math] \lg n + const [/math], где [math]const[/math] — длина кода без десятичной записи [math]n[/math]. Пусть [math]n_0[/math] — решение уравнения [math]\lg n + const = n[/math]. Тогда для всех натуральных [math] n \gt \left \lceil n_0 \right \rceil [/math] будет выполнено неравенство: [math] n \gt len(p_n) \Rightarrow BB(n) \geqslant BB(len(p_n)) \gt m = f(n) [/math]. Данный переход корректен, так как мы доказали, что [math]BB(n)[/math] — монотонно возрастающая функция. Так как [math]n_0[/math] конечно, то мы всегда можем найти такие значения [math]n[/math], при которых будет выполняться полученное неравенство. Отсюда следует, что утверждение доказано.
[math]\triangleleft[/math]

Вывод: доказав предыдущее утверждение, мы проверили, что максимальное число шагов, которое может совершить программа и при этом остановиться, на самом деле растет с большей скоростью, чем любая вычислимая функция. Отсюда следует, что [math]BB(n)[/math] невычислима.


Утверждение:
Функция Busy beaver невычислима.
[math]\triangleright[/math]

По теореме о рекурсии, программа может знать свой исходный код. Значит, в неё можно написать функцию [math] \mathrm{getSrc()} [/math], которая вернёт строку — исходный код программы. Предположим, что функция Busy beaver вычислима. Тогда напишем такую программу

 [math]p(){:}[/math]
   for i = 1..BB([math]|\mathrm{getSrc()}|[/math]) + 1
     do smth

Такая программа всегда совершает больше шагов, чем функция [math] BB [/math] от этой программы. А это невозможно, так [math] BB(|p|) [/math] равна максимальному числу шагов как раз этой программы. Получили противоречие.
[math]\triangleleft[/math]

См. также[править]

Источники информации[править]