-
Машина Тьюринга.
Маши́на Тью́ринга (МТ) — aбстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
В состав машины Тьюринга входит неограниченная в обе стороны лента (возможны машины Тьюринга, которые имеют несколько бесконечных лент), разделённая на ячейки, и управляющее устройство (также называется головкой записи-чтения (ГЗЧ)), способное находиться в одном из множества состояний. Число возможных состояний управляющего устройства конечно и точно задано.
Управляющее устройство может перемещаться влево и вправо по ленте, читать и записывать в ячейки символы некоторого конечного алфавита. Выделяется особый пустой символ, заполняющий все клетки ленты, кроме тех из них (конечного числа), на которых записаны входные данные.
Управляющее устройство работает согласно правилам перехода, которые представляют алгоритм,реализуемый данной машиной Тьюринга. Каждое правило перехода предписывает машине, в зависимости от текущего состояния и наблюдаемого в текущей клетке символа, записать в эту клетку новый символ, перейти в новое состояние и переместиться на одну клетку влево или вправо. Некоторые состояния машины Тьюринга могут быть помечены как терминальные, и переход в любое из них означает конец работы, остановку алгоритма.
-
Нормальные алгоритмы Маркова.
Нормальный алгоритм Маркова— один из стандартных способов формального определения понятия алгоритма (другой известный способ — машина Тьюринга). Понятие нормального алгоритма введено А. А. Марковым (младшим) в конце 1940-х годов в работах по неразрешимости некоторых проблем теории ассоциативных вычислений. Традиционное написание и произношение слова «алгорифм» в этом термине также восходит к его автору, многие годы читавшему курс математической логики на механико-математическом факультете МГУ.
Нормальный алгоритм описывает метод переписывания строк, похожий по способу задания на формальные грамматики. НАМ является Тьюринг-полным языком, что делает его по выразительной силе эквивалентным машине Тьюринга и, следовательно, современным языкам программирования. На основе НАМ был создан функциональный язык программирования Рефал.
Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах.
Определение
всякого нормального алгоритма состоит
из двух частей: определения алфавита алгоритма
(к словам из символов которого алгорифм
будет применяться) и определения
его схемы.
Схемой нормального алгоритма называется
конечный упорядоченный набор так
называемых формул
подстановки, каждая из
которых может быть простой или заключительной.
Простыми формулами подстановки называются
слова вида 
,
где 
и 
—
два произвольных слова в алфавите
алгоритма (называемые, соответственно,
левой и правой частями формулы
подстановки). Аналогично, заключительными
формулами подстановки называются слова
вида 
,
где 
и 
—
два произвольных слова в алфавите
алгоритма. При этом предполагается, что
вспомогательные буквы 
и 
не
принадлежат алфавиту алгоритма (в
противном случае на исполняемую ими
роль разделителя левой и правой частей
следует избрать другие две буквы).
-
Способы композиции алгоритмов.
Способы композиции нормальных алгоритмов:
I. Суперпозиция алгоритмов. При суперпозиции двух алгоритмов слово первого алгоритма рассматривается как входное слово второго алгоритма B, результат суперпозиции C может быть представлен в виде C(p) и B(A(p)).
II. Объединение алгоритмов. Объединением алгоритмов А и B в одном и том же алфавите называется алгоритм Св том же алфавите, преобразующий любое слово p содержащееся в пересечении областей определения алгоритмов Аи В, в записаныe рядом слова А(р) и В(р).
III. Разветвление алгоритмов. Разветвление алгоритмов представляет собой композицию D трех алгоритмов A,В и С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмовА, В и С, а для любого слова р из этого пересечения D(p) = А(р), если С(р) = е, D(p) = B(p), если C(p) = е, где е - пустая строка.
IV. Итерация алгоритмов. Итерация (повторение) представляет собой такую суперпозицию С двух алгоритмовА и В, что для любого входного слова p соответствующее слово С(р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом B.