Машины Тьюринга и теория вычислимости

Машина Тьюринга – центральная теоретическая конструкция в информатике. Машина Тьюринга – это абстрактная математическая модель вычислений. Использование машин Тьюринга помогает объяснить, что такое вычисление, путем разграничения так называемых «вычислимых функций».

Раннее исследование логики Алана Тьюринга было сосредоточено на известной нерешенной проблеме, известной как Entscheidungsproblem. Entscheidungsproblem (примерно переводится с немецкого как «проблема решения») была предложена философом и математиком Дэвидом Гильбертом в 1928 году. Задача заключалась в том, существует ли алгоритм, который решал бы каждое утверждение на формальном языке.

Формальный язык – это система аксиом и правил вывода, например, в арифметике или логике первого порядка. Аксиомы могут быть любыми символами, а правила вывода могут быть любым списком правил манипулирования этими символами. «Принятие решения по каждому утверждению» означало либо вывод, было ли утверждение истинным/ложным, либо вывод, было ли утверждение выводимым/невыводимым. Теорема Курта Гёделя о полноте доказала, что алгоритм, определяющий применимость, эквивалентен эффективной процедуре, определяющей выводимость. В статье Алана Тьюринга 1936 года «О вычислимых числах в приложении к Entscheidungsproblem» был доказан отрицательный результат, заключающийся в невозможности алгоритмически решить каждое утверждение в формальной системе.

Алан Тьюринг

Чтобы доказать отрицательный результат для проблемы Entscheidungsproblem, Тьюрингу нужно было формализовать понятие алгоритма. Формализация алгоритма Тьюринга была математической моделью вычислений, которая позже стала известна как машина Тьюринга. Машина Тьюринга имеет конечный набор состояний, в которых она может находиться. Машина Тьюринга имеет бесконечно длинную ленту, разделенную на квадраты. На каждом квадрате ленты есть символ, составленный из конечного набора символов. В любой момент вычислений машина Тьюринга считывает символ на одном квадрате ленты. Машина Тьюринга может заменить этот символ другим символом и переместиться либо на квадрат справа, либо на квадрат слева. Действие машины Тьюринга автоматически определяется состоянием, в котором она находится. После того, как символ замены и перемещение в другой квадрат произойдут, машина Тьюринга может перейти в другое состояние. Каждое состояние имеет свой набор правил, касающихся того, как заменять символы и в каком направлении двигаться.

Редкая физическая реализация конструкции машины Тьюринга (без бесконечной ленты)

Каноническая формулировка машины Тьюринга обычно состоит из двоичного алфавита, состоящего исключительно из нулей и единиц. Эта формулировка соответствует интуиции современных программистов, учитывая, что все современные компьютеры используют двоичный код. Фактически машины Тьюринга нейтральны по отношению к размеру алфавита символов. Машина Тьюринга также может использовать любой символ, числовой или взятый из любого другого типа алфавита, такого как графические символы или латинский алфавит. Любая формулировка любого возможного конечного алфавита доказуемо сводится к двоичной машине Тьюринга.

Машины Тьюринга предполагают, что доступен бесконечный объем памяти. Никакие реальные физически инстанциированные машины не могут удовлетворить этому требованию быть машиной Тьюринга. Машина Тьюринга также предполагает, что на вычисление функции можно потратить потенциально бесконечное количество времени. Эти предположения были сделаны для создания наиболее обширного класса возможных функций для определения вычислимых функций по Тьюрингу. Вычислимые функции Тьюринга – это любые функции, которые могут быть вычислены машиной Тьюринга. Многие из этих вычислимых функций никогда не могут быть вычислены какой-либо машиной с физическим экземпляром, потому что они требуют слишком много времени или памяти.

Тезис Чёрча-Тьюринга утверждает эквивалентность вычислимых функций и функций, которые могут быть вычислены машиной Тьюринга. Это влечет за собой, что все функции, не вычисляемые машинами Тьюринга, не могут быть вычислены никаким другим методом. Дэвид Гильберт ожидал положительного ответа на проблему Entscheidungs, который означал бы, что все проблемы вычислимы. Результат Тьюринга привел к открытию многих невычислимых проблем.

Самая известная невычислимая проблема – это проблема остановки. Проблема остановки – это проблема создания алгоритма, который в общем случае может решить, остановится ли компьютерная программа с ее входными данными или будет продолжаться бесконечно. Хотя есть конкретные случаи, когда проблема остановки может быть решена, она не может быть решена для каждой компьютерной программы с любым вводом. Этот результат имел важные последствия для компьютерного программирования, так как программисты должны знать о возможности бесконечных циклов и невозможности обнаружения всех бесконечных циклов до запуска своих программ.

Еще одно следствие машины Тьюринга – возможность универсальных машин Тьюринга. В дизайне Тьюринга неявно заложена концепция хранения программы, которая изменяет данные вместе с данными, которые она изменяет. Это указывало на возможность создания универсальных и перепрограммируемых компьютеров. Современные компьютеры обычно являются универсальными машинами Тьюринга в том смысле, что их можно запрограммировать для выполнения любого алгоритма. Это устранило необходимость в различном оборудовании для каждой потенциальной компьютерной программы и ввело различие между аппаратным и программным обеспечением.

Модель машины Тьюринга непосредственно привела к изобретению компьютеров, но это не тот проект, который используется при проектировании современных компьютеров. Архитектура фон Неймана, используемая в качестве чертежа для современных компьютеров, использует концепцию хранимой программы, неявную в модели машины Тьюринга, но отличается от остальной части модели машины Тьюринга по нескольким важным аспектам. Самые большие различия заключаются в том, что архитектура фон Неймана не использует головку чтения-записи и вместо этого включает несколько регистров, оперативную память, шины данных, небольшой набор базовых машинных инструкций и возможности обработки нескольких битов. Архитектура фон Неймана также явно допускает использование специализированных устройств ввода и вывода, таких как клавиатуры и мониторы.

Модель машины Тьюринга была первой математической моделью вычислений. Это привело непосредственно к изобретению физических компьютеров. Физические компьютеры имеют все те же возможности, что и машины Тьюринга, при условии ограниченной памяти и временных ограничений на фактические вычисления. Формулировка Тьюринга по-прежнему играет центральную роль в изучении вычислений. Ученые-информатики все еще активно занимаются исследованием того, могут ли определенные функции вычислить машины Тьюринга.

(1 оценок, среднее: 5,00 из 5)

Загрузка...