ВУЗ:
Составители:
Пусть все перерабатываемые алгоритмом Г условия сведены в
последовательность и пронумерованы целыми числами: А
0
, А
1
, …, А
n
.
Множество решений объединим в последовательность В
0
, В
1
, …, В
m
.
Мы можем теперь сказать, что любой алгоритм, перерабатывающий
запись А
n
в В
m
, сводится к вычислению значений числовой функции )(nym
=
,
в которой (после перенумерации) мы можем иметь дело только с номерами
записей и решений, т.е. алгоритм перерабатывает номер записи условий в
номер записи решений. Иначе говоря, мы имеем уже не логический, а
численный алгоритм.
Очевидно, что если есть некоторый алгоритм, решающий исходную
задачу, то есть и алгоритм вычисления значений
соответствующей функции.
Действительно, чтобы найти значение y(n) при
*nn
=
, можно по n*
восстановить запись условий задачи. Затем с помощью имеющегося
алгоритма найти запись решения и по записи решения определить номер m*.
Следовательно,
**)( mny =
. Обратно, если есть алгоритм вычисления функции
y(n), то, стало быть, имеется и алгоритм решения исходной задачи.
Действительно, по записи условий задачи можно найти соответствующий ей
номер n*, затем вычислить и по m* определить запись решения.
Таким образом, возможность построения любого алгоритма сводится к
понятию вычислимости функции. Понятие вычислимости функции
можно
формализовать с помощью машин Тьюринга.
2. МАШИНЫ ТЬЮРИНГА
2.1. Состав и работа машины Тьюринга
Машина Тьюринга (МТ) состоит из устройства управления, головки и
бесконечной ленты.
Устройство управления способно принимать некоторое конечное
множество состояний. Лента разбита на ячейки, в которые заранее вносятся
обрабатываемые данные, записанные в символах некоторого алфавита (
в
Страницы
- « первая
- ‹ предыдущая
- …
- 23
- 24
- 25
- 26
- 27
- …
- следующая ›
- последняя »
