Введение в информационные системы. Брюхомицкий Ю.А. - 102 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

102
– текущее внутреннее состояние, α
1
– слово слева от головки, а α
2
– слово, об-
разованное символом под головкой и символами справа от него, причем слева
от α
1
и справа от α
2
нет непустых символов. Например, конфигурация с внут-
ренним состоянием q
i
, в которой на ленте записано abcde, а головка обозревает
d, запишется как abcqide. Стандартная начальная конфигурация – q
1
α. Стан-
дартная заключительная конфигурация – q
z
α. Ко всякой незаключительной
конфигурации К машины Т применима ровно одна команда вида (7.1), которая
переводит К в К' (обозначается K→K'). Если для К
1
и К
n
существует последова-
тельность конфигураций К
1
, К
2
, … , К
n
, такая, что K
1
→K
2
→…→K
n
, то это обо-
значается как K⇒K
n
. Последовательность конфигураций К
1
→К
2
→К
3
→… одно-
значно определяется исходной конфигурацией К
1
и полностью описывает рабо-
ту машины Т, начиная с К
1
. Она конечна, если в ней встретится заключительная
конфигурация, и бесконечна в противном случае.
Пример 7.2.а. Машина с алфавитом А={1, λ}, состояниями {q
1
, q
z
} и
системой команд q
1
1→q
1
1R, q
1
λ→ q
1
1R из любой начальной конфигурации бу-
дет работать бесконечно, заполняя единицами всю ленту вправо от начальной
точки.
Пример 7.2.б. Для любой машины Т, если К
1
=>К
i
=>К
j
и К
i
=К
j
, последо-
вательность К
1
⇒К
i
⇒К
j
⇒... является бесконечной: ее отрезок К
i
⇒К
j
будет по-
вторяться (зациклится).
Если α
1
q
1
α
2
⇒β
1
q
z
β
2
, то машина Т перерабатывает слово α
1
α
2
в слово
β
1
β
2
(обозначается Т(α
1
α
2
)=β
1
β
2
).
При использовании машины Т возникает вопрос: для всех ли алгорит-
мических процедур можно строить реализующие их машины Т? Утвердитель-
ный ответ на этот вопрос содержится в тезисе Тьюринга, который формулиру-
ется так: «Всякий алгоритм может быть реализован машиной Тьюринга». Этот
тезис доказать нельзя, поскольку само понятие алгоритма является неточным.
По
существу тезис Тьюринга связывает теорию с объектами, для описания ко-
торых она и была создана.
Подтверждением тезиса Тьюринга является, во-первых, математическая
практика, а во-вторых, то обстоятельство, что описание алгоритма в терминах
любой другой известной алгоритмической модели может быть сведено к его
описанию в виде машины Тьюринга. Однако не следует
понимать тезис Тью-
ринга в том смысле, что вся теория алгоритмов может быть сведена к теории
машин Тьюринга.
Проблема остановки. В числе общих требований, предъявляемых к ал-
горитмам, упоминалось требование результативности. Наиболее радикальной
формулировкой здесь было бы требование, чтобы по любому алгоритму А и
данным α можно было определить, приведет
ли работа А при исходных данных
α к результату или нет. В силу тезиса Тьюринга эту задачу можно сформулиро-
вать как задачу о возможности построении машины Т
0
, которая для любой ма-
шины Т и любых исходных данных α могла бы останавливаться.

Страницы