Методика Флойда

1. Для контроля за ходом вычислений выбираются, так называемые, контрольные дуги. К числу контрольных обязательно относят входную дугу и все выходные дуги, а также некоторое количество других дуг так, чтобы в блок-схеме алгоритма оказались “разрезанными” все циклы.

2. Для каждой контрольной дуги формулируется индуктивное условие, которому предположительно должно удовлетворять содержимое памяти алгоритма при каждом его прохождении через рассматриваемую дугу. Считаем, что все контрольные дуги и соответствующие им индуктивные утверждения пронумерованы.

3. Рассматриваются все пути от точки к точке не содержащие других точек. По индукции доказывается, что “Если при очередном проходе через точку i выполнялось индуктивное предположение P_i и если реализуется рассматриваемый путь, то при достижении точки _j будет выполняться условие P_j ”.

1. Элементарные Тьюринговы программы: l,r,a.

2. Бинарные распознающие программы (рисунок) («да/нет» выходы)

3. Охраняемая программа (Если P)T (рисунок) (все «да» на вход Т)

4. (Пока Р)Т

5. Т(делай Р) выходы «нет» Р идут на вход Т

6. Последовательное соединение Т1,Т2,Т3 => [Т1,Т2,Т3]

7. Ú _{j = 1…(n)} (Если Pi)Ti (рисунок)

Упорядоченный набор из n слов в алфавите А называется n -местным набором над А. Множество всех n -местных наборов над А обозначим через (A *) ⁿ.

Любое подмножество R множества (A *) ⁿ называется n -местным словарным отношением(предикатом).

Результатом работы программы T при входном псевдослове X называется псевдослово T (x), которое появляется на ленте в момент остановки программы; если программа работает бесконечно, то результат не определен.

Программу, которая в процессе работы над любым псевдословом X не сдвигает головку левее пробела, расположенного слева от n -го слова псевдослова X, будем назвать n -программой.

Словарное n-местное отношение R называется полуразрешимым, если существует n -программа T, которая останавливается в точности на всех псевдословах, имеющих вид

X # u_n # u_{n -1}#...# u ₁ где (u ₁, u ₂,…. u_n) R. (На всех остальных наборах работает бесконечно долго)

Словарное n -местное отношение R называется разрешимым, если R и (A *) ⁿ \ R полуразрешимы.

Дата добавления: 2015-08-31