Новосибирский государственный университет

Факультет информационных технологий

ICT SBRAS
А.М.Федотов

Словарь терминов в коллекции "Современные проблемы информатики" & "Вычислительные системы"

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

Синонимы: Машина Тьюринга-Поста; Машина Тьюринга; Машина Поста;

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

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

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

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

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

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

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

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

  1. Процедурный язык

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

  1. Пост Эмиль Леон
  2. Тьюринг Алан

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


Контекстный поиск: Задайте образец для поиска:

|Головная| |Преподавание| | Современные проблемы информатики| |Информатика| |Ключевые термины| |Персоны|

Федотов Анатолий Михайлович
[SBRAS]
НГУ
ФИТ НГУ
ИВТ СО РАН
© 1998-2019, Новосибирский государственный университет, Новосибирск
© 1998-2019, Институт вычислительных технологий СО РАН, Новосибирск
© 1998-2019, Федотов А.М.
    Дата последней модификации: 12.09.2016