Избранное
ЭБ Нефть
и Газ
Главная
Оглавление
Поиск +
Еще книги ...
Энциклопедия
Помощь
Для просмотра
необходимо:


Книга: Главная » Варпаховский Ф.Л. Элементы теории алгоритмов
 
djvu / html
 

которого алфавита Л. Поставим теперь в соответствие каждому слову, кодирующему какую-нибудь из данных задач, слово, кодирующее решение этой задачи. Тем самым на подмножестве множества слов алфавита А будет определена функция, значениями которой также будут слова алфавита А. Область определения этой функции совпадает с множеством слов, кодирующих данные задачи, а множество значений — с множеством слов, кодирующих решения этих задач. Поэтому алгоритм можно понимать как единый способ, позволяющий в конечное число шагов «вычислять» значения построенной функции для любых значений аргумента из ее области определения.
Рекомендуем читателю, освоившись с приведенным описанием, еще раз внимательно просмотреть примеры, приведенные ранее. При этом полезно уяснить, о каком именно бесконечном множестве задач идет речь в каждом примере, как обосновывается конечность применяемой процедуры и т. д.
Упражнение 5. Бесконечное множество задач, о котором говорится в описании алгоритма, на самом деле счетно. Почему?
§ 2. МАШИНЫ ТЬЮРИНГА И ТЕЗИС ЧЕРНА
В этом параграфе будет изучен один важный специальный класс алгоритмов, так называемые машины Тьюринга. Рассматриваемый здесь вариант машины является некоторой модификацией первоначального варианта, предложенного английским ученым Тьюрингом.
Машина Тьюринга включает в себя ленту, бесконечную в обе стороны и разбитую на ячейка, в каждой из которых записана ровно одна буква алфавита А = = {0о, 01, . . • , 0п} (я^1), называемого алфавитом машины. Предполагается, что машина может находиться в одном из конечного числа состояний <7о, <7ь • • • , <7ь (&^1)и что в каждый момент времени машина «обозревает» в точности одну ячейку ленты.
Машина может совершать следующие элементарные действия: 1) изменить свое состояние и Заменить букву обозреваемой ею ячейки ленты на любую другую букву своего алфавита; 2) изменить свое состояние и передвинуться на одну ячейку вправо, т. е. начать обозревать ближайшую справа ячейку ленты; 3) изменить свое со-
Ю

 

1 10 11 12 13 14 15 16 17 18 19 20


Математика