Машины Тьюринга

Машина Тьюринга — это абстрактное устройство с конечным управлением и неограниченной лентой, которое воплощает интуитивное понятие алгоритма и служит стандартной эталонной моделью для определения того, что является вычислимым.

Definition

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

Scope

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

Core questions

• Как простое устройство чтения-записи-перемещения охватывает полное понятие алгоритма?
• Почему многие варианты модели вычисляют одни и те же функции?
• Что такое универсальная машина и почему ее существование значимо?
• Как кодирование машин в виде строк позволяет доказывать их собственное поведение?

Key theories

Универсальность

Существует одна универсальная машина Тьюринга, которая, получив кодировку любой машины и ее входные данные, имитирует вычисления этой машины, предвосхищая компьютер с хранимой программой, в котором программы сами являются данными.

Устойчивость модели

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

Clinical relevance

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

History

Тьюринг представил свои машины в 1936 году, чтобы точно определить, что означает вычислимость числа, и решить проблему разрешимости Гильберта. Идея универсальной машины, в которой хранимое описание управляет общим устройством, повлияла на разработку фон Нейманом компьютера с хранимой программой десятилетие спустя.

Key figures

• Alan Turing
• Emil Post
• John von Neumann

Seminal works

• turing1937
• sipser2013

Frequently asked questions

Является ли машина Тьюринга настоящим компьютером?

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

Почему универсальная машина Тьюринга важна?

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