Дискретная математика. Кулаков Ю.В - 49 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

Перемещение в данный такт работы происходит либо на одну клетку вправо (П), либо на одну клетку
влево (Л), либо может отсутствовать (Н).
В каждый такт работы управляющая головка совершает следующие дейст-
вия: 1) считывает символ m
i
, находящийся в клетке ленты, которую в этом такте она «видит»; 2) в соот-
ветствии со считанным символом m
i
и своим состоянием s
j
записывает символ m
i
в эту клетку; 3) дви-
жется или не движется вдоль ленты; 4) переходит в следующее состояние s
p
.
Всю работу машины можно задать с помощью функциональной таблицы Т,
в клетках которой стоят тройки вида m
k
s
p
d
l
, где d
l
∈ D – символ, определяющий перемещение. Таким
образом, функциональная таблица определяет отображение M × S в M × S × D. Содержательный смысл
отображения (m
i
, s
j
) → (m
k
, s
p
, d
l
) состоит в том, что, находясь в состоянии s
j
и считывая из клетки сим-
вол m
i
, управляющая головка записывает в данную клетку ленты символ m
k
, переходит в состояние s
p
и
производит движение, определяемое символом d
l
. Условимся считать, что таблица Т всегда устроена
так, что имеет место отображение (m
i
, s
0
) → (m
i
, s
0
, Н). Это означает, что в «выключенном» состоянии
машина не работает.
До начала функционирования машины следует заполнить (если это необхо-
димо) некоторые клетки ленты символами, отличными от m
0
, перевести УГ в состояние, отличное от s
0
,
и задать ее исходное положение относительно ленты. После этого машина будет функционировать в
соответствии с таблицей Т. Функционирование машины можно задать и с помощью графа, вершины ко-
торого взаимно однозначно соответствуют состояниям этого устройства, дуги – переходам из одного
состояния в другое, при этом каждая дуга (s
j
, s
p
) взвешена парой (m
i
, m
k
d
l
).
Описанное гипотетическое устройство называется по имени английского
математика машиной Тьюринга.
Приведем интуитивное (наивное) определение алгоритма. Совокупность
правил, обладающих свойствами массовости (инвариантности относительно входной информации),
детерминированности (однозначности применения этих правил на каждом шаге), результативности
(получения после применения этих правил информации, являющейся результатом) и элементарности
(отсутствии необходимости дальнейшего уточнения правил), называется алгоритмом.
Тезис Тьюринга. Для любого алгоритма, понимаемого в интуитивном
смысле, можно построить машину Тьюринга, функционирование которой эквивалентно этому алго-
ритму.
Понятие машины Тьюринга является строгим уточнением интуитивного по-
нятия алгоритма и позволяет решить вопрос алгоритмической (машинной) разрешимости той или иной
проблемы.
Проблема является алгоритмически неразрешимой, если не существует ал-
горитма (соответствующей машины Тьюринга) для ее решения. Заметим, что отдельная машина Тью-
ринга может быть представлена как программа произвольного вида для цифровой вычислительной ма-
шины с потенциально бесконечной памятью.
ОТВЕТЫ К ЗАДАЧАМ И УПРАЖНЕНИЯМ
Глава 1
1. а) {∅, {a}, {b}, {a, b}}; б) {∅, {b}, {c}, {d}, {b, c}, {b, d}, {c, d}, {b, c, d}}; в) {∅, {1}, {2}, {1,
2}}; г) {∅, {2}, {3}, {4}, {2, 3}, {2, 4}, {3, 4}, {2, 3, 4}}.
2.
3.
A
B
C
1
A
B
C
1
A
B
C
1
A
B
C
1
а) б) в) г)

Страницы