СУЭБ ИВТ СО РАН

Словарные статьи в коллекции: (public_cat = Thesaurus of Information Technology: Dictionary Articles )

Машина Тьюринга-Поста

Машина Тьюринга-Поста (МТ) - абстрактный универсальный исполнитель, предложенный в 1936 году Аланом Тьюрингом из Кембриджского университета (и независимо от него для Эмилем Постом)формализации понятия алгоритма.

Абстрактность заключается в том, что исполнитель представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину.
Универсальность говорит о том, что данный исполнитель способен имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.

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

Программы записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает управляющее устройство в ячейке, и его внутренне состояние определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.

Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:

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

Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:

Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
Перемещаться влево и вправо по ленте.
Менять свое внутреннее состояние.

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

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

Ключевые термины, связанные с термином : "Машина Тьюринга-Поста":

Ссылка на персон:

Пост Эмиль Леон

Ключевые термины публикации: Архитектура фон Неймана; Вычислительная машина; алгоритм;

© 2013-2024, Евразийский национальный университет им. Л.Н.Гумилева, Астана
© 2007-2024, Новосибирский государственный университет, Новосибирск
© 1998-2024, Институт вычислительных технологий СО РАН, Новосибирск
© 1998-2024, Федотов А.М.

ФИТ НГУ НГУ
ЕНУ им.Гумилева
ИВТ СО РАН

Дата последней модификации: 29.11.2013