Введение в схемы, автоматы и алгоритмы



             

Тезис Тьюринга-Черча и алгоритмически неразрешимые проблемы - часть 2


В качестве доводов в пользу тезиса Тьюринга-Черча можно также рассматривать замкнутость класса машин Тьюринга и ч.р.ф. относительно многочисленных естественных операций над алгоритмами и функциями. Отметим также, что тезис Тьюринга-Черча обращен и в будущее: он предполагает, что какие бы новые формальные определения алгоритмов ни были предложены (а таковыми, например, являются новые языки программирования), все они не выйдут из класса алгоритмов, задаваемых машинами Тьюринга.

Чтобы показать связь теории алгоритмов с "практическим" программированием, рассмотрим некоторые алгоритмичские проблемы, связанные со структурированными программами.

Зафиксируем конечный алфавит A={a0, a1,…, am-1}, включающий все символы латинского алфавита, цифры, знак пробела (пусть это будет a0), знаки ';', '=', '<', ':=' , а также знаки-ключевые слова если, то, конец, пока, делай и все. Тогда каждая структурированная программа ? представляет собой некоторое слово

w_{\Pi}=a_{i_1}a_{i_2}\ldots a_{i_k}
в алфавите A. Не ограничивая общности, будем считать, что это слово начинается не с пробела, т.е. i1 >0. Тогда слово w? однозначно определяет натуральное число n?, m-ичной записью которого оно является, т.е.
n_{\Pi}=\sum_{j=1}^k i_j m^{k - j}.
Назовем это число номером программы ?. По тексту программы ? ее номер n? определяется однозначно. Рассмотрим теперь обратное соответствие. Конечно, не каждое число является номером некоторой структурированной программы. Поэтому сопоставим каждому числу n
N структурированную программу ?n следующим образом: если n=n? для некоторой программы ?, то ?n=?, иначе, т.е. когда n не является "естественным" номером никакой программы, сопоставим ему в качестве ?n

некоторую никогда не останавливающуюся программу P (например, программу ?5(1): x1 := x1; пока x1=x1 делай x1:=x1 все из примера 7.5).




Содержание  Назад  Вперед