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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 12: Строка 12:
 
|proof=
 
|proof=
  
−
В данной задаче существует функция <tex>\Sigma(n)</tex>, которая в зависимости от числа состояний <tex>n</tex> возвращает максимальное число единиц, которое может быть записано на ленту машиной-чемпионом. Именно машина-чемпион является усердным бобром. Из смысла задачи следует, что функция <tex>\Sigma(n)</tex> не убывает. <br>Теперь покажем, что <tex>\forall n \ BB(n) > \Sigma(n).</tex> Для того, чтобы поместить одну единицу на ленту, требуется совершить хотя бы 1 шаг. Из этого следует, что <tex>BB(n)</tex> растет быстрее, чем <tex>\Sigma(n)</tex>. Следовательно, <tex>BB(n)</tex> не убывает.  
+
Существует программа длины <tex>n + 1</tex>, которая делает столько же шагов: надо просто в предыдущую добавить один незначащий символ. Например, пробельный. Значит, существует программа длины на один больше, которая делает не меньше шагов. Следовательно, <tex>BB</tex> не убывает. Значит, переход является корректным и наше утверждение доказано.
 
}}
 
}}
 
----
 
----
Строка 28: Строка 28:
  
 
Каждая такая программа делает как минимум <tex>f(n) + 1</tex> шагов.
 
Каждая такая программа делает как минимум <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>n</tex>, совершающую максимальное число шагов. Существует программа длины <tex>n + 1</tex>, которая делает столько же шагов: надо просто в предыдущую добавить один незначащий символ. Например, пробельный. Значит, существует программа длины на один больше, которая делает не меньше шагов. Следовательно, <tex>BB</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>n</tex>, совершающую максимальное число шагов.
 
}}
 
}}
 
----
 
----

Версия 18:17, 16 января 2016

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

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

Определение:
[math]BB(n)[/math] — функция от натурального аргумента [math]n[/math], равная максимальному числу шагов, которое может совершить программа длиной [math]n[/math] символов и затем остановиться.
Утверждение:
Функция [math]BB(n)[/math] не убывает.
[math]\triangleright[/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]n[/math], совершающую максимальное число шагов.
[math]\triangleleft[/math]

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

См. также

Источники информации

Источник — «http://neerc.ifmo.ru/wiki/index.php?title=Busy_beaver&oldid=51230»