ВУЗ:
Составители:
103
Эта задача называется проблемой остановки. Для ее решения доказана
теорема, согласно которой не существует машины Т
0
, решающей проблему ос-
тановки для произвольной машины Т. Это один из примеров алгоритмически
неразрешимой проблемы остановки.
Следует однако помнить, что речь идет об отсутствии единого алгорит-
ма, решающего данную проблему. При этом не исключается возможность ре-
шения этой проблемы в частных случаях, но различными средствами для каж-
дого случая. В
частности, теорема не исключает того, что для отдельных клас-
сов машин Т проблема остановки вполне разрешима.
Неразрешимость проблемы остановки можно интерпретировать также
как отсутствие общего алгоритма для отладки программ, т.е. алгоритма, кото-
рый по тексту любой программы и данным для нее определял бы, зациклится ли
программа на этих данных или
нет. С учетом сделанного замечания, такая ин-
терпретация не противоречит тому эмпирическому факту, что большинство
программ в конце концов удается отладить, т. е. установить и устранить причи-
ну зацикливания.
Формы описания алгоритмов. В примере 7.1 описание алгоритма зада-
ется вербально. Это одна из возможных форм. Рассмотрим другую форму пред-
ставления алгоритма.
Пусть алгоритм направлен на преобразование информации, представ-
ляемой дискретными величинами X
1
, X
2
, . . ., Х
m
, каждая из которых в любой
момент времени имеет единственное значение из множества x
1
i
, x
2
i
, . . ., х
ki
i
, где i
= 1, 2, . . ., т. Для преобразования информации назначим набор элементарных
операций {О
1
, О
2
, ... О
n
}. Любую операцию из этого множества будем обозна-
чать знаком *. Последовательность величин, объединенных знаками операций,
называется оператором. Величины, входящие в оператор, называются операн-
дами. Принято выделять следующие элементарные операторы: сингулярный
оператор *X
i
и бинарный оператор X
i
*X
j
. Оператор *X
i
определяет значение *x
l
i
,
получаемое применением операции к значению x
l
i
. Аналогично, оператор X
i
*X
j
определяет значение x
l
i
*x
l
j
. На основе элементарных операторов строятся более
сложные операторы вида X
i
*X
j
*…* X
k
.
Будем обозначать операторы, направленные на вычисление значений, в
виде A
1
, A
2
, A
3
, …, где индекс имеет смысл метки, выделяющей конкретный
оператор на множестве операторов. Некоторое действие по преобразованию
информации можно представить последовательностью операторов A
1
, A
2
, …, A
k
,
выполняемых дискретно в последовательные моменты времени в порядке их
записи. Выполнение оператора A
j
в последовательности операторов называется
j-м шагом реализации алгоритма. С последовательностью шагов связана после-
довательность значений {x
i
1
}, {x
i
2
}, . . ., {х
i
k
}, характеризующих состояние вели-
чин {X
i
} в моменты 1, 2, . . ., k.
Может оказаться, что выбор следующего реализуемого оператора зави-
сит от текущего состояния величин {X
i
}. Чтобы сделать выбор, в набор элемен-
тарных операций {О
1
, О
2
, ... О
n
} вводятся операции отношения, посредством
Страницы
- « первая
- ‹ предыдущая
- …
- 101
- 102
- 103
- 104
- 105
- …
- следующая ›
- последняя »
