-1

Функция BB не вычислима, поскольку доказано, что для любой вычислимой функции f существует n такое, что BB (n + c)> f (n + c). Тем не менее, некоторые из его значений известны, а именно известно, что BB (1) = 1, BB (2) = 4, BB (3) = 6 и BB (4) = 13. Также известно, что BB (5)> 4097 и нижний предел для BB (6) также известен. Получите машины, которые доказывают, что BB (1) = 1, BB (2) = 4, BB (3) = 6 и BB (4) = 13. Покажите, что если бы BB были вычислимы, то также было бы вычислимым при заданном n найти машину, которая определяет BB (n).

задан 14 Окт 2:54

изменен 14 Окт 3:01

@aneta: тут без точного описания функции BB во всех деталях и мелочах, ничего решить нельзя. То есть нужна подробная информация. Дело в том, что Busy Beaver существует в куче равноценных версий, и там значения функции могут отличаться.

Последнюю фразу надо скорректировать, хотя её смысл понятен.

(14 Окт 4:49) falcao

@falcao, а можно предположить функцию BB? наблюдая за поведением BB, мы придем к этой формуле F(n)=(4(n+1))^2*n, где n - количество возможных состояний, а результатом будет количество машин Тьюринга, необходимое для достижения результата. как получить машины, которые доказывают, что BB (1) = 1, BB (2) = 4, BB (3) = 6 и BB (4) = 13? как показать, что если машина Тьюринга остановится, можно будет вычислить BB-функцию? спасибо большое за ответ! я совсем новичок в категории вычислимость и сложность

(15 Окт 3:28) aneta

@aneta: что значит "предположить функцию"? Я говорил о точном определении, без рассмотрения которого нельзя сказать что-либо. Там всё зависит от версии, в которой рассматривается "соревнование по трудолюбию", и от деталей устройства машин Тьюринга. Для подтверждения значений функции надо указать конкретные машины, которые печатают данное количество единиц.

(15 Окт 10:43) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×56

задан
14 Окт 2:54

показан
88 раз

обновлен
15 Окт 10:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru