🦫 Человечество никогда не сможет вычислить число Busy Beaver для 748 🦫
Расскажу о факте о котором недавно узнал, он меня так поразил, что я до 6 утра разбирался что к чему: Busy Beaver для 748 — это существующее
конечное целое число которое мы не сможем вычислить никогда. Оно невычислимо в рамках любой системы математических аксиом. Его нельзя вычислить принципиально - даже при неограниченных времени и памяти.
Что такое Busy Beaver от N
Числа Busy Beaver (BB) - это ключевые числа в теории информатики. Первоначально BB определяется для машин Тьюринга, но для простоты будем рассматривать программы на Python.
BB от N — это сколько шагов будет работать самый долгий скрипт на Python длиной до N символов из тех, что когда-либо остановятся. Например:
for i in range(5): pass
#
Это программа проработает 5 шагов
while True: pass
#
А эт
а
никогда не остановится, поэтому нам не подходит
Можно понять, что число программ короче N символов конечно. Из тех что останавливаются, будет та которая работает дольше всех. Число шагов которая она работает и будет BB(N).
Математика опирается на систему аксиом
Для краткости эту систему называют ZFC. Мы предполагаем, что эти аксиомы не противоречат друг другу: нельзя из них вывести утверждение
A и
not A.
Однак
о Гёдель показал, что ZFC не может доказать свою собственную непротиворичивоть. Этот факт мы используем далее.
Пишем программу для поиска противоречий
Оказывается 748 символов достаточно чтобы написать программу на Python которая будет искать противоречия в ZFC всеми возможными способами. Если она найдет противоречие, она остановится; в противном случае она будет работать бесконечно. Мы считаем, что ZFC последовательна, следовательно, программа никогда не должна остановиться.
Если бы мы знали BB(748), мы могли бы оспорить теорему Гёделя.
Мы бы запустили нашу 748 символьную программу по поиску противоречий и подождали BB(748) шагов. Если бы она не остановилась, то это бы значило что она не принадлежит к классу программ которые когда-то останавливаются. Иначе BB(748) было бы больше. А раз она не остановится никогда, тогда мы доказали что в нашей системе аксиом нет противоречий. Что мы принципиально не можем сделать.
И поэтому мы никогда не сможем узнать BB(748).
Wake up Neo
BB от 748 — это непознаваемое число. Мы даже никогда не сможем узнать верхнюю границу для него. Но это конечное целое число! WOW.