- PVSM.RU - https://www.pvsm.ru -
IT технологии проникли в большинство сфер жизни человека и продолжают развиваться. Автопилот, банковская сфера, машинный перевод, медицина, финансовые рынки, полеты в космос — все это возможно благодаря одной простой идее.
В этой статье я предлагаю заглянуть за границы возможностей компьютеров и рассмотреть чего же они не могут. И почему. Алан Тьюринг еще в 30-е годы обозначил невозможные для компьютера задачи.
Если быть предельно точным, то та самая публикация Тьюринга, которая положила начало компьютерным наукам[1], была именно о вычислимых функциях, что подчеркивает существование границы, которую не может перешагнуть машина Тьюринга.
Машина Тьюринга(МТ) — это абстрактная вычислительная машина, тесно связанная с понятием алгоритма[10]. Это самый простой компьютер.
Также стоит помнить, что любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга[2]. Это ведет к тому, что все выводы касающиеся абстрактной машины Тьюринга, полностью применимы к любым компьютерам на любой архитектуре.
Проблему остановки[3] можно сформулировать как: не существует общего алгоритма, который бы мог определить, остановится ли программа, по ее описанию и входным данным.
Т.е. функция определения остановки невычислима. Доказательства можно найти в Википедии.
На практике это выглядит так — сам компьютер никогда не сможет определить точно, зависнет ли его очередная программа в бесконечном потоке инструкций или нет. А ведь написанные человеком программы ой как несовершенны.
Одна известная попытка решить эту задачу возникла в недрах Майкрософт под названием Microsoft Terminator[4]. В Microsoft хотели уменьшить количество забагованных драйверов к железу путем построение автоматической системы проверки их на корректность. Они пытались построить инструмент доказательства корректности математической модели программы. О положительных результатах мне не известно, но, думаю, частично повысить стабильность драйверов им удалось.
Эту задачу в 1962 году обозначил венгерский математик Tiber Rado, в статье "On non-computable functions"[5]. При помощи аналогии с бобром, он объяснял машину Тьюринга, но название закрепилось. Еще в этой статье было упомянуто самое большое число, известное на то время.
Если ограничить машину Тьюринга(MT) N состояниями, то можно создать конечное число машин.
При росте количества состояний N, количество возможных машин Тьюринга растет быстрее чем экспоненциально: (4(n+1))^2n.
Среди оставшихся МТ будут два типа — те, что останавливаются и нет.
Rado задался одним вопросом в двух формулировках:
Очевидно, что это число существует. И посчитав его, можно было бы проверить, завершается ли выполнение МТ за это число шагов. Если нет — очевидно, что она будет работать вечно, так как максимальный порог пройден.
The Busy Beaver Game предлагает найти программу для машины Тьюринга с N состояниями, которая работает максимально долго и потом завершается.
В качестве входных данных, лента машины Тьюринга заполнена нулями.
Необходимо составить программу, которая заполнит ее максимальным числом единиц и завершится, перейдя в состояние HALT.
Вот так выглядят правила для машины Тьюринга с двумя состояниями (N=2). Этот же пример является решением Busy Beaver для N=2.
Выполнение программы происходит примерно так:
Рисунок 1. Визуализация пошаговой работы MT при N=2. Первая колонка — это номер шага. Вторая колонка показывает как меняются состояния МТ по мере выполнения. Третья колонка — состояния ленты, где видно очередность появления единиц на ней. Четвертая — траектория перемещения указателя по ленте.
Рисунок 2. Решение Busy Beaver для задачи N=3
Рисунок 3. Визуализация пошаговой работы MT при N=3.
Рисунок 4. Решение Busy Beaver для задачи N=4
Рисунок 5. Визуализация пошаговой работы MT при N=4. Вот такая елка, с Наступающим!
Для отображения такого графа N=5 нам бы потребовалось 47,176,870 шагов минимум.
При N=6, максимальное найденное на сегодня число Бобра S(6) = 7.4 × 10^36534.
Для N=7 есть только предварительная оценка S(7) > Σ(7) > 10^10^10^10^18705352[6]
На сегодняшний день есть мнение, что люди могут найти S(6) и предоставить доказательства что оно максимальное. S(7) же абсолютно недоступно[8].
Существуют различные вариации: на ленту можно записывать 3,4,5,6 символов, вместо {0,1}. При этом числа только растут.
Общий подход к решению выглядит как разделение всех возможных машин Тьюринга на следующие классы:
При помощи нормализации по дереву(tree normalization) можно значительно сократить количество МТ.
Если бы удалось построить машину для расчета BB(n), это была бы уже сверхтьюринговая машина.
Сверхтьюринговые вычисления — это такие вычисление, которые не могут быть проделаны на машине Тьюринга[9]. Но можно ли построить физический сверхтьюринговый компьютер[7]?
Важный вопрос для создания Сильного Искусственного Интеллекта — оперирует ли разум человека только тьюринговыми вычислениями?
Зачем пытаться решить нерешаемую задачу? Может потому, что пограничные случаи в математике открывают всю полноту исходной теории.
The Busy Beaver Game тесно связана с теорией вычислимости, проблемой остановки и теорией сложности.
Еще эта задача заставила меня задуматься — что же такого может вычислить машина Тьюринга на протяжении чуть менее чем бесконечность?
[1] On Computable Numbers [1]
[2] Тезис Черча-Тьюринга [2]
[3] Проблема остановки [3]
[4] Microsoft Terminator [4]
[5] On non-computable functions [5]
[6] Good bound for S(7) [6]
[7] Hypercomputation: Hype or Computation? [7]
[8] The complex behavior of simple machines. Rona Machilin [8]
[9] Сверхтьюринговые вычисления [9]
[10] Машина Тьюринга [10]
[11] Python and C++ sources by by Peteris Krumins [11]
Автор: snowman647
Источник [12]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/matematika/223708
Ссылки в тексте:
[1] [1] On Computable Numbers : https://www.cs.virginia.edu/~robins/Turing_Paper_1936.pdf
[2] [2] Тезис Черча-Тьюринга: https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%B7%D0%B8%D1%81_%D0%A7%D1%91%D1%80%D1%87%D0%B0_%E2%80%94_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0
[3] [3] Проблема остановки: https://ru.wikipedia.org/wiki/%D0%9F%D1%80%D0%BE%D0%B1%D0%BB%D0%B5%D0%BC%D0%B0_%D0%BE%D1%81%D1%82%D0%B0%D0%BD%D0%BE%D0%B2%D0%BA%D0%B8
[4] [4] Microsoft Terminator: https://en.wikipedia.org/wiki/Microsoft_Terminator
[5] [5] On non-computable functions: http://computation4cognitivescientists.weebly.com/uploads/6/2/8/3/6283774/rado-on_non-computable_functions.pdf
[6] [6] Good bound for S(7): http://googology.wikia.com/wiki/User_blog:Wythagoras/A_good_bound_for_S(7)%3F
[7] [7] Hypercomputation: Hype or Computation?: https://www.cs.bgu.ac.il/~sipper/papabs/hypercomp.pdf
[8] [8] The complex behavior of simple machines. Rona Machilin: https://deepblue.lib.umich.edu/bitstream/handle/2027.42/28528/0000325.pdf?sequence=1&isAllowed=y
[9] [9] Сверхтьюринговые вычисления: https://ru.wikipedia.org/wiki/%D0%A1%D0%B2%D0%B5%D1%80%D1%85%D1%82%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%BE%D0%B2%D1%8B%D0%B5_%D0%B2%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F
[10] [10] Машина Тьюринга: https://ru.wikipedia.org/wiki/%D0%9C%D0%B0%D1%88%D0%B8%D0%BD%D0%B0_%D0%A2%D1%8C%D1%8E%D1%80%D0%B8%D0%BD%D0%B3%D0%B0
[11] [11] Python and C++ sources by by Peteris Krumins: https://github.com/pkrumins/busy-beaver
[12] Источник: https://habrahabr.ru/post/317996/?utm_source=habrahabr&utm_medium=rss&utm_campaign=best
Нажмите здесь для печати.