Глоссарий учебного элемента
Алгоритм – это точное предписание о выполнении в некотором порядке системы операций, определяющих процесс перехода от исходных данных к искомому результату для решения задачи данного типа
Машина Тьюринга - абстрактная (воображаемая) "вычислительная машина" некоторого точно охарактеризованного типа, дающая пригодное для целей математического рассмотрения уточнение общего интуитивного представления об алгоритме
Управляющая головка – это некоторое устройство, которое может перемещаться вдоль ленты так, что в каждый рассматриваемый момент времени оно находится напротив определенной ячейки ленты
Внутренняя память машины – это выделенная ячейка памяти, которая в каждый рассматриваемый момент находится в некотором «состоянии».
Конфигурация машины Тьюринга – совокупность, образованная содержимым текущей обозреваемой ячейки aj и состоянием внутренней памяти Si.
Программа машины Тьюринга – совокупность команд установленного формата
Тезис Тьюринга – любой алгоритм можно преобразовать в машину Тьюринга
Глоссарий учебного элемента
Машина В эквивалентна машине А, если в соответствующие такты их работы лента машины В содержит всю информацию о ленте машины А.
Т.1.2.(1) Теорема Всякая k -ленточная машина Тьюринга М может быть преобразована в эквивалентную машину М* с одной лентой.
Самоанализирующие машины - это машины, в которых все служебные символы как-либо изображаются ленточными символами.
Универсальная машина – машина Тьюринга, обладающая способностью путём подходящего кодирования выполнить любое вычисление.
Глоссарий учебного элемента
Т.1.3.(1) Теорема Шеннона №1 Всякая машина Тьюринга А может быть преобразована в эквивалентную машину В не более чем с двумя внутренними состояниями.
Т.1.3.(2) Теорема Шеннона №2 Всякая машина Тьюринга А может быть преобразована в эквивалентную машину С не более чем с двумя знаками внешнего алфавита.
Нормальный алгоритм Маркова - математическое построение, предназначенное для уточнения понятия алгоритм, которое задается алфавитом и нормальной схемой подстановок, выполняемых по заранее определенной схеме.
Тезис Маркова: любой вычислительный процесс можно преобразовать в нормальный алгоритм
Глоссарий учебного элемента
Т.1.5.(1) Теорема Задача об остановке произвольной машины Тьюринга на произвольном входном слове алгоритмически неразрешима.
Т.1.5.(2) Теорема Задача об остановке произвольной машины Тьюринга на пустой ленте алгоритмически неразрешима.
Т.1.5.(3) Теорема (без доказательства) Задача об остановке конкретной универсальной машины на произвольной ленте специального типа алгоритмически неразрешима.
Т.1.5.(4) Теорема Задача о печатании данного символа на чистой ленте точно один раз алгоритмически неразрешима.
Т.1.5.(5)Теорема Задача о печатании данного символа на чистой ленте бесконечно много раз алгоритмически неразрешима.
Т.1.5.(6) Теорема Задача о печатании данного символа на чистой ленте хотя бы один раз алгоритмически неразрешима.
Две машины Тьюринга, имеющие один и тот же внешний алфавит, будем называть взаимозаменяемыми, если, каково бы ни было слово в их общем алфавите, не содержащее пустого символа, они либо перерабатывают его в одно и то же слово, либо обе к нему неприменимы.
Свойство машин Тьюринга называется инвариантным, если любые две взаимозаменяемые машины либо обе обладают этим свойством, либо обе не обладают.
Свойство машин Тьюринга называется нетривиальным, если существуют как машины, обладающие этим свойством, так и не обладающие им.
Т.1.5.(7) Теорема Райса (без доказательства) Ни для какого нетривиального инвариантного свойства машин Тьюринга не существует алгоритма, позволяющего для любой машины Тьюринга узнать, обладает ли она этим свойством.
Т.1.5.(8) Теорема Невозможно доказать алгоритмическую неразрешимость задачи об остановке конкретной машины Т0 на конкретном входящем слове t0.
Глоссарий учебного элемента
Эффективно перечислимым множеством называется множество, элементы которого можно перечислить по алгоритму (пронумеровать натуральным рядом без пропусков и повторений)
Подмножество В множества А эффективно распознается в А, если существует алгоритм, позволяющий однозначно для каждого элемента множества А определить, принадлежит ли данный элемент множеству В или дополнению В до А.
Т.1.5.(1) Теорема Поста Если множество А эффективно перечислимо, то подмножество В эффективно распознается в А тогда и только тогда, когда В и А\В оба эффективно перечислимы.
Т.1.5.(2) Теорема Множество машин Тьюринга эффективно перечислимо.
Т.1.5.(3) Теорема Множество алгоритмов Маркова эффективно перечислимо.
Т.1.5.(4) Теорема Множество останавливающихся машин Тьюринга эффективно перечислимо.
Т.1.5.(5) Теорема Множество не останавливающихся машин Тьюринга невозможно эффективно перечислить.