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

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

ICT SBRAS

Словарь-справочник по информатике (онтология информатики)

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

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

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

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

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

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

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

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

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

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

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

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

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

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


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

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

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