96.Машины Тьюринга.Сложение
Приведем пример машины Тьюринга, выполняющей унарное сложение двух операндов. Операнды представляются в унар -ной системе, т. к. целое неотрицательное число n представляет ся n+1 единицей.
Табличное представление МТ
MT={
'k':1,
'start': '1pass',
'stop': 'q',
'program': {
#(Состояние, символы на лентах) -> (новое состояние, (действия по каждой ленте))
('1pass', ('1')): ('1pass', (('1','R'))), # проходим первое число
('1pass', ('*')): ('2pass', (('1','R'))), # меняем разделитель
('2pass', ('1')): ('2pass', (('1','R'))), # проходим второе число
('2pass', ('*')): ('del1', (('*','L'))), # конец второго числа
('del1', ('1')): ('del2', (('*','L'))), # удаляем первую лишнюю 1
('del2', ('1')): ('rewind',(('*','L'))), # удаляем вторую лишнюю 1
('rewind',('1')): ('rewind',(('1','L'))), # перематываем к началу.
('rewind',('*')): ('q', (('*','R'))) # конец.
}
}
Графовое представление МТ
Примеры
выполнения МТ «1» + «1»
96.Машины Тьюринга.Копирование
Копирование
-го
слова.Обозначение
|
Вход |
|
|
Выход |
|
|
Программа |
|
Машина Тьюринга представляет собой автомат, имеющий беско нечную в обе стороны ленту, считывающую головку и управ - ляющее устройство. Управляющее устройство может находи - ться в одном из состояний, образующих конечное множество Q = {q0, q1, ..., qn}. Множество Q называют внутренним алфа - витом машины Тьюринга. Принципиальное отличие машины Тьюринга от вычислительных машин состоит в том, что ее запо- минающее устройство представляет собой бесконечную ленту, из-за которой невозможна ее физическая реализация. Лента разделена на ячейки, в каждой из которых может быть записан один из символов конечного алфавита A = {a0, a1, . . . , am}, который называют входным алфавитом машины Тьюринга. Во время функционирования машины Тьюринга может быть запол- нено конечное число ячеек. Считывающая головка в каждый
момент времени обозревает ячейку ленты, в зависимости от символа в этой ячейке и состояния управляющего устройства записывает в ячейку новый символ или оставляет его без изме - нения, сдвигается на ячейку влево или вправо или остается на месте. При этом управляющее устройство переходит в новое состояние или остается в старом. Среди состояний управляю - щего устройства выделены начальное состояние q0 и заклю - чительное состояние qz. Таким образом, за один такт работы машина Тьюринга может считать символ, записать вместо него новый или оставить его без изменения и сдвинуть головку на одну ячейку влево или вправо или оставить ее на месте.
80.Типы вершин
Рассмотрим дерево
с
вершинами.
Назовем его концевые вершины вершинами
типа 1. Теперь
удалим все вершины типа 1 и концевые
ребра. В результате получим связный
граф без циклов
,
то есть опять дерево, но с уже меньшим
количеством вершин. Концевые вершины
дерева
назовем
вершинами
типа 2 в дереве
.
Аналогично определяются вершины типов
3, 4 и т. д. Легко видеть, что дерево может
иметь либо одну вершину максимального
типа, либо две таких вершины. Типы вершин
дерева
,
изображенного на рис. 4. 37, записаны рядом
с соответствующими вершинами. Здесь же
показаны последовательные этапы
процедуры, позволяющей их определить.
Это дерево имеет две вершины максимального
типа. Если у дерева
удалить
одну из вершин типа 2 и ребра, ей
инцидентные, то получившееся при этом
дерево будет иметь уже только одну
вершину максимального типа.
Пусть вершина типа k есть вершина максимального типа. Из определения типа вершин дерева следует, что эксцентриситет единственной вершины максимального типа равен ее типу, то есть равен k, а эксцентриситет каждой из двух вершин максимального типа равен k-1. При этом эксцентриситет любой вершины не максимального типа будет обязательно больше.