ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 31.03.2021
Просмотров: 6587
Скачиваний: 50
46
ки, а затем нанести метку.
Программа, добавляющая к числу метку слева, имеет вид:
Программа, добавляющая к числу метку справа, имеет вид:
(отличие только в направлении движения головки в первой команде. Проверьте работоспособ-
ность этих программ на каких-либо частных примерах).
Предположим, что головка расположена на расстоянии нескольких клеток слева от числа, к
которому нужно прибавить единицу. В этом случае программа усложняется. Появится «блок по-
иска числа» - две команды, приводящие головку в состояние, рассмотренное в предыдущем при-
мере:
Ниже - полные тексты программ, добавляющие единицу слева и справа, соответственно:
В первом случае не нужно перемещать головку к крайней левой метке числа
4. Приведем программу для сложения целых неотрицательных чисел а и и на машине По-
ста, когда головка находится над числом
а,
а число
b
находится правее числа
а
на некоторое число
клеток. Эта программа реализует следующий алгоритм: первое число постепенно придвигается ко
второму до их слияния, а потом стирается одна метка (иначе результат оказался бы на единицу
больше правильного).
47
В случае более сложных начальных условий, когда неизвестно, справа или слева от головки
(и на какое число клеток) находится число, можно применить такой принцип поиска числа: двигая
головку вправо и влево и отмечая метками степень удаления головки от исходного положения,
найти число, а потом уже применить известную программу сложения. При этом проверяется, на-
ходится ли головка над одной из меток числа и если да, то задача решена. Иначе проверяется, пус-
та ли секция справа от головки и следующая за ней; если обе пусты, то делается возврат головки
на один шаг и ставится метка, а затем такая же операция выполняется слева и по отмеченной до-
рожке головка возвращается вправо и т.д. до тех пор, пока головка не натолкнется на число, после
чего можно применить ранее рассмотренные выше программы:
Машину Поста можно рассматривать как упрощенную модель ЭВМ. В самом деле, как
ЭВМ, так и машина Поста имеют:
• неделимые носители информации (клетки - биты), которые могут быть заполненными или
незаполненными;
• ограниченный набор элементарных действий - команд, каждая из которых
выполняется за один такт (шаг).
Обе машины работают на основе программы. Однако, в машине Поста информация распо-
лагается линейно и читается подряд, а в ЭВМ можно читать информацию по адресу; набор команд
ЭВМ значительно шире и выразительнее, чем команды машины Поста и т.д.
73. МАШИНА ТЬЮРИНГА
48
Машина Тьюринга подобна машине Поста, но функционирует несколько иначе.
Машина Тьюринга (МТ) состоит из счетной ленты (разделенной на ячейки и ограниченной
слева, но не справа), читающей и пишущей головки, лентопротяжного механизма и операционного
исполнительного устройства, которое может находиться в одном из дискретных состояний
qo, q
1
,
..., q
s
,
принадлежащих некоторой конечной совокупности (алфавиту внутренних состояний). При
этом
q
о
называется начальным состоянием.
Читающая и пишущая головка может читать буквы рабочего алфавита
А = [а
0
, a
1
,
...,
а
t
},
стирать их и печатать. Каждая ячейка ленты в каждый момент времени занята буквой из множест-
ва
А.
Чаще всего встречается буква
a
0
- «пробел». Головка находится в каждый момент времени
над некоторой ячейкой ленты -текущей рабочей ячейкой. Лентопротяжный механизм может пере-
мещать ленту так, что головка оказывается над соседней ячейкой ленты. При этом возможна си-
туация выхода за левый край ленты (ЛК), которая является аварийной (недопустимой), или ма-
шинного останова (МО), когда машина выполняет предписание об остановке.
Порядок работы МТ (с рабочим алфавитом
a
0
,
a
1
,...,
а
t
и состояниями
q
0
,
q
1
,..., q
s
)
описыва-
ется таблицей машины Тьюринга. Эта таблица является матрицей с четырьмя столбцами и (
s
+ 1)
(
t
+ 1) строками. Каждая строка имеет вид
Здесь через
v
ij
обозначен элемент объединения алфавита
{а
0
, а
1
,..., а
t
}
и множества предпи-
саний для лентопротяжного механизма:
l
- переместить ленту влево,
r -
переместить ленту вправо,
s
-
остановить машину;
v
ij
- действие МТ, состоящее либо в занесении в ячейку ленты символа ал-
фавита
a
0
,
а
1
, ..., а
t
,
либо в движении головки, либо в останове машины;
q
ij
является последующим
состоянием.
МТ работает согласно следующим правилам: если МТ находится в состоянии
q
i
,
головка
прочитывает символ 0 в рабочей ячейке. Пусть строка
q
i
а
j
v
ij
q
ij
,
начинающаяся с символов
q
i
,
a
j
,
встречается только один раз в таблице. Если
v
ij
- буква рабочего алфавита, то головка стирает со-
держимое рабочей ячейки и заносит туда эту букву. Если
v
ij
-
команда
r
или
l
для лентопротяжного
механизма, то лента сдвигается на одну ячейку вправо или влево (если не происходит выход за ле-
вый край ленты) соответственно. Если
v
ij
=s,
то происходит машинный останов.
Машина Тьюринга начинает работу из некоторой начальной конфигурации, включающей в
себя начальное состояние (обычно
q
0
)
и положение считывающе-записывающей головки над оп-
ределенной ячейкой ленты, содержащей один из символов рабочего алфавита A.
Отметим, что наличие разнообразных символов в рабочем алфавите МТ позволяет пред-
ставлять на ленте произвольную текстовую и числовую информацию, а переходы управляющего
центра МТ в различные состояния моделируют запоминание машиной Тьюринга промежуточных
результатов работы. Таблица, определяющая порядок работы МТ, не является в прямом смысле
слова программой (ее предписания выполняются не последовательно, одно за другим, а описыва-
ют преобразования символов некоторого текста, находящегося на ленте). Таблицу МТ часто назы-
вают схемой машины Тьюринга или попросту отождествляют с самой машиной Тьюринга, коль
скоро ее устройство и принцип функционирования известны.
Рассмотрим примеры нескольких схем машины Тьюринга.
1. Алгоритм прибавления единицы к числу
п
в десятичной системе счисления. Дана деся-
тичная запись числа
п
(т.е. представление натурального числа
п
в десятичной системе счисления);
требуется получить десятичную запись числа
п
+ 1.
Очевидно, что внешний алфавит МТ должен состоять из десяти цифр 0,1,2,3,4,5,6,7,8,9 и
символа пробела _. Эти цифры записывают по одной в ячейке (подряд, без пропусков).
Оказывается достаточным иметь два внутренних состояния машины:
q
1
и
q
2
.
Предположим, что в начальный момент головка находится над одной из цифр числа, а ма-
шина находится в состоянии
q
1
.
Тогда задача может быть решена в два этапа: движения головки к
цифре единиц числа (во внутреннем состоянии
q
1
)
и замене этой цифры на единицу большую (с
учетом переноса 1 в следующий разряд, если это 9, во внутреннем состоянии
q
2
.
Соответствующая
схема МТ может иметь вид
49
а
i
q
i
q
1
q
2
0
0П
q
1
1C
q
2
1
1П
q
1
2C
q
2
2
2П
q
1
3C
q
2
3
3П
q
1
4C
q
2
4
4П
q
1
5C
q
2
5
5П
q
1
6C
q
2
6
6П
q
1
7C
q
2
7
7П
q
1
8C
q
2
8
8П
q
1
9C
q
2
9
9П
q
1
0C
q
2
-
-Л
q
1
1C
q
2
2. Алгоритм записи числа в десятичной системе счисления.
Дана конечная последовательность меток, записанных в клетки ленты подряд, без пропус-
ков. Требуется записать в десятичной системе число этих меток пересчитать метки).
Суть алгоритма может состоять в том, что к числу 0, записанному на ленте в начале работы
машины, машина добавляет 1, стирая метку за меткой, так что вместо нуля возникает число 0 +
k.
Легко могут быть построены алгоритмы сложения чисел, их перемножения, нападения наи-
большего общего делителя и т.д. Однако, главная цель введения машин Поста и Тьюринга не про-
граммирование для них, а изучение свойств алгоритмов и проблемы алгоритмической разрешимо-
сти задач.
В зависимости от числа используемых лент, их назначения и числа состояний устройства
управления можно рассматривать различные модификации машин Тьюринга.
Предположим, мы расширили определение МТ, добавив определенное состояние
q.
устрой-
ства управления машины. Будем говорить, что если устройство управления переходит в состояние
q
0
для заданного входного слова
х,
то машина допускает
х;
если устройство переходит в состояние
q
x
, то машина запрещает
х.
Такую машину будем называть машиной Тьюринга с двумя выходами.
Могут быть рассмотрены многочисленные варианты машины Тьюринга, имеющие некоторое ко-
нечное число лент. В каждой клетке этих лент может находиться один из символов внешнего ал-
фавита
А
= {
a
0
, a
1
, ...,
а
n
}.
Устройство управления машиной в каждый момент времени находится в
одном из конечного множества состояний
Q
=
{q
0
, q
1
, ..., q
m
}.
Для
K
-ленточной машины конфигу-
рация ее в
i
-й момент времени описывается системой
k
-слов вида:
a
il1
… a
ill
q
i
a
ill+1
… s
i1t
;
a
ik1
… a
ikl
q
i
a
ikl+1
…a
ikv
;
первый индекс соответствует моменту времени, второй - номеру ленты, третий -номеру клетки,
считая слева направо. Говорят, что машина выполняет команду
q
i
a
a1
… a
ak
→ q
j
a
b1
k
1
… a
bk
k
k
,
К = {Л, С, П}.
Если, находясь в состоянии
q
i
и обозревая ячейки с символами
a
a1
—
a
аk
,
машина переходит
в состояние
q
j
,
заменяя содержимое ячеек соответственно символами
а
b1
— а
bк
,
то после этого лен-
ты соответственно сдвигаются в направлениях
k
1
... k
k
.
До сих пор принималось, что различные алгоритмы осуществляются на различных маши-
нах Тьюринга, отличающихся набором команд, внутренним и внешним алфавитами. Однако,
можно построить универсальную машину Тьюринга, способную выполнять любой алгоритм лю-
бой машины Тьюринга. Это достигается путем кодирования конфигурации и программы любой
данной машины Тьюринга в символах внешнего алфавита универсальной машины. Само кодиро-
вание должно выполняться следующим образом:
1) различные символы должны заменяться различными кодовыми группами, но один и тот
же символ должен заменяться всюду, где бы он не встретился, одной и той же кодовой группой;
50
2) строки кодовых записей должны однозначно разбиваться на отдельные кодовые группы;
3) должна иметься возможность распознать кодовые группы, соответствующие командам
Л, П, С,
различать кодовые группы, соответствующие символам внешнего алфавита и внутренним
состояниям.
Для сравнения структур различных машин и оценки их сложности необходимо иметь соот-
ветствующую меру сложности машин. К.Шеннон предложил рассматривать в качестве такой меры
произведение числа символов внешнего алфавита и числа внутренних состояний. Большой инте-
рес вызывает задача построения универсальной машин Тьюринга наименьшей сложности.
Может быть рассмотрено еще одно обобщение машин Тьюринга: их композиции. Операции
композиции, выполняемые над алгоритмами, позволяют образовывать новые, более сложные ал-
горитмы из ранее известных простых алгоритмов. Поскольку машина Тьюринга - алгоритм, то
операции композиции применимы и к машинам Тьюринга. Рассмотрим основные из них: произве-
дение, возведение в степень, итерацию.
Пусть заданы машины Тьюринга
T
1
и
T
2
, имеющие общий внешний алфавит
А
= {
a
0
,
a
1
, ...,
a
m
} и внутренние состояния
Q
1
=
{
q
0
, q
1
,… q
n
} и
Q
2
=
{q
0
, q
1
,
...,
q
t
}
соответственно. Композицией
или произведением машины
T
1
и машины
T
2
будем называть машину
Т
с тем же внешним алфави-
том
А = {a
0
, а
1
, ...,
a
m
} и набором внутренних состояний
Q
=
{q
0
, q
1
,..., q
2
,,
q
n+1
,...,
q
n+1
} и програм-
мой, эквивалентной последовательному выполнению программ машин
Т
1
и
Т
2
:
Т =
T
1
*
T
2
..
Таким же образом определяется операция возведения в степень:
n
-й степенью машины
Т
называется произведение
T
...
Т
c
n
сомножителями.
Операция итерации применима к одной машине и определяется следующим образом. Пусть
машина
T
1
имеет несколько заключительных состояний. Выберем ее
r-е
заключительное состоя-
ние и отождествим его в схеме машины с ее начальным состоянием. Полученная машина
T
явля-
ется результатом итерации машины
Т
1
: Т = T
1
.
Прежде чем остановиться на проблеме алгоритмической разрешимости задач обратимся к
другим способам формализации понятия алгоритма.
7.4. НОРМАЛЬНЫЕ АЛГОРИТМЫ МАРКОВА
Для формализации понятия алгоритма российский математик А.А.Марков предложил ис-
пользовать ассоциативные исчисления.
Рассмотрим некоторые понятия ассоциативного исчисления. Пусть имеется алфавит (ко-
нечный набор различных символов). Составляющие его символы будем называть буквами. Любая
конечная последовательность букв алфавита (линейный их ряд) называется словом в этом алфави-
те.
Рассмотрим два слова
N
и
М
в некотором алфавите
А.
Если
N
является частью
М,
то гово-
рят, что
N
входит в
М.
Зададим в некотором алфавите конечную систему подстановок
N - М, S - Т,...,
где
N, М, S,
Т,... -
слова в этом алфавите. Любую подстановку
N-M
можно применить к некоторому слову
К
следующим способом: если в
К
имеется одно или несколько вхождений слова
N,
то любое из них
может быть заменено словом
М,
и, наоборот, если имеется вхождение
М,
то его можно заменить
словом
N.
Например, в алфавите
А = {а, b, с}
имеются слова
N
=
ab, М = bcb, К = abcbcbab,
Заменив в
слове
К
слово
N
на
М,
получим
bcbcbcbab
или
abcbcbbcb,
и, наоборот, заменив
М
на
N,
получим
aabcbab
или
аbсаbаb.
Подстановка
ab - bcb
недопустима к слову
bacb,
так как ни
ab,
ни
bcb
не входит в это слово.
К полученным с помощью допустимых подстановок словам можно снова применить допустимые
подстановки и т.д. Совокупность всех слов в данном алфавите вместе с системой допустимых
подстановок называют
ассоциативным исчислением.
Чтобы задать ассоциативное исчисление,
достаточно задать алфавит и систему подстановок.
Слова
P
1
и
Р
2
в некотором ассоциативном исчислении называются смежными, если одно из
них может быть преобразовано в другое однократным применением допустимой подстановки.