Граница вычислений

Консалтинговая компания по машинному обучению:
Подпишитесь на мою рассылку, чтобы получать обучающие и полезные статьи (и ничего больше!):
Хотите работать вместе? Смотрите здесь:
У алгоритмов есть предел. СОЦИАЛЬНЫЕ СЕТИ LinkedIn:   / dj-rich-90b91753   Twitter:   / duanejrich   Github:
Нравится учиться таким образом? Хотите, чтобы я снял больше видео? Поддержите меня на Patreon:   / mutualinformation   МИР ДЕЯТЕЛЬНЫХ БОБРОВ На мой взгляд, лучше всего начать со статьи Ааронсона «Граница деятельных Бобров» (ссылка [1]). Она доступна для понимания, хорошо написана и даёт всестороннее представление о мире БОБРОВ. Кроме того, Гугология хорошо представляет сообщество в его стремлениях и энтузиазме (например, см. ссылку [8]). ПРИМЕЧАНИЯ [1] Описывая, как вычисляется Sigma(4), я говорю «свести к небольшой группе, которая остановилась и побежала, чтобы получить максимальное количество единиц». Мне указали на то, что это неточное описание. Точнее сказать, что мы свели к небольшой группе, которая *не останавливается*. В результате многие машины работают, некоторые останавливаются, а некоторые продолжают работать. Самая сложная работа заключается в доказательстве того, что работающие машины будут работать вечно. После того, как это будет доказано, число занятых бобровых машин будет равно максимальному количеству единиц, записанных всеми остановленными машинами. СПРАВОЧНЫЕ ЗАМЕЧАНИЯ Как уже упоминалось, я в основном читал работу Скотта Ааронсона (ссылки [1], [3]) и его блог:
, где он публикует новости, связанные с BB. Следующей была страница в Википедии (ссылка [6]). Кроме того, [2] и [7] были полезны для понимания того, как люди ищут границы и значения для Sigma(n). Оригинальная статья (ссылка [4]) была полезна для понимания того, почему Sigma(n) была изначально изобретена (чтобы обеспечить чётко определённую невычислимую функцию), и для понимания первоначального формата соревнования BB. Границы, связанные с последовательностью Грэма, были найдены в [6] и [8]. СПИСОК ЛИТЕРАТУРЫ [1] С. Ааронсон, «Граница занятого бобра»,
[2] А. Х. Брэди. «Определение значения невычислимой функции Радо Σ(k) для четырёхмашин Тьюринга». Математика вычислений, 1983. [3] А. Йедидиа и С. Ааронсон. «Относительно небольшая машина Тьюринга, поведение которой не зависит от теории множеств». Complex Systems, (25):4, 2016,
[4] Т. Радо. «О невычислимых функциях». Bell System Technical Journal. 41 (3): 877–884, 1962 [5] Коупленд, Б. Джек, «Тезис Чёрча-Тьюринга», Стэнфордская философская энциклопедия (лето 2020 г.), под ред. Эдварда Н. Залты
[6] Авторы Википедии. «Деловой бобер» Википедия, 2023,
[7] П. Мишель. «Конкурс «Делового бобра»: исторический обзор». 2019.
3749 [8] Wythagoras (имя пользователя), «Девятнадцатое число трудолюбивого Бобра больше числа Грэма!», googology.fandom.com, 2016,
! [9] S. Ligocki, «BB(6, 2) больше 10^10...^10», 2022,
ТАЙМ-КОДЫ 0:00 Введение 1:21 Двоичная машина Тьюринга 2:42 Два факта о машинах Тьюринга 3:54 Что такое функция трудолюбивого Бобра? 5:40 Почему это сложно вычислить? 6:28 Вычислимость 7:41 Выстрел в короля 10:36 Книга «Деловые бобры» ссылается на открытые проблемы 11:39 Её значения невозможно доказать в некоторых системах 12:08 Мир «Деловых бобров»