A0 q1 11. a0 |*

A0 q3 21. a0 *

A0 q2 2. a0 |*

A0 q2 12. a0 |*

A0 q3 22. a0 *

A0 q3 3. a0 |*

A0 q2 13. a0 |*

A0 q3 23. a0 *

A0 q3 4. a0 |*

A0 q2 14. a0 |*

A0 q3 24. a0 *

A0 q3 5. a0 |*

A0 q2 15. a0 |*

A0 q1 25. a0 *

A0 q3 6. a0 |*

A0 q2 16. a0 a0 *

A0 q2 26. a0 *

A0 q3 7. a0 |*

A0 q2 17. a0 *

A0 q2 27. a0 *

A0 q3 8. a0 |*

A0 q3 18. a0 *

A0 q2 28. a0 *

A0 q3 9. a0 |*

A0 q3 19. a0 *

A0 q2 29. a0 *

A0 q1 10. a0 |*

A0 q3 20. a0 *

A0 q2 30. a0 a0 || a0 q0 Этот процесс позволяет записать алгоритм в виде двумерной таблицы, изображенной на рис. 6. «0 * q1 а0 н q1 а0 п q1 q2 | н q1 * п q1 | п q1 q3 а0 п q1 * ^q1 | ^ q1

Рис. 6.

Таким образом, здесь использован внешний алфавит (а0,*,|)и состояния машиныq0, q1, q2, q3.

На­пример 3. Алгоритм Евклида.

Алгоритм Евклида решает задачи вида: для двух данных натуральных чисел найти их общий наибольший делитель.

Как известно, алгоритм Евклида сводится к построению убывающей последовательности чисел, из которых первое является большим из двух данных чисел, второе — меньшим, третье получается как остаток от деления пер­вого на второе, четвертое - как остаток от деления вто­рого на третье и так далее, пока не будет совершено де­ление без остатка. Делитель в этом последнем делении и будет результатом решения задачи*

Нам требуется задать алгоритм Евклида в виде программы машины Тьюринга. Эта программа должна обес­печить попеременное чередование циклов сравнения и циклов вычитания чисел.

Будем использовать внешний алфавит, состоящий из четырех букв:(а0,|,а,) Здесь а0 - символпустой клетки,| -палочка,а и - буквы, играющие роль временных палочек. Пусть, для конкретности, требует­ся найти НОДчисел 4 и 6 при начальной конфигурации

а0

А0 q1 Сначала машина должна сравнить числа, изображенные на ленте. С этой целью она должна заменять палочки, изображающие первое число, буквами a, а палочки, изображающие второе число, — буквами . При этом конфигурации, соответствующие первым четырем так­там работы машины, будут иметь вид: 1.a0



A0 q1 2. a0

A

A0 q2 3. a0

A

A0 q2 4. a0

A

A0 q1 После этих четырех тактов управляющая головка должна двигаться влево в поисках еще не отмеченной ближайшей палочки первого числа, которая должна быть заменена на а , а затем начинается движение управляющей головки вправо в поисках ближайшей палочки второго числа, которая должна быть заменена на. После соответствующего числа тактов работы машины на лен­те возникнет конфигурация a0 aaaa ||a0 q1 На этом заканчивается цикл сравнения исходных чисел и начинается цикл вычитания, в результате которого меньшее число должно быть стерто целиком, палочки второго числа, помеченные буквой , заменяются на обычные палочки, и, следовательно, большее число 6 будет разбито на два числа 4 и 2. Этим операциям соответствует ряд конфигураций. Выпишем некоторые из них, пропуская очевидные кон­фигурации. a0 aaaa ||a0 q1 a0 aaaa ||a0 q3 a0 a0 aaaa ||a0 q3 ……………………………….. a0 a0 a0 a0 a0||a0 q3 a0 a0 a0 a0 a0||a0 q3 ……………………………….. a0 a0 a0 a0 a0

A0 q3 a0 a0 a0 a0 a0

A0 q2 На этом заканчивается первый цикл вычитания. Те­перь машина должна сравнить числа 4 и 2, Цикл сравне­ния этих чисел приводит к конфигурации: a0 ||aa a0 q2 а цикл вычитания — к конфигурации a0 | a0 q1 Третий цикл сравнения чисел 2 и 2 приводит к конфигурации a0 aa a0 q1 а цикл вычитания — к заключительной конфигурации В связи с этим функциональная схема Тьюринга име­ет вид a0 | a  q1 a0 п q3 aН q2 a0 q1 0  q1 q2 a0  q4  Н q1 a п q2  п q2 q3 a0 Н q0 | Н q2 a0 п q3 | п q3 q4 a0 Н q0 | Н q1 |0  q4 a00  q4 Рис.7 Основная гипотеза теории алгоритмов. Машина Тьюринга дает один из путей уточнения понятия алгоритма. В связи с этим возникают вопросы: насколько общим является понятие машины Тьюринга? Можно ли считать, что способ задания алгоритмов с помощью машины Тьюринга является универсальным? Может ли всякий алгоритм задаваться таким образом? На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы: Всякий алгоритм может быть задан посредством Тьюринговой функциональной схемы и реализован в соот­ветствующей машине Тьюринга. Эта гипотеза называется тезисом Тьюринга. Бе нельзя доказать, так как она связывает нестрогое определение понятия алгоритма со строгим определением понятия машины Тьюринга. Эта гипотеза может быть опровергнута, если удастся привести пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы. Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем. Напомним также, что другие способы уточнения понятия алгоритма (понятие нормального алгоритма А. А. Маркова, понятие рекурсивного алгоритма (рекур­сивной функции), введенного Чёрчем, Гёделем и Клини) оказались равносильными. Этот факт является важным доводом в пользу сформулированной гипотезы. Кроме того, следует сказать, что внутри самой тео­рии алгоритмов эта гипотеза не применяется, то есть при доказательстве теорем теории алгоритмов никаких ссылок на гипотезу не делается.




6528520833005154.html
6528605071901493.html
    PR.RU™