Что означает эквивалентность различных универсальных исполнителей
Урок 33
Уточнение понятие алгоритма. Универсальные исполнители
§34. Уточнение понятия алгоритма
Содержание урока
Универсальные исполнители
Универсальные исполнители
Как мы уже видели, понятие алгоритма оказывается «привязанным» к его исполнителю и некоторому языку программирования. Это не позволяет определить алгоритм как математический объект. Поэтому возникла идея попытаться построить универсальный исполнитель.
Универсальный исполнитель — это исполнитель, который может моделировать работу любого другого исполнителя.
Это значит, что для любого алгоритма, написанного для любого исполнителя, существует эквивалентный алгоритм для универсального исполнителя.
Такой исполнитель можно было бы использовать для доказательства разрешимости или неразрешимости задач. Если удаётся построить алгоритм решения задачи для универсального исполнителя, то задача разрешима. Если доказано, что алгоритм не существует, то задача неразрешима. Система команд такого исполнителя должна быть как можно проще — так его будет легче использовать в доказательствах.
В середине XX века разными учёными независимо друг от друга были предложены несколько исполнителей, претендующих на роль универсальных (они будут рассмотрены далее), причём в теории алгоритмов доказано, что все они эквивалентны друг другу. Это означает, что для любого алгоритма для одного универсального исполнителя можно построить эквивалентный алгоритм для другого универсального исполнителя.
Как же связан универсальный исполнитель с проблемой строгого определения алгоритма?
Любой алгоритм может быть представлен как программа для универсального исполнителя.
Это основная идея теории алгоритмов. Строго доказать это утверждение невозможно, потому что здесь используется интуитивное понятие «алгоритм».
Как мы увидим, каждый универсальный исполнитель описывается с помощью математических терминов, поэтому на его основе можно дать строгое определение алгоритма:
Алгоритм — это программа для универсального исполнителя.
Универсальный исполнитель — это некоторая модель вычислений, которая задаёт способ описания алгоритмов и их выполнения.
Модель вычислений должна содержать:
• «процессор», задающий систему команд и способ их выполнения;
• «память», определяющую способ хранения данных;
• язык программирования (способ записи программ);
• способ ввода данных (чтения входного слова);
• способ вывода слова-результата.
Все универсальные исполнители эквивалентны, поэтому последнее приведённое определение алгоритма не зависит от конкретного исполнителя.
Следующая страница 
Машина Тьюринга
Cкачать материалы урока
Содержание урока
Вопросы и задания
Вопросы и задания
1. Зачем понадобилось уточнять понятие «алгоритм»?
2. Какие задачи рассматриваются в теории алгоритмов?
3. Почему можно ограничиться алгоритмами обработки символьных строк? Можно ли рассматривать только алгоритмы для преобразования двоичных кодов?
4. Как вы понимаете утверждение «Алгоритм задаёт некоторую функцию»?
5. Как связаны понятия «алгоритм» и «исполнитель»?
6. Что такое программа?
7. В каком случае говорят, что два алгоритма эквивалентны?
8. Что такое универсальный исполнитель?
9. Сравните интуитивное и строгое понятия алгоритма.
10. Опишите устройство и систему программирования машины Тьюринга.
11. Что такое состояние машины Тьюринга?
12. Сопоставьте устройство машины Тьюринга с устройством компьютера. Какие устройства машины Тьюринга выполняют те же функции, что и аналогичные устройства компьютера?
13. В чем особенность состояний q0 и q1, машины Тьюринга?
14. По какому принципу можно построить программу для машины Тьюринга, которая последовательно выполняет операции А и Б?
15. Сформулируйте тезис Чёрча-Тьюринга.
16. Сравните машины Тьюринга и Поста.
17. Зачем нумеруются строки в программе для машины Поста?
18. Что такое нормальный алгорифм Маркова?
19. Зачем используют специальные символы в НАМ?
20. Что означает эквивалентность различных универсальных исполнителей?
Подготовьте сообщение
а) «Какие бывают машины Тьюринга?»
б) «Эзотерические языки программирования»
в) «Рекурсивные функции»
Следующая страница Задачи
Cкачать материалы урока
Урок 33
Уточнение понятие алгоритма. Универсальные исполнители
§34. Уточнение понятия алгоритма
Содержание урока
Нормальные алгорифмы Маркова
Нормальные алгорифмы Маркова
Советский математик А. А. Марков младший (сын Андрея Андреевича Маркова (2 (14) июня 1856, Рязань — 20 июля 1922, Петроград) — русского математика, академика, внёсшего большой вклад в теорию вероятностей, математический анализ и теорию чисел), который в середине XX века изучал разрешимость некоторых задач алгебры, предложил новую модель вычислений, которую он назвал нормальными алгорифмами.
Нормальные алгорифмы Маркова (НАМ) — это строгая математическая форма записи алгоритмов обработки символьных строк, которую можно использовать для доказательства разрешимости или неразрешимости различных задач. Марков предположил, что любой алгоритм можно записать как НАМ. В отличие от машин Тьюринга и Поста НАМ — это «чистый» алгоритм, который не связан ни с каким «аппаратным обеспечением» (лентой, кареткой и т. п.).
НАМ преобразует одно слово (цепочку символов некоторого алфавита) в другое и задаётся алфавитом и системой подстановок. Заметьте, что в жизни мы нередко применяем такие замены. Например, при умножении в столбик мы не вычисляем каждый раз произведение 7 • 8, а просто помним, что оно равно 56.
Пример 1. Пусть алфавит НАМ — это русские буквы и задана система подстановок:
Применим эту систему подстановок к начальному слову «муха». Подстановки нужно просматривать по порядку, начиная с первой. Первая подстановка означает: «если в слове есть буквы “а”, заменить первую букву “а” на букву “н”». В слове «муха» есть буква «а», поэтому заменяем её на «н». Получается «мухн».
Начинаем просмотр подстановок сначала. Букв «а» больше нет, поэтому переходим ко второй подстановке. Сочетание «ух» есть в слове «мухн», поэтому вторая подстановка срабатывает, и мы заменяем «ух» на «ло»: получается «млон».
Теперь ни первая, ни вторая подстановки не применимы, а использование третьей даёт в результате слово «слон». Больше ни одну подстановку сделать нельзя, и НАМ заканчивает работу. Таким образом, приведённая система подстановок преобразует слово «муха» в слово «слон».
При поиске образца рабочая цепочка символов просматривается с начала. Если в строке слово-образец встречается несколько раз, то за один шаг заменяется только первое из них. Так как на следующем шаге просмотр опять начинается с начала цепочки, после первой выполненной замены может «сработать» совсем другая подстановка.
В записи подстановок слово-образец может быть пустым, в этом случае слово-замена приписывается в начало рабочей строки:
Такая подстановка всегда должна быть последней в списке, иначе программа зациклится: в начало слова будут постоянно дописываться всё новые и новые нули.
Если после слова-замены стоит точка, после выполнения такой подстановки работа программы заканчивается. Например, если применить НАМ
а→о.
к слову «карова», то в результате получим «корова», потому что после первого же действия работа программы закончится, и последняя буква не будет заменена.
Однако такой НАМ будет неправильно работать для слов, начинающихся с буквы «b», например для слова «bbа», в котором будет удалена последняя буква, потому что первая подстановка выполнится раньше, чем вторая. Перестановка двух строк также не даёт решения — теперь алгоритм неправильно работает для слов, начинающихся с буквы «а». Чтобы решить эту задачу, в алфавит НАМ добавляют еще один специальный символ, например символ «*». Этим символом помечают начало слова, используя подстановку.
Полный алгоритм выглядит так:
Сначала срабатывает третья подстановка (ставим «*» в начало строки), затем, в зависимости от первой буквы исходного слова, работает первая или вторая подстановка, и алгоритм заканчивает работу. Дополнительный символ похож на маркер в текстовом редакторе — он отмечает место в тексте, с которым потом будут выполняться какие-то действия.
Как показано в теории алгоритмов, любой алгоритм для машин Тьюринга и Поста можно записать как НАМ и наоборот.
Поэтому все три рассмотренных подхода к строгому определению понятия «алгоритм» эквивалентны (равносильны).
Следующая страница Вопросы и задания
Cкачать материалы урока
Примеры универсальных исполнителей
Электронные ресурсы:
1. Машина Тьюринга. Введение. Понятие машины Тьюринга. Решение задачиhttps://www.youtube.com/watch?v=clrdEuTX9r8&list=PLT1KJddt96CF5dFATm3KXemsfPTKsxGS_
2.Машина Тьюринга. 2 часть. Решение задач.
Ссылка на эмулятор «Машина Тьюринга»: http://kpolyakov.spb.ru/prog/turing.htm
Алгоритм — это строго детерминированная последовательность действий, описывающая процесс преобразования объекта из начального состояния в конечное, записанная с помощью понятных исполнителю команд (Н. Д. Угринович)
Алгоритмом называют точный набор инструкций для исполнителя, который приводит к решению задачи за конечное время (К. Ю. Поляков)
Впервые необходимость формального понятия алгоритма возникла в связи с проблемой алгоритмической неразрешимости некоторых задач. Долгое время математики верили в возможность того, что все строго поставленные математические задачи могут быть алгоритмически решены, нужно только найти алгоритм их решения. Вера в универсальность алгоритмических методов была подорвана работой Курта Геделя (1931 год), в которой было показано, что некоторые математические проблемы не могут быть решены с помощью алгоритмов из некоторого класса. Этот класс алгоритмов определяется некоторой формальной конкретизацией понятия алгоритма. Встал вопрос: являются ли алгоритмически неразрешимыми эти проблемы только в рамках использованной Геделем модели алгоритма или же для решения этих проблем вообще нельзя придумать никакого алгоритма ни в каком смысле? Общность результата Геделя зависит от того, совпадает ли использованный им класс алгоритмов с классом всех алгоритмов в интуитивном смысле. Поэтому поиск и анализ различных уточнений и формализации алгоритма и соотношение этих формализаций с интуитивным понятием алгоритма является практически важным.
Интенсивный поиск универсального уточнения алгоритма предложил примерно 20 формальных конструкций алгоритмов, которые условно можно разбить на три типа:
Алгоритмические машины (АМ)имеют единственный процессор, выполняющий небольшой набор очень примитивных действий,простую структуру данных (структуру памяти) в виде бесконечной ленты,простую логику (правила) управления процессором.
— Машина Тьюринга (МТ) предложена Тьюрингом в 1937 г.
— Машина Поста (МР) предложена Постом в 1937 г.
— Нормальный алгоритм Маркова (НАМ) предложен Марковым в 1953 г.
Машина Тьюринга-абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча — Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
Тьюринг назвал свое абстрактное механическое устройство «универсальной машиной», поскольку она должна была справляться с любой допустимой, то есть теоретически разрешимой задачей — математической или логической.
Данные должны были вводиться в машину на бумажной ленте, поделенной на клетки — ячейки.
Каждая такая ячейка либо содержала символ, либо была пустой.
Машина могла не только обрабатывать записанные на ленте символы, но и изменять их, стирая старые и записывая новые в соответствии с инструкциями, хранимыми в ее внутренней памяти.
Машина Тьюринга
(тренажер для изучения универсального исполнителя)
Машина Тьюринга состоит из каретки (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки. Каждая ячейка ленты может содержать символ из некоторого алфавита A=
Машина Тьюринга — это автомат, который управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q=
В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей:
— направление перемещения: > (вправо),
Дата добавления: 2020-12-22 ; просмотров: 57 ; Мы поможем в написании вашей работы!
Урок 33
Уточнение понятие алгоритма. Универсальные исполнители
§34. Уточнение понятия алгоритма
Содержание урока
Вопросы и задания
Вопросы и задания
1. Зачем понадобилось уточнять понятие «алгоритм»?
2. Какие задачи рассматриваются в теории алгоритмов?
3. Почему можно ограничиться алгоритмами обработки символьных строк? Можно ли рассматривать только алгоритмы для преобразования двоичных кодов?
4. Как вы понимаете утверждение «Алгоритм задаёт некоторую функцию»?
5. Как связаны понятия «алгоритм» и «исполнитель»?
6. Что такое программа?
7. В каком случае говорят, что два алгоритма эквивалентны?
8. Что такое универсальный исполнитель?
9. Сравните интуитивное и строгое понятия алгоритма.
10. Опишите устройство и систему программирования машины Тьюринга.
11. Что такое состояние машины Тьюринга?
12. Сопоставьте устройство машины Тьюринга с устройством компьютера. Какие устройства машины Тьюринга выполняют те же функции, что и аналогичные устройства компьютера?
13. В чем особенность состояний q0 и q1, машины Тьюринга?
14. По какому принципу можно построить программу для машины Тьюринга, которая последовательно выполняет операции А и Б?
15. Сформулируйте тезис Чёрча-Тьюринга.
16. Сравните машины Тьюринга и Поста.
17. Зачем нумеруются строки в программе для машины Поста?
18. Что такое нормальный алгорифм Маркова?
19. Зачем используют специальные символы в НАМ?
20. Что означает эквивалентность различных универсальных исполнителей?
Подготовьте сообщение
а) «Какие бывают машины Тьюринга?»
б) «Эзотерические языки программирования»
в) «Рекурсивные функции»
Следующая страница Задачи
Cкачать материалы урока