Phenquestions
Машина Тьюринга - центральная теоретическая конструкция в информатике. Машина Тьюринга - это абстрактная математическая модель вычислений. Использование машин Тьюринга помогает объяснить, что такое вычисление, путем разграничения так называемых «вычислимых функций».”
Раннее исследование логики Алана Тьюринга было сосредоточено на известной нерешенной проблеме, известной как Entscheidungsproblem. Entscheidungsproblem (примерно переводится с немецкого как проблема решения) была предложена философом и математиком Дэвидом Гильбертом в 1928 году. Проблема заключалась в том, существует ли алгоритм, который решал бы каждое утверждение на формальном языке.
Формальный язык - это система аксиом и правил вывода, например, в арифметике или логике первого порядка. Аксиомы могут быть любыми символами, а правила вывода могут быть любым списком правил для управления этими символами. «Решение каждого утверждения» означало либо вывод, было ли утверждение истинным / ложным, либо вывод, было ли утверждение выводимым / невыводимым. Теорема Курта Гёделя о полноте доказала, что алгоритм, определяющий применимость, эквивалентен эффективной процедуре, определяющей выводимость. Статья Алана Тьюринга 1936 года «О вычислимых числах в приложении к Entscheidungsproblem» доказала отрицательный результат, что невозможно алгоритмически решить каждое утверждение в формальной системе.
Алан Тьюринг
Чтобы доказать отрицательный результат для проблемы Entscheidungsproblem, Тьюрингу нужно было формализовать понятие алгоритма. Формализация алгоритма Тьюринга была математической моделью вычислений, которая позже стала известна как машина Тьюринга. Машина Тьюринга имеет конечный набор состояний, в которых машина может находиться. Машина Тьюринга имеет бесконечно длинную ленту, разделенную на квадраты. На каждом квадрате ленты изображен символ, составленный из конечного набора символов. В любой момент вычислений машина Тьюринга считывает символ на одном квадрате ленты. Машина Тьюринга может заменить этот символ другим символом и переместиться либо на квадрат справа, либо на квадрат слева. Действие машины Тьюринга автоматически определяется состоянием, в котором она находится. После замены символа и перехода к другому квадрату машина Тьюринга может перейти в другое состояние. В каждом штате есть свой набор правил о том, как заменять символы и в каком направлении двигаться.
Редкая физическая реализация конструкции машины Тьюринга (без бесконечной ленты)
Каноническая формулировка машины Тьюринга обычно состоит из двоичного алфавита, состоящего исключительно из нулей и единиц. Эта формулировка соответствует интуиции современных компьютерных программистов, учитывая, что все современные компьютеры используют двоичный код. На самом деле машины Тьюринга нейтральны по отношению к размеру алфавита символов. Машина Тьюринга также может использовать любой символ, числовой или взятый из любого другого типа алфавита, например графические символы или латинский алфавит. Любая формулировка любого возможного конечного алфавита доказуемо сводится к двоичной машине Тьюринга.
Машины Тьюринга предполагают, что доступен бесконечный объем памяти. Никакие реальные физически созданные машины не могут удовлетворить это требование быть машиной Тьюринга. Машина Тьюринга также предполагает, что на вычисление функции можно потратить потенциально бесконечное количество времени. Эти предположения были сделаны для создания наиболее обширного класса возможных функций для определения вычислимых функций по Тьюрингу. Вычислимые функции Тьюринга - это любые функции, которые могут быть вычислены машиной Тьюринга. Многие из этих вычислимых функций могут никогда не быть вычислимы на какой-либо машине с физическим экземпляром, потому что они требуют слишком много времени или памяти.
Тезис Чёрча-Тьюринга утверждает эквивалентность вычислимых функций и функций, которые могут быть вычислены машиной Тьюринга. Это влечет за собой, что все функции, не вычисляемые машинами Тьюринга, не могут быть вычислены никаким другим методом. Дэвид Гильберт ожидал положительного ответа на проблему Entscheidungs, который означал бы, что все проблемы вычислимы. Результат Тьюринга привел к открытию многих невычислимых проблем.
Самая известная невычислимая проблема - это проблема остановки. Проблема остановки - это проблема создания алгоритма, который может, в общем случае, решить, остановится ли компьютерная программа с ее входными данными или будет продолжаться бесконечно. Хотя есть конкретные случаи, когда проблема остановки может быть решена, она не может быть решена для каждой компьютерной программы с любым вводом. Этот результат имел важные последствия для компьютерного программирования, поскольку программисты должны знать о возможности бесконечных циклов и невозможности обнаружения всех бесконечных циклов перед запуском своих программ.
Еще одно следствие машины Тьюринга - возможность универсальных машин Тьюринга. В дизайне Тьюринга неявно заложена концепция хранения программы, которая изменяет данные вместе с данными, которые она изменяет. Это указывало на возможность создания универсальных и перепрограммируемых компьютеров. Современные компьютеры обычно являются универсальными машинами Тьюринга в том смысле, что их можно запрограммировать для запуска любого алгоритма. Это устранило необходимость в различном оборудовании для каждой потенциальной компьютерной программы и ввело различие между аппаратным и программным обеспечением.
Модель машины Тьюринга напрямую привела к изобретению компьютеров, но это не тот проект, который использовался для разработки современных компьютеров. Архитектура фон Неймана, используемая в качестве схемы для современных компьютеров, использует концепцию хранимой программы, неявную в модели машины Тьюринга, но отличается от остальной части модели машины Тьюринга несколькими важными способами. Самые большие различия заключаются в том, что архитектура фон Неймана не использует головку чтения-записи и вместо этого включает несколько регистров, оперативную память, шины данных, небольшой набор базовых машинных инструкций и возможности обработки нескольких бит. Архитектура фон Неймана также явно допускает использование специализированных устройств ввода и вывода, таких как клавиатуры и мониторы.
Модель машины Тьюринга была первой математической моделью вычислений. Это привело непосредственно к изобретению физических компьютеров. Физические компьютеры имеют все те же возможности, что и машины Тьюринга, при условии ограниченной памяти и временных ограничений на фактические вычисления. Формулировка Тьюринга по-прежнему играет центральную роль в изучении вычислений. Ученые-информатики по-прежнему активно участвуют в исследованиях вычислимости конкретных функций машинами Тьюринга.
