|
Новосибирский государственный университет
|
|
Машина Тьюринга-Поста
Синонимы: машина тьюринга-поста; машина тьюринга; машина поста;Машина Тьюринга-Поста (МТ) - абстрактный универсальный исполнитель, предложенный в 1936 году Аланом Тьюрингом из Кембриджского университета (и независимо от него для Эмилем Постом)формализации понятия алгоритма.
Абстрактность заключается в том, что исполнитель представляет собой логическую вычислительную конструкцию, а не реальную вычислительную машину.
Универсальность говорит о том, что данный исполнитель способен имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
Кроме того, предполагается, что универсальный исполнитель должен уметь доказывать существование или отсутствие алгоритма для той или иной задачи.
Машина Тьюринга состоит из бесконечной в обе стороны ленты (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделенной на ячейки, и управляющего устройства (автомата).
Программы записываются в виде таблицы, где первые столбец и строка содержат буквы внешнего алфавита и возможные внутренние состояния автомата (внутренний алфавит). Содержимое таблицы представляет собой команды для машины Тьюринга. Буква, которую считывает управляющее устройство в ячейке, и его внутренне состояние определяют, какую команду нужно выполнить. Команда определяется пересечением символов внешнего и внутреннего алфавитов в таблице.
Чтобы задать конкретную машину Тьюринга, требуется описать для нее следующие составляющие:
- Внешний алфавит: конечное множество, элементы которого называются буквами (символами). Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
- Внутренний алфавит: конечное множество состояний автомата. Одно из состояний должно быть начальным (запускающим программу). Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
- Таблица переходов: описание поведения автомата в зависимости от состояния и считанного символа.
Автомат машины Тьюринга в процессе своей работы может выполнять следующие действия:- Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).
- Перемещаться влево и вправо по ленте.
- Менять свое внутреннее состояние.
Команда для машины Тьюринга представляет собой конкретную комбинацию этих трех составляющих: указаний, какой символ записать в ячейку (над которой стоит автомат), куда передвинуться и в какое состояние перейти. Команда может содержать не все эти составляющие.
Машина Тьюринга называется детерминированной, если каждой комбинации состояния и ленточного символа в таблице соответствует не более одного правила. Если существует пара «ленточный символ - состояние», для которой существует две и более команд, такая машина Тьюринга называется недетерминированной.Ключевые термины, связанные с термином "машина тьюринга-поста":
- Процедурный язык
Ссылки на персон:
- Пост Эмиль Леон
- Тьюринг Алан
Ключевые термины: архитектура фон неймана; вычислительная машина; алгоритм;
|А.М.Федотов|
|Преподавание|
|Современные проблемы
информатики|
|Информатика|
|Ключевые термины|
|Персоны|
© 2007-2024, Новосибирский государственный университет, Новосибирск
© 1998-2024, Институт вычислительных технологий СО РАН, Новосибирск
© 1998-2024, Федотов А.М.
Дата последней модификации:
29.11.2013