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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 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> (англ. ''busy beaver fuction'') {{---}} функция от натурального аргумента <tex>n</tex> (busy beaver fuction), равная максимальному числу шагов, которое может совершить программа длиной <tex>n</tex> символов и затем остановиться.
 
}}
 
}}
  
Строка 11: Строка 14:
 
Пусть <tex>f(n)</tex> представлена своим кодом.
 
Пусть <tex>f(n)</tex> представлена своим кодом.
 
Для каждого <tex>n</tex> определим программы вида:
 
Для каждого <tex>n</tex> определим программы вида:
−
   <tex>P_n</tex>():
+
   <tex>P_n</tex>:
−
     k = {десятичная запись числа n}
+
     k = {десятичная запись числа n};
−
     f = f(k)
+
     f = f(k);
−
     for i = 1 to f + 1
+
     for i = 1 to f + 1 do
−
       do smth
+
       /* шаг программы */;
  
 
Каждая такая программа делает как минимум <tex>f(n) + 1</tex> шагов.
 
Каждая такая программа делает как минимум <tex>f(n) + 1</tex> шагов.
Строка 21: Строка 24:
 
}}
 
}}
  
−
* Из этого утверждения следует, что <tex>BB(n)</tex> невычислима.
+
'''Вывод:''' доказав предыдущее утверждение, мы проверили, что максимальное число шагов, которое может совершить программа и при этом остановиться, на самом деле растет с большей скоростью, чем любая вычислимая функция. Отсюда следует, что <tex>BB(n)</tex> невычислима.
 +
 
 +
== См. также ==
 +
* [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 Машина Тьюринга]
  
−
=== Смотрите также ===
+
==Источники информации==
−
* [http://en.wikipedia.org/wiki/Busy_beaver#The_busy_beaver_function Английская Википедия]
+
* ''Хопкрофт Д., Мотвани Р., Ульман Д.'' — '''Введение в теорию автоматов, языков и вычислений''', 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 Федотов П.В., Царев Ф.Н., Шалыто А.А. {{---}} Задача поиска усердных бобров и ее решения]

Версия 01:35, 14 января 2016

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

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

Определение:
[math]BB(n)[/math] (англ. busy beaver fuction) — функция от натурального аргумента [math]n[/math] (busy beaver fuction), равная максимальному числу шагов, которое может совершить программа длиной [math]n[/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]n[/math] определим программы вида: 

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

Каждая такая программа делает как минимум [math]f(n) + 1[/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]BB(n)[/math], будет выполнено: [math] n \gt len(P_n) \Rightarrow BB(n) \geqslant BB(len(P_n)) \gt f = f(n) [/math]. Так как [math]n_0[/math] конечно, то утверждение доказано.
[math]\triangleleft[/math]

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

См. также

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

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