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


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

Доказательство. Предположим, наоборот, что такой алгоритм существует. Тогда согласно тезису Чёрча функция \|)(а) должна быть вычислимой, т. е. существует вычисляющая ее машина Тьюринга с алфавитом {а0, |, ,. . . , at}. Эта машина должна каждое слово алфавита
переработать в слово того же алфавита (по определению функции ip(a)). Пусть k — какой-нибудь номер этой машины в нашей -нумерации. Посмотрим, чему равно слово if (| | . . . |). С одной стороны, это слово есть резуль-
""IS
тат переработки слова длины k алфавита Ai машиной с HOMeipOM k и поэтому оно равно р&. С другой же стороны, по самому определению функции г|э(а), это слово равно Р^|. Полученное противоречие доказывает теорему.
Хотя приведенное доказательство весьма просто, оно дает представление о методах, которые применяются для выяснения алгоритмической неразрешимости в значительно более сложных случаях.
Отметим еще, что алгоритмическая неразрешимость вовсе не означает невозможности решить ту или иную задачу из данной серии задач, а лишь отсутствие общего способа для решения всех задач данной серии. Это обстоятельство следует иметь в виду, с тем чтобы не принимать доказательства алгоритмической неразрешимости в качестве матемаТйнеского подтверждения философского тезиса о непознаваемости явлений.
§ 4. НОРМАЛЬНО ВЫЧИСЛИМЫЕ ФУНКЦИИ
Как уже было сказано, всякую алгоритмическую задачу можно понимать как задачу о вычислении значений некоторой функции, заданной в некотором алфавите. Когда возник вопрос о математическом уточнении понятия алгоритмически вычислимой функции, было предложено почти одновременно несколько различных определений, одним из которых является приведенное выше определение вычислимой функции по Тьюрингу. Другое важное определение — определение нормальна вычислимой функции — принадлежит советскому математику А. А. Маркову.
В этом параграфе рассматривается определение Маркова, разбираются некоторые примеры и выясняется связь между понятиями вычислимости и нормальной вычислимости.
20

 

1 10 20 21 22 23 24


Математика