25
правок
Изменения
Нет описания правки
[[Категория: Теория формальных языков]]
'''Поиск усердных бобров'''(англ. ''busy beaver'') {{---}} известная задача в теории вычислимости. Под усердным бобром в теории вычислимости понимают машину Тьюринга с заданным числом состояний конечного автомата, которая будучи запущенной на пустой ленте, записывает на нее максимальное количество ненулевых символов и останавливается.
В данном конспекте будет рассмотрена функция, которая используется в этой задаче для подсчета числа шагов для завершения программы при определенном числе состояний.
{{Определение
|definition =
<b><tex>BB(n)</tex></b> (англ. ''busy beaver fuction'') {{---}} функция от натурального аргумента <tex>n</tex> (busy beaver fuction), равная максимальному числу шагов, которое может совершить программа длиной <tex>n</tex> символов и затем остановиться.
}}
Пусть <tex>f(n)</tex> представлена своим кодом.
Для каждого <tex>n</tex> определим программы вида:
<tex>P_n</tex>(): k = {десятичная запись числа n}; f = f(k); for i = 1 to f + 1do do smth/* шаг программы */;
Каждая такая программа делает как минимум <tex>f(n) + 1</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 Федотов П.В., Царев Ф.Н., Шалыто А.А. {{---}} Задача поиска усердных бобров и ее решения]
