A0 q1 11. a0 |*

⇐ ПредыдущаяСтр 31 из 34Следующая ⇒

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.

Таким образом, здесь использован внешний алфавит (а ₀, *, |) и состояния машины q _0, q _1, q _2, q _3.

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

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

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

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

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

а ₀

А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 Основная гипотеза теории алгоритмов. Машина Тьюринга дает один из путей уточнения понятия алгоритма. В связи с этим возникают вопросы: насколько общим является понятие машины Тьюринга? Можно ли считать, что способ задания алгоритмов с помощью машины Тьюринга является универсальным? Может ли всякий алгоритм задаваться таким образом? На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы: Всякий алгоритм может быть задан посредством Тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга. Эта гипотеза называется тезисом Тьюринга. Бе нельзя доказать, так как она связывает нестрогое определение понятия алгоритма со строгим определением понятия машины Тьюринга. Эта гипотеза может быть опровергнута, если удастся привести пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы. Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем. Напомним также, что другие способы уточнения понятия алгоритма (понятие нормального алгоритма А. А. Маркова, понятие рекурсивного алгоритма (рекурсивной функции), введенного Чёрчем, Гёделем и Клини) оказались равносильными. Этот факт является важным доводом в пользу сформулированной гипотезы. Кроме того, следует сказать, что внутри самой теории алгоритмов эта гипотеза не применяется, то есть при доказательстве теорем теории алгоритмов никаких ссылок на гипотезу не делается.

⇐ Предыдущая 25 26 27 28 29 303132 33 34 Следующая ⇒

© 2023 :: MyLektsii.ru :: Мои Лекции
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.
Копирование текстов разрешено только с указанием индексируемой ссылки на источник.