Что такое компьютер? До середины 20-го века это слово обычно относилось к людям, которые выполняли вычисления для крупных научных и инженерных проектов. Затем эти компьютеры были заменены электронными гигантами, запрограммированными на решение конкретных математических задач.
Сегодня мы можем использовать один ноутбук для множества не связанных между собой задач, которые, на первый взгляд, далеки от работы с числами. Определение вычислительной техники, охватывающее все это, может показаться слишком расплывчатым, чтобы быть полезным.
Вычисления имеют точное определение, сформулированное почти 90 лет назад Аланом Тьюрингом. В своей статье он описал гипотетические устройства, которые считывают и записывают значения 0 и 1 на бесконечной ленте по простым правилам. Эти устройства теперь известны как машины Тьюринга.
Затем он предположил, что вычислительная техника - это именно то, что могут делать машины Тьюринга. Это определение может показаться банальным, но простая модель Тьюринга оказала огромное влияние. Это выявило фундаментальные ограничения вычислительной техники и заложило теоретические основы для компьютеров общего назначения, которыми мы сейчас пользуемся каждый день.
Тьюринг разработал свою модель вычислений, чтобы ответить на главную открытую проблему в области основ математики, касающуюся пределов пошаговых процедур доказательства теорем, или алгоритмов. Он показал, что машины Тьюринга в принципе могут выполнять любой известный алгоритм, а затем доказал, что существуют фундаментальные ограничения на то, какие задачи могут решать машины Тьюринга. Это говорит о том, что некоторые “неразрешимые” проблемы вообще недоступны алгоритмам.
Выдающийся результат Тьюринга был не так уж плох. Он также доказал, что теоретически возможно построить универсальную машину Тьюринга, которая может имитировать вычисления любой другой машины Тьюринга. Это понимание вдохновило математика Джона фон Неймана на разработку более практичного плана создания программируемого компьютера, который мог бы запускать различные программы для решения различных задач. Это также побудило более поздних исследователей исследовать тесные связи между вычислениями и фундаментальными законами физики, как объяснил Майкл Нильсен в колонке для журнала Quanta в 2015 году.
Алан Тьюринг никогда не предполагал, что его воображаемая машина станет основой для реального компьютера. Но, тем не менее, его изобретение сыграло центральную роль в истории информатики и породило вопросы, над которыми исследователи бьются до сих пор.
Что нового и примечательного в этом изобретении?
Машины Тьюринга - не единственный способ математического моделирования вычислений. Исследователи разработали множество других моделей, которые являются “полными по Тьюрингу”, то есть теоретически могут выполнять все те же алгоритмы, что и машины Тьюринга. Некоторые из этих моделей гораздо менее практичны, чем другие. В 2024 году редактор Quanta Джордана Цепелевич (Jordana Cepelewicz) написала о необычном дополнении к списку: вычислениях оригами, в которых различные способы складывания бумаги представляют собой элементарные математические операции.
У полноты Тьюринга есть и темная сторона. Любая универсальная вычислительная система, должно быть, страдает от той же неразрешимости, что и машины Тьюринга. Чарли Вуд недавно проанализировал результаты десятилетий работы по полноте Тьюринга и неразрешимости в физике. Для некоторых физических задач, которые кажутся простыми, исследователи доказали, что невозможно разработать какой-либо универсальный алгоритм поиска решения, даже если вы в совершенстве знаете конфигурацию системы.
Несмотря на то, что многие исследователи обратились к новым моделям вычислений, другие продолжают изучать поведение машин Тьюринга. Одна из моих любимых тем в области компьютерных наук - игра busy beaver, в которой исследователи стремятся определить максимально возможное время работы машин Тьюринга с заданным количеством правил.
В прошлом году я сообщал об онлайн-сообществе математиков-любителей, которые нашли "занятого бобра" для машин Тьюринга с пятью правилами, решив вопрос, который оставался открытым в течение 50 лет. Этим летом я написал продолжение статьи о прогрессе в работе над примером из шести правил, который заставил исследователей работать с ошеломляюще большими цифрами. А в 2020 году Джон Павлус показал, как исследователи использовали игру busy beaver для оценки сложности самых сложных математических задач.