tgoop.com/ansi_logic/12
Last Update:
В теоретической информатике есть функция с забавным названием "усердный бобёр". Суть в чём: пусть задано натуральное число n. Рассмотрим все возможные машины Тьюринга в алфавите {0,1} с n состояниями, начинающие работу на пустой ленте. Каждая такая машина либо работает бесконечно долго, либо спустя конечное число шагов останавливается. Тогда BB(n) равно максимальному числу шагов, которые будут выполнены такими останавливающимися машинами. Нетрудно убедиться, что BB - всюду определённая невычислимая функция, которая при этом очень быстро растёт. Казалось бы, пока всё в порядке и почти ничего не внушает УЖАС... Но погодите.
Рассмотрим какую-нибудь сильную теорию, например, ZFC. Она перечислима: существует алгоритм, который работает бесконечно долго и перечисляет все её теоремы (факт понятный: перебираем все возможные выводы и выписываем то, что получается в конце). Немного пошевелим алгоритм: повелим ему остановиться, если вдруг он выведет что-то заведомо ложное, типа 0=1. Тогда получится, что наш алгоритм завершает работу, если ZFC противоречива и работает вечно, если ZFC непротиворечива. То есть мы придумали конкретный алгоритм, проблема остановки которого эквивалентна проблеме непротиворечивости ZFC. Пока что УЖАСА не случилось: подумаешь, какой-то дурацкий алгоритм, я просто сказала известные вещи другими словами...
Этот дурацкий алгоритм реализуется на какой-то вполне конкретной машине Тьюринга. И эта конкретная машина Тьюринга имеет фиксированное число состояний k. Отсюда вывод: вычислить BB(k) или даже просто оценить его сверху, оставаясь в рамках теории ZFC, невозможно!!! Потому что если это было бы можно, то, запустив нашу машину Тьюринга и подождав сколько сказано тактов, мы бы увидели, закончилась работа или нет (если не закончилась, то и не закончится никогда) и потому сказали бы, непротиворечива ZFC или нет.
И ЭТО ВСЁ ПРОСТО СВОДИТ МЕНЯ С УМА. Значения вполне конкретной, понятной, укладывающейся в сознание функции из натуральных чисел в натуральные зависят от факта непротиворечивости теории множеств - по сути, всей человеческой математики. ААААААААААА!!!!
Вот тут (https://www.scottaaronson.com/busybeaver.pdf) А.Эдидиа и С.Аронсон описывают такие машины Тьюринга, имеющие около нескольких тысяч состояний. Кто знает, может быть, удастся снизить эту границу - сейчас нет верхних оценок даже для BB(5).
BY Анси логика
Share with your friend now:
tgoop.com/ansi_logic/12