http://books.altspu.ru/files/original/63/50/_[650].jpg 3bcf0c3c702dc35e6b7bd1e4cc8fe113 http://books.altspu.ru/files/original/63/50/dronova.pdf 97f8361100762ede8b5d322b31bb4a55 PDF Text Text Содержание �Содержание Об издании Основной титульный экран Дополнительный титульный экран непериодического издания – 1 Дополнительный титульный экран непериодического издания – 2 �Содержание Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего образования «Алтайский государственный педагогический университет» Е.Н. Дронова ОСНОВНЫЕ АЛГОРИТМИЧЕСКИЕ МОДЕЛИ Учебное пособие Барнаул ФГБОУ ВО "АлтГПУ" 2016 Об издании - 1, 2, 3. ISBN 978–5–88210–814–3 �Содержание УДК 002(075)+510(075) ББК 32.97я73+22.1я73 Д758 Дронова, Е.Н. Основные алгоритмические модели [Электронный ресурс] : учебное пособие / Е.Н. Дронова. – Барнаул : АлтГПУ, 2016. – Систем. требования: ПК с Intel® x86-совместимый процессором, Pentium® 4 или новее ; 512 Мб ОЗУ ; Windows XP и более поздние ; Adobe Acrobat Reader ; SVGA видеоплата и монитор (1024х768, 16 млн цв.) ; мышь. ISBN 978–5–88210–814–3 Рецензенты: Алтухов Ю.А., доктор физико-математических наук, профессор (АлтГТУ); Афонина М.В., кандидат педагогических наук, доцент (АлтГПУ) В пособии представлено описание таких алгоритмических моделей, как класс рекурсивных функций, машина Тьюринга, машина Поста, машины произвольного доступа, нормальные алгоритмы Маркова. Особое внимание уделено разработке вычислительных алгоритмов в указанных алгоритмических моделях. Пособие предназначено студентам педагогических вузов, изучающих теорию алгоритмов. Рекомендовано к изданию редакционно-издательским советом АлтГПУ 28.01.2016 г. Деривативное электронное издание. Текстовое (символьное) электронное издание. Системные требования: ПК с Intel® x86-совместимый процессором, Pentium® 4 или новее ; 512 Мб ОЗУ ; Windows XP и более поздние ; Adobe Acrobat Reader ; SVGA видеоплата и монитор (1024х768, 16 млн цв.) ; мышь. Об издании - 1, 2, 3. �Содержание Электронное издание создано при использовании программного обеспечения Sunrav BookOffice. Объём издания - 8 166 КБ. Дата подписания к использованию: 30.03.2016 Федеральное государственное бюджетное образовательное учреждение высшего образования «Алтайский государственный педагогический университет» (ФГБОУ ВО «АлтГПУ») ул. Молодежная, 55, г. Барнаул, 656031 Тел. (385-2) 36-82-71, факс (385-2) 24-18-72 е-mail: rector@altspu.ru, http://www.altspu.ru Об издании - 1, 2, 3. �Содержание Содержание Предисловие Глава 1. «Алгоритм» как центральное понятие теории алгоритмов 1.1. Развитие понятия алгоритма 1.2. Возникновение и основные этапы развития теории алгоритмов как науки 1.3. Алгоритмы: интуитивное представление об алгоритмах, исполнитель алгоритма, свойства и способы записи алгоритмов 1.3.1. Интуитивное представление об алгоритмах 1.3.2. Исполнитель алгоритма 1.3.3. Свойства алгоритмов 1.3.4. Способы записи алгоритмов 1.4. Базовые алгоритмические структуры Вопросы к главе 1 Задания к главе 1 Глава 2. Класс рекурсивных функций 2.1. Введение в теорию рекурсивных функций 2.2. Примитивно рекурсивные функции 2.3. Частично рекурсивные функции 2.4. Взаимосвязь между различными классами рекурсивных функций 2.5. Тезис Черча Вопросы к главе 2 Задания к главе 2 Глава 3. Машина Тьюринга 3.1. Назначение и предпосылки создания машины Тьюринга 3.2. Устройство машины Тьюринга 3.3. Команды и порядок работы машины Тьюринга 3.4. Вычислимые по Тьюрингу функции 3.5. Основные операции над машинами Тьюринга 3.6. Тезис Тьюринга 3.7. Машины Тьюринга и современные электронно-вычислительные машины Вопросы к главе 3 �Содержание Задания к главе 3 Глава 4. Машина Поста 4.1. Назначение и устройство машины Поста 4.2. Команды и порядок работы машины Поста 4.3. Примеры типичных программ машины Поста 4.4. Тезис Поста Вопросы к главе 4 Задания к главе 4 Глава 5. Машины произвольного доступа 5.1. Устройство и порядок работы машины произвольного доступа 5.2. Вычисление функций на машине произвольного доступа 5.3. Композиция программ машин произвольного доступа Вопросы к главе 5 Задания к главе 5 Глава 6. Нормальные алгоритмы Маркова 6.1. Марковские подстановки 6.2. Нормальные алгоритмы и их применение к словам 6.3. Нормально вычислимые функции 6.4. Способы сочетания нормальных алгоритмов 6.5. Принцип нормализации Маркова Вопросы к главе 6 Задания к главе 6 Заключение Ответы, указания и решения Глава 1 Глава 2 Глава 3 Глава 4 Глава 5 Глава 6 Библиографический список �Содержание Предисловие Данное учебное пособие предназначено для тех, кто изучает теорию алгоритмов в высших учебных заведениях. Автор знакомит будущих специалистов с основными понятиями теории алгоритмов, описывает основные алгоритмические модели и правила их функционирования, показывает взаимосвязь теории алгоритмов со школьным курсом информатики. В первой главе представлен материал о сущности понятия алгоритма, о развитии и использовании его в науке, о становлении и задачах теории алгоритмов, об основных направлениях ее применения. Главы 2, 3, 4, 5, 6 посвящены различным алгоритмическим моделям; здесь описаны назначение, устройство и функционирование следующих формальных моделей алгоритма: класс частичнорекурсивных функций, машина Тьюринга, машина Поста, машины произвольного доступа, нормальные алгоритмы Маркова. Все главы в пособии завершаются списком вопросов и заданий. Вопросы, приведенные в конце каждой главы, помогут вам понять, хорошо ли вы усвоили новый материал, и ускорят процесс его повторения. Подобранные нами задачи к главам весьма разнообразны – среди них есть простые, а есть и такие, для решения которых нужно проявить смекалку. Мы надеемся, что каждый здесь найдет себе задачи по вкусу. В нашем пособии, как и в любом другом, вам встретятся новые термины. Для удобства они напечатаны курсивом. Ключевые идеи и слова в тексте также выделены курсивом. Мы не считаем важным заучивать их наизусть, но понимать их смысл и уметь применять на практике вы должны научиться. С этой целью изложенный нами в пособии материал иллюстрирован большим количеством примеров. Часть этих примеров позволит вам более глубоко усвоить сущность новых терминов, часть – освоить правила оперирования с ними и научиться применять их при решении задач. Часть ключевых задач, позволяющих усвоить новый материал на более высоком уровне, приведена не в содержании соответствующей главы, а вынесена в список заданий к ней. Решение этих задач предлагается найти самостоятельно, что потребует не только понимания изученного материала, но и проявления творчества. Однако если решение какой-либо задачи вам не удастся найти – не огорчайтесь: подробное решение ключевых задач представлено нами в конце пособия, там же вы сможете найти ответы и указания к решению большинства задач, приведенных в конце всех глав. В завершении подчеркнем, что данное пособие не является исчерпывающим руководством по изучению основных алгоритмических моделей. Оно призвано помочь студентам более тщательно разобраться с соответствующими основными понятиями, научиться решать типовые задачи и позволит в дальнейшем (при написании курсовых, дипломных работ) приступить уже со знанием дела к изучению более подробной специальной литературы. �Содержание Глава 1. «Алгоритм» как центральное понятие теории алгоритмов § 1. Развитие понятия алгоритма § 2. Возникновение и основные этапы развития теории алгоритмов как науки § 3. Алгоритмы: интуитивное представление об алгоритмах, исполнитель алгоритма, свойства и способы записи алгоритмов § 4. Базовые алгоритмические структуры Вопросы к главе 1 Задания к главе 1 �Содержание 1.1. Развитие понятия алгоритма Понятие «алгоритм» давно является привычным не только для математиков. Оно является концептуальной основой разнообразных процессов обработки информации, возможность автоматизации таких процессов обеспечивается наличием соответствующих алгоритмов. В упрощенном понимании «алгоритм» – это то, что можно запрограммировать на ЭВМ. Термин «алгоритм» происходит от algorithmi – латинской формы написания великого математика средневекового Востока Аль-Хорезми. Он жил приблизительно с 783 по 850 гг. в городе Ургенче – областном центре современной Хорезмской области Узбекистана. Его научные работы посвящены правилам выполнения арифметических действий в десятичной системе счисления. Роль их в развитии математики огромна. Связано это во многом с тем, что в XI веке еще не была разработана математическая символика (знаки операций, скобки, буквенные обозначения и т. п.). В связи с этим, Аль-Хорезми в своих работах стремился выработать такой стиль четкого, строгого словесного предписания, который бы не позволил читателям уклониться от предписанных действий или что-либо пропустить в них. Разработанные этим ученым правила выполнения арифметических действий над десятичными числами начинались (в латинском варианте) словами «Алгоризми сказал». С течением времени это выражение преобразовалось во фразу «алгоритм гласит». Таким образом, слово «алгоритм» происходит от имени ученого Аль-Хорезми и как научный термин первоначально обозначало лишь правила выполнения арифметических действий в десятичной системе счисления. С течением времени слово «алгоритм» приобрело более широкий смысл и стало обозначать не только правила цифровых вычислений десятичной позиционной арифметики, но и любые точные правила действий в произвольных процессах, следуя которым искомые величины решаемых задач можно было найти из исходных данных. Вплоть до 30-х годов XX века понятие алгоритма оставалось интуитивно понятным: под алгоритмом понимали конечную последовательность элементарных действий, направленных на решение поставленной задачи. К этому времени были известны такие яркие примеры алгоритмов, как алгоритм Евклида для нахождения наибольшего общего делителя двух натуральных чисел, алгоритм Гаусса для решения системы линейных уравнений над полем, алгоритм нахождения рациональных корней многочленов одного переменного с рациональными коэффициентами, алгоритм разложения многочлена одного переменного над конечным полем на неприводимые множители и т. д. Указанные математические проблемы решены путем указания конкретных разрешающих процедур (алгоритмов). Иными словами, для доказательства алгоритмической разрешимости той или иной проблемы достаточно представить алгоритм ее решения. Наряду с алгоритмически разрешимыми проблемами к началу XX века были сформулированы такие проблемы, алгоритмическая разрешимость которых была маловероятна. В связи с этим, возник вопрос «Как доказать, что та или иная проблема (задача) не имеет алгоритма решения (алгоритмически неразрешима)»? Данный вопрос позволил немного прояснить сложившуюся на тот период времени ситуацию: для того, чтобы можно было строго математически доказать отсутствие алгоритма решения некоторой задачи, необходимо сначала строго математически определить само понятие алгоритма. Таким образом, в среде ученых обострился следующий вопрос: «Как формализовать понятие "алгоритм"?» �Содержание 1.2. Возникновение и основные этапы развития теории алгоритмов как науки Начальной точкой отсчета современной теории алгоритмов можно считать теорему о неполноте символических логик, доказанную немецким математиком Куртом Геделем в 1931 году. В этой работе было показано, что некоторые математические проблемы не могут быть решены алгоритмами из определенного класса. Важность результата Геделя связана с вопросом о том, совпадает ли использованный им класс алгоритмов с классом всех алгоритмов в интуитивном понимании этого термина. Эта работа дала толчок к поиску и анализу различных формализаций понятия «алгоритм». Первые фундаментальные работы по теории алгоритмов были опубликованы в середине 1930-х годов Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и класс частично-рекурсивных функций Черча были первыми формальными описаниями алгоритма, использующими строго определенные модели вычислений (алгоритмическими моделями). Сформулированные гипотезы Тьюринга, Поста и Черча постулировали эквивалентность предложенных ими моделей вычислений и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство существования алгоритмически неразрешимых проблем. В 1950-е годы существенный вклад в развитие теории алгоритмов внесли работы А.Н. Колмогорова и А.А. Маркова. Формальные модели Поста, Тьюринга и Черча, равно как и модели А.Н. Колмогорова и А.А. Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешим и в другой. Появление доступных ЭВМ и существенное расширение круга решаемых на них задач привели в 1960– 70-х годах к практически значимым исследованиям алгоритмов и вычислительных задач. На этой основе в данный период оформились следующие разделы в теории алгоритмов: − классическая теория алгоритмов (формулировка задач в терминах формальных языков, понятие задачи разрешения, описание сложностных классов задач, формулировка в 1965 году Эдмондсом проблемы P  NP , открытие класса NP -полных задач и его исследование и др.); − теория асимптотического анализа алгоритмов (понятие сложности и трудоемкости алгоритма, критерии оценки алгоритмов, методы получения асимптотических оценок, в частности для рекурсивных алгоритмов, асимптотический анализ трудоемкости или времени выполнения, получение теоретически нижних оценок сложности задач); − теория практического анализа вычислительных алгоритмов (получение явных функций трудоемкости, практически значимые критерии качества алгоритмов, методики выбора рациональных алгоритмов). Обобщая исследования в различных разделах теории алгоритмов, можно выделить следующие основные задачи и направления развития, характерные для современной теории алгоритмов: − формализация понятия «алгоритм» и исследование формальных алгоритмических систем (моделей вычислений); − доказательство алгоритмической неразрешимости задач; − формальное доказательство правильности и эквивалентности алгоритмов; − классификации задач, определение и исследование сложностных классов; − доказательство теоретических нижних оценок сложности задач; �Содержание − получение методов разработки эффективных алгоритмов; − асимптотический анализ сложности итерационных алгоритмов; − исследование и анализ рекурсивных алгоритмов; − получение явных функций трудоемкости алгоритмов; − разработка классификаций алгоритмов; − исследование емкостной (по ресурсу памяти) сложности задач и алгоритмов; − разработка критериев сравнительной оценки ресурсной эффективности алгоритмов и методов их сравнительного анализа. Полученные в теории алгоритмов результаты находят сегодня достаточно широкое практическое применение, в рамках которого можно выделить два аспекта: теоретический и практический. Теоретический аспект: при исследовании некоторой задачи результаты теории алгоритмов позволяют ответить на вопрос – является ли эта задача в принципе алгоритмически разрешимой? В случае алгоритмической разрешимости задачи следующим важным теоретическим вопросом является вопрос о принадлежности этой задачи к классу NP-полных задач. При утвердительном ответе можно говорить о существенных временных затратах для получения точного решения этой задачи для больших размерностей исходных данных, иными словами – об отсутствии быстрого точного алгоритма ее решения. Практический аспект: методы и методики теории алгоритмов, в основном асимптотического и практического анализа, позволяют осуществить: − рациональный выбор из известного множества алгоритмов решения данной задачи, учитывающий особенности их применения в разрабатываемой программной системе; − получение временных оценок решения сложностных задач на основе функции трудоемкости; − получение достоверных оценок невозможности решения некоторой задачи за определенное время; − разработку и совершенствование эффективных алгоритмов решения практически значимых задач в области обработки информации. �Содержание 1.3. Алгоритмы: интуитивное представление об алгоритмах, исполнитель алгоритма, свойства и способы записи алгоритмов Понятие «алгоритм» является центральным понятием теории алгоритмов, поэтому рассмотрим его более подробно. 3.1. Интуитивное представление об алгоритмах 3.2. Исполнитель алгоритма 3.3. Свойства алгоритмов 3.4. Способы записи алгоритмов �Содержание 1.3.1. Интуитивное представление об алгоритмах Первоначально под словом «алгоритм» понимали способ выполнения арифметических действий над десятичными числами (см. 1.1). В дальнейшем это понятие стали использовать для обозначения любой последовательности действий, приводящей к решению поставленной задачи. Современный человек понимает под алгоритмом четкую систему инструкций о выполнении в определенном порядке некоторых действий для решения всех задач какого-то данного класса. Многочисленные и разнообразные алгоритмы окружают нас буквально во всех сферах жизни и деятельности. Многие наши действия доведены до бессознательного автоматизма, мы порой и не осознаем, что они регламентированы определенным алгоритмом четкой системой инструкций. Например, наши действия при входе в продуктовый магазин (сдать свою сумку, получить корзину с номером, пройти в торговый зал, заполнить корзину продуктами, оплатить покупку в кассе, предъявить чек контролеру, взять свою сумку, переложить в нее продукты, сдать корзину, покинуть магазин). Вместе с тем, есть немало таких действий, выполняя которые, мы тщательно следуем той или иной инструкции. Это непривычные действия, профессионально нам не свойственные. Например, если вы никогда раньше не пекли торт, то, получив рецепт его приготовления, вы будете стараться выполнить в указанной последовательности все его предписания. Говоря об алгоритмах, нельзя не подчеркнуть их огромную роль в математике. Каждый из вас буквально с первых классов школы при изучении математики встретился с большим количеством алгоритмов. Это, прежде всего, алгоритмы выполнения четырех арифметических действий над различными числами натуральными, целыми, дробными, комплексными; алгоритмы геометрических построений с помощью циркуля и линейки (деление пополам отрезка и угла, опускание и восстановление перпендикуляров, проведение параллельных прямых); алгоритмы вычисления площадей и объемов различных геометрических фигур и т. д. При изучении математики в вузе вами были освоены алгоритм вычисления наибольшего общего делителя двух натуральных чисел (алгоритм Евклида), алгоритм нахождения определителей различных порядков, алгоритм вычисления интегралов от рациональных функций и т. д. Иными словами, алгоритмы широко распространены как в практике, так и в науке, и требуют более внимательного к себе отношения и тщательного изучения. Следует выделить следующую особенность понятия «алгоритм»: оно не является формальным математическим понятием, так как в его определении используются такие неуточняемые понятия, как «точные правила действий», «последовательность элементарных действий» и т. д. Вместе с тем, описание понятия алгоритма раскрывает его суть; употребляя термин «алгоритм», мы можем пояснить его смысл. Поэтому принято говорить, что «алгоритм» это интуитивное понятие. Из разнообразных вариантов словесного описания сущности понятия «алгоритм» приведем, на наш взгляд, наиболее удачные [3]: алгоритм (по А.Н. Колмогорову) это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи; алгоритм (по А.А. Маркову) это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату. �Содержание Подчеркнем, что, несмотря на существование различных определений понятия «алгоритм», в явной или неявной форме все эти определения постулируют следующий ряд требований к алгоритму: − алгоритм должен содержать конечное количество элементарно выполнимых предписаний, т. е. удовлетворять требованию конечности записи; − алгоритм должен выполнять конечное количество шагов при решении задачи, т. е. удовлетворять требованию конечности действий; − алгоритм должен быть единым для всех допустимых исходных данных, т. е. удовлетворять требованию универсальности; − алгоритм должен приводить к правильному по отношению к поставленной задаче решению, т. е. удовлетворять требованию правильности. �Содержание 1.3.2. Исполнитель алгоритма Любой алгоритм существует не сам по себе, а предназначен для определенного исполнителя действий. Так, алгоритм вычисления производной для полинома фиксированной степени вполне ясен тем, кто знаком с основами математического анализа, но для прочих он может оказаться совершенно непонятным. Исполнитель алгоритма это тот объект (или субъект), для управления которым составляется алгоритм. Иными словами, исполнитель алгоритма это некоторая абстрактная или реальная система (техническая, биологическая или биотехническая), способная выполнить действия, предписываемые алгоритмом. Исполнителем алгоритма может быть человек, группа людей, робот, станок, компьютер, язык программирования и т. д. Его характеризуют: − среда; − система команд; − элементарные действия; − отказы. Среда (или обстановка) это «место обитания» исполнителя. Система команд исполнителя (СКИ) это конечное множество команд, которые понимает исполнитель, т. е. умеет их выполнять. Для каждой такой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды. Элементарное действие совершается исполнителем после вызова какой-либо команды. Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды. В качестве примера рассмотрим широко известного учебного исполнителя Кенгуренка. Среда исполнителя. На экране присутствуют три основных элемента среды учебного исполнителя: строка меню, поле программы и поле рисунка, на котором находится Кенгуренок. На поле рисунка неявно (т. е. ее не видно) нанесена прямоугольная сетка. Длину стороны одной квадратной ячейки этой сетки назовем шагом. Размер всего поля 15 шагов по горизонтали и 19 шагов по вертикали. Система команд исполнителя. Команды делятся на команды установки режимов (определенного состояния учебного исполнителя, в котором могут выполняться определенные действия) и команды управления Кенгуренком. Команды установки режимов следующие: − пуск (запуск на исполнение готовой программы в пошаговом автоматическом режиме); − отладка (выполнение программы в отладочном режиме с остановкой после каждой команды); − установка (очистка поля и установка положения Кенгуренка с помощью клавиш перемещения курсора); − разное (содержит подменю с дополнительными командами работы с файлами печать программы, печать рисунка, стереть программу); чтение, запись, �Содержание − результат (мгновенное получение результата работы программы исполнения). автоматический режим Команды управления Кенгуренком следующие: − шаг (перемещение Кенгуренка на один шаг вперед с рисованием линии); − поворот (поворот Кенгуренка на 900 против часовой стрелки); − прыжок (перемещение Кенгуренка на один шаг вперед без рисования линии); − пока <условие> повторять <тело цикла> конец цикла (цикл с предусловием); − если <условие> то <серия 1> иначе <серия 2> конец ветвления (полное ветвление); − если <условие> то <серия> конец ветвления (неполное ветвление); − сделай <имя процедуры> (обращение к процедуре). Отметим еще одну важнейшую характеристику исполнителя алгоритма: исполнитель не вникает в смысл того, что он делает! Он действует формально, т. е. отвлекается от содержания поставленной задачи и только строго согласно алгоритму выполняет некоторые инструкции, действия. Целесообразность же предусматриваемых алгоритмом действий обеспечивается точным анализом со стороны того, кто составляет алгоритм. Раскрытое нами понятие исполнителя алгоритма позволяет привести следующее определение термина «алгоритм»: «Алгоритм понятное и точное предписание исполнителю выполнить конечную последовательность команд, приводящих от исходных данных к искомому результату». В приведенном определении содержатся основные понятия, связанные с алгоритмом и его свойствами. Взаимосвязь этих понятий отражена нами на рис. 1. Рис. 1. Схема функционирования исполнителя алгоритмов �Содержание 1.3.3. Свойства алгоритмов Несмотря на то, что понятие алгоритма имеет интуитивный характер, его определение нестрогое, можно выделить следующие характерные черты алгоритма. 1. Дискретность. Описываемый алгоритмом процесс должен быть разбит на последовательность отдельных шагов. Возникающая в результате такого разбиения запись представляет собой упорядоченную совокупность четко разделенных друг от друга предписаний, образующих прерывную (дискретную) структуру алгоритма. 2. Понятность. Алгоритм не должен содержать предписаний, смысл которых может восприниматься исполнителем неоднозначно, т. е. запись алгоритма должна быть настолько четкой и полной, чтобы у исполнителя не возникало потребности в принятии каких-либо самостоятельных решений. 3. Детерминированность (или определенность). Запись алгоритма должна быть четкой, полной и продуманной в деталях, чтобы у исполнителя не могло возникнуть потребности в принятии решений. Кроме того, в алгоритмах недопустимы также ситуации, когда после выполнения очередной команды алгоритма исполнителю неясно, какая из команд алгоритма должна выполняться на следующем шаге. 4. Результативность (или направленность, конечность). Выполнение алгоритма обязательно должно привести к решению поставленной задачи, либо к сообщению о том, что при заданных исходных величинах задачу решить невозможно. Алгоритмический процесс не может обрываться безрезультатно. 5. Массовость. Алгоритм пригоден для решения любой задачи из некоторого класса задач, т. е. алгоритм правильно работает на некотором множестве исходных данных, которое называется областью применимости алгоритма. Вопрос: «Возможна ли ситуация, когда способ решения задачи есть, но он не является алгоритмом?» Ответ. Не каждый способ, приводящий к решению задачи, является алгоритмом. Например, опишем следующий способ (метод) проведения перпендикуляра к прямой MN, проходящего через заданную точку A: 1) отложить в обе стороны от точки A на прямой MN циркулем отрезки равной длины с концами B и C; 2) увеличить раствор циркуля до радиуса, в полтора-два раза большего длины отрезков AB и AC; 3) провести указанным раствором циркуля дуги окружностей с центрами B и C так, чтобы они охватили точку A и образовали две точки пересечения друг с другом (D и E); 4) взять линейку, приложить ее к точкам D и E и соединить их отрезком. При правильном построении отрезок пройдет через точку А и будет искомым перпендикуляром. Указанный способ рассчитан на исполнителя-человека. Применяя его, человек, разумеется, построит искомый перпендикуляр. Но, тем не менее, этот способ алгоритмом не является. Прежде всего, оно не обладает свойством детерминированности. Так, в пункте 1 требуется от исполнителя сделать выбор �Содержание отрезка произвольной длины (для построения точек B и C можно провести окружность произвольного радиуса r с центром в точке A). В пункте 2 требуется сделать выбор отрезка в полтора-два раза большего длины отрезков AB и AC. В пункте 3 надо провести дуги, которые также однозначно не определены. Человек-исполнитель, применяющий данный способ к одним и тем же исходным данным (прямой MN и точке A) повторно, получит несовпадающие промежуточные результаты. Это противоречит требованию детерминированности алгоритма. Вышесказанное позволяет дать уточненное понятие алгоритма, которое опять же не является определением в математическом смысле слова, но более формально описывает понятие алгоритма, раскрывает его сущность. Алгоритм это конечная система команд, сформулированная на языке исполнителя, которая определяет последовательность перехода от допустимых исходных данных к конечному результату и которая обладает свойствами дискретности, понятности, детерминированности, результативности и массовости. �Содержание 1.3.4. Способы записи алгоритмов Алгоритм, составленный для некоторого исполнителя, можно представить различными способами: с помощью графического или словесного описания, в виде таблицы, последовательности формул, записанных на алгоритмическом языке, и т. д. Рассмотрим следующие наиболее распространенные формы представления алгоритма: − словесная (запись на естественном языке); − графическая (изображения из графических символов); − псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.); − программная (тексты на языках программирования). Опишем эти способы записи алгоритма более подробно. Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Например, алгоритм нахождения наибольшего общего делителя двух натуральных чисел может быть следующим: 1) задать два числа; 2) если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма; 3) определить большее из чисел; 4) заменить большее из чисел разностью большего и меньшего из чисел; 5) повторить алгоритм с шага 2. Укажем недостатки использования словесной формулировки алгоритма: − описание действий строго неформализуемы; − многословность записей; − неоднозначность толкования отдельных предписаний. Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным. Примером графического представления алгоритма может служить его представление в виде блоксхемы, когда алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, �Содержание проверки условий, управлению повторением действий и т. д.) соответствует геометрическая фигура, представленная в виде блочного символа. Блочные символы соединяются линиями переходов, определяющими очередность выполнения действий. В таблице 1 приведены наиболее часто употребляемые блочные символы. Блок «процесс» применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдельных блоков обработки можно объединять в один блок. Представление отдельных операций достаточно свободно. Таблица 1 Блочные символы Название символа Обозначение и пример заполнения Пояснение Процесс Вычислительное действие или последовательность действий Условие Проверка условий Модификация Начало цикла с заранее известным количеством повторов Предопределенный процесс Вычисления подпрограмме Ввод-вывод Ввод и вывод данных Пуск-останов Начало, конец алгоритма Печать Вывод печать результатов по на Блок «условие» используется для обозначения переходов управления по условию. В каждом таком блоке должны быть указаны вопрос, условие или сравнение, которые он определяет. Блок «модификация» используется для организации циклических конструкций. (Слово «модификация» означает видоизменение, преобразование). Внутри блока записывается параметр цикла, для которого �Содержание указываются его начальное значение, конечное значение и шаг изменения значения параметра для каждого повторения. Блок «предопределенный процесс» используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращений к библиотечным подпрограммам. Недостаток блок-схем в том, что при описании сложных алгоритмов они превращаются в весьма запутанную сеть. Псевдокод представляет собой систему правил, предназначенную для записи алгоритмов с помощью текстовых структур. Он занимает промежуточное место между естественными и формальными языками. С одной стороны, псевдокод близок к естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи. В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, как и в формальных языках, есть служебные слова, смысл которых строго определен. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются. Формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций. Примером псевдокода является школьный алгоритмический язык, описанный в учебнике А.Г. Кушниренко «Основы информатики и вычислительной техники». Общий вид алгоритма на этом языке можно представить следующим образом: Приведем пример записи конкретного алгоритма на школьном алгоритмическом языке. �Содержание Описание алгоритма в словесной, графической формах, на псевдокоде допускает некоторый произвол при изображении команд. Вместе с тем, эти способы позволяют человеку понять суть дела и исполнить алгоритм. Однако для компьютера алгоритм должен быть записан на «понятном» ему языке, на языке программирования. Программа это описание структуры алгоритма на языке программирования. Выбор того или иного способа записи алгоритма зависит от нескольких причин. Так, если для вас наиболее важна наглядность записи алгоритма, то разумно использовать блок-схему. Если алгоритм небольшой, то его можно записать в текстовой форме, при этом команды могут быть пронумерованы или записаны в виде сплошного текста. Если же разрабатываемый вами алгоритм предназначен для исполнения на компьютере, то нужно использовать формальный язык для его записи (язык программирования) и в качестве формы записи алгоритма применять программу. Псевдокод можно, например, использовать как промежуточное звено при переходе к представлению алгоритма в виде программы. �Содержание 1.4. Базовые алгоритмические структуры Вне зависимости от выбранной формы записи элементарные шаги алгоритма (команды) при укрупнении объединяются в алгоритмические конструкции: последовательные, ветвящиеся, циклические, рекурсивные. В 1969 году Эдсгер В. Дейкстра в статье «Структуры данных и алгоритмы» доказал, что для записи любого алгоритма достаточно трех основных алгоритмических конструкций: последовательных, ветвящихся, циклических. Иными словами, алгоритмы можно представлять как некоторые структуры, состоящие из отдельных базовых элементов, а поэтому изучение основных принципов конструирования алгоритмов необходимо начинать с раскрытия сущности этих базовых элементов. Логическая структура любого алгоритма может быть представлена комбинацией трех базовых структур: следование, ветвление, цикл. Характерной особенностью базовых структур является наличие в них одного входа и одного выхода. 1. Базовая структура следование предписывает выполнение последовательности действий, следующих одно за другим, без пропусков и повторений (таблица 2). Таблица 2 Базовая структура следование 2. Базовая структура ветвление обеспечивает в зависимости от результата проверки условия (да или нет) выбор одного из альтернативных путей работы алгоритма. Каждый из путей ведет к общему выходу, так что работа алгоритма будет продолжаться независимо от того, какой путь будет выбран. Структура ветвления существует в четырех основных вариантах (таблица 3): «если иначе», «выбор», «выбор иначе». то», «если то �Содержание Таблица 3 Базовая структура ветвление �Содержание 3. Базовая структура цикл обеспечивает многократное выполнение некоторой совокупности действий, которая называется телом цикла. Существует три основные разновидности циклов (таблица 4): − цикл типа «пока» (или цикл с предусловием) предписывает выполнять тело цикла до тех пор, пока выполняется условие, записанное после слова «пока». Чтобы цикл не повторялся бесконечно необходимо, чтобы в теле цикла осуществлялись действия, приводящие к ситуации, когда условие перестанет быть истинным; − цикл типа «до» (или цикл с постусловием) предписывает выполнять тело цикла до тех пор, пока условие не станет истинным. Чтобы не происходило зацикливания необходимо, чтобы в теле цикла осуществлялись действия, приводящие к ситуации, когда условие станет истинным; − цикл типа «для» (или цикл с параметром) предписывает выполнять тело цикла для всех значений некоторой переменной (параметра цикла) в заданном диапазоне с заданным шагом. �Содержание Таблица 4 Базовая структура цикл Описанные нами базовые алгоритмические структуры при составлении различных алгоритмов могут использоваться и в различных комбинациях. Например, в случае, когда внутри цикла необходимо повторить некоторую последовательность действий, т. е. организовать внутренний цикл, используют структуру «цикл в цикле». �Содержание Вопросы к главе 1 1. Раскройте сущность понятия «алгоритм». 2. С именем какого ученого связано происхождение термина «алгоритм»? 3. Какие алгоритмы были разработаны самыми первыми? 4. В каких науках, по вашему мнению, алгоритмы играют важную роль? Ответ обоснуйте. 5. Приведите примеры алгоритмов, которые вы узнали при обучении в школе, в вузе. 6. Приведите примеры алгоритмов, которыми вы пользуетесь в повседневной жизни. 7. Как вы думаете, существуют ли задачи, которые человек, вообще говоря, умеет решать, не зная при этом алгоритм их решения? Ответ обоснуйте. 8. Что означают слова «алгоритмически разрешимая проблема», «алгоритмически неразрешимая проблема»? 9. Какой вопрос возник перед учеными при их попытке неразрешимость некоторой проблемы? доказать алгоритмическую 10. В какой период времени возникла наука «теория алгоритмов»? 11. С именами каких ученых связано развитие теории алгоритмов? 12. Назовите и охарактеризуйте основные этапы развития теории алгоритмов. 13. Раскройте основные задачи и направления развития современной теории алгоритмов. 14. Почему принято говорить об интуитивном представлении понятия алгоритма? 15. Раскройте сущность понятия «исполнитель алгоритма». 16. Приведите примеры различных исполнителей алгоритма. 17. Что характеризует исполнителя алгоритма? Раскройте суть этих характеристик. 18. Назовите основные свойства алгоритма и раскройте их содержание. 19. Приведите пример алгоритма и покажите, что он удовлетворяет всем основным свойствам алгоритмов. 20. Почему кулинарный рецепт приготовления торта нельзя считать алгоритмом? Какими свойствами алгоритма он не обладает? 21. Какие способы записи алгоритма существуют? В чем их суть? 22. Приведите примеры различных способов записи алгоритмов. 23. Существует ли, по вашему мнению, наилучший способ записи алгоритма? Ответ обоснуйте. 24. Какие базовые алгоритмические структуры существуют? Запишите их на языке блок-схем. �Содержание Задания к главе 1 1. Составьте алгоритм сложения в столбик двух натуральных чисел. Предполагается, что операция сравнения двух натуральных чисел для человека является выполнимой. 2. Переформулируйте способ проведения перпендикуляра к прямой в заданной точке (см. 1.3.3.) так, чтобы он стал алгоритмом. 3. Является ли следующее правило нахождения наибольшего общего делителя двух натуральных чисел алгоритмом? НОД ( a , b )  ?, г де a , b  N a  bq1  r1 , г де 0  r1  b, b  r1q2  r2 , г де 0  r2  r1 , r1  r2 q3  r3 , г де 0  r3  r2 , ......................................... ri  ri 1qi  2  ri  2 , г де 0  ri  2  ri 1 , НОД (116 ,24 )  ? 116  24  4  20, 24  20  1  4, 20  4  5. НОД (116 ,24 )  4. ri 1  ri  2 qi  3 . Действительно: НОД ( a, b)  ri  2 . 116  2  2  29, 24  2  2  2  3. 4. Рассмотрите правило деления десятичных дробей. Выясните, при всех ли значениях десятичных дробей данное правило приведет к точному результату (оборвется на n -м шаге)? Можно ли это правило назвать алгоритмом? 5. Является ли алгоритмом следующая последовательность шагов? 1. исходное число умножим на 2; 2. к полученному числу прибавим 1; 3. определим остаток «у» от деления полученной в п. 2 суммы на 3; 4. разделим исходное число на у; частное будет являться искомым результатом. Здесь исходные данные все натуральные числа. 6. Есть двое песочных часов: на 3 минуты и на 8 минут. Для приготовления эликсира бессмертия его надо варить ровно 7 минут. Как это сделать? Придумайте систему команд исполнителя «Колдун» и запишите последовательность команд этого исполнителя для приготовления эликсира. 7. Составьте в виде блок-схемы алгоритм нахождения факториала числа n. 8. Рассмотрим способ выписывания всех простых чисел в интервале от 1 до некоторого N. Этот способ носит название «Решето Эратосфена», по имени древнегреческого ученого, впервые предложившего данный алгоритм. Для этого выпишем подряд все натуральные числа от 1 до N. Возьмем первое число, большее 1 (это �Содержание будет 2), и зачеркнем каждое второе число, начиная отсчет со следующего за двойкой числа. Затем возьмем первое незачеркнутое число, большее 2 (это будет 3), и зачеркнем каждое третье число, начиная отсчет с числа 3+1 (ранее зачеркнутые числа участвуют в отсчете). Далее возьмем первое незачеркнутое число, большее 3 (это будет 5), и зачеркнем каждое пятое число, начиная отсчет с числа 5 +1. Продолжая так действовать, остановимся тогда, когда первое незачеркнутое число окажется больше N . В результате применения этого алгоритма незачеркнутыми останутся все простые числа, не превосходящие N, и только они. Докажите это. 9. Постройте блок-схемы алгоритмов вычисления по известным x и n следующих выражений с использованием только арифметических действий +, , *, /. Входные параметры: x вещественное, n целое неотрицательное число. В построенных блок-схемах вложенных циклов быть не должно. 1. 1  x  x 2  x 3  x 4    ( 1) n x n ; 2. 1 x  3. 1 x 2 x3 x 4 xn      ( 1) n ; 2! 3! 4! n! n x 2 x 4 x 6 x8 xn       ( 1) 2 (n 2! 4! 6! 8! n! четное натуральное число). 10. Дана последовательность целых чисел a1 , a2 ,, an . Укажите все ошибки в предлагаемой записи алгоритма нахождения максимального и минимального элемента в заданной последовательности. Идея алгоритма такова: разбиваем последовательность на пары; числа в каждой паре упорядочиваем по возрастанию; максимальный элемент ищем среди четных (по месту расположения) элементов последовательности, а минимальный среди нечетных. 1. Разобьем исходную последовательность на пары. Последняя пара может быть неполной, если число n нечетно. n Положим m  2 , если n обработать). 2. 3. четно, и m n 1 2 в противном случае ( m число пар, которые надо Упорядочим числа в каждой паре по возрастанию. Будем элементы в паре обозначать Pk ,1 и Pk , 2 , где k номер пары. 4. Положим min  P1,1 и max  P1, 2 . 5. Положим k  1 . 6. Если Pk , 2  max , тогда max  Pk , 2 . 7. Если Pk ,1  min , тогда min  Pk ,1 . 8. Увеличим k на единицу. 9. Если k  m , конец алгоритма; иначе переход на п. 6. 11. У исполнителя КВАДР две команды, которым присвоены номера: �Содержание 1) прибавь 1, 2) возведи в квадрат. Первая из этих команд увеличивает число на экране на 1, вторая – возводит в квадрат. Программа для исполнителя КВАДР – это последовательность номеров команд. Запишите программу для исполнителя КВАДР, которая преобразует число 5 в число 2500 и содержит не более 6 команд. Если таких программ более одной, то запишите любую из них. 12. У исполнителя ДВАПЯТЬ две команды, которым присвоены номера: 1) отними 2, 2) раздели на 5. Выполняя первую из них, ДВАПЯТЬ отнимает от числа на экране 2, а выполняя вторую, делит это число на 5 (если деление нацело невозможно, ДВАПЯТЬ отключается). Запишите порядок команд в программе, которая содержит не более 5 команд и переводит число 152 в число 2. 13. У исполнителя КАЛЬКУЛЯТОР две команды, которым присвоены номера: 1) отними 2, 2) раздели на 3. Выполняя первую из них, КАЛЬКУЛЯТОР отнимает от числа на экране 2, а выполняя вторую, делит его на 3 (если деление нацело невозможно, КАЛЬКУЛЯТОР отключается). Запишите порядок команд в программе получения из числа 37 числа 3, содержащей не более 5 команд, указывая лишь номера команд. 14. Исполнитель КУЗНЕЧИК живёт на числовой оси. Начальное положение КУЗНЕЧИКА – точка 0. Система команд Кузнечика: Вперед 7: КУЗНЕЧИК прыгает вперёд на 7 единиц, Назад 5: КУЗНЕЧИК прыгает назад на 5 единиц. Какое наименьшее количество раз должна встретиться в программе команда «Назад 5», чтобы КУЗНЕЧИК оказался в точке 19? 15. Исполнитель РОБОТ ходит по клеткам бесконечной вертикальной клетчатой доски, переходя по одной из команд вверх, вниз, вправо, влево в соседнюю клетку в указанном направлении. РОБОТ выполнил следующую программу: вправо вниз вправо вверх влево вверх вверх влево Укажите наименьшее возможное число команд, которое необходимо для того, чтобы РОБОТ вернулся в �Содержание ту же клетку, из которой начал движение. 16. На экране есть два окна, в каждом из которых записано по числу. Исполнитель СУММАТОР имеет только две команды, которым присвоены номера: 1. Запиши сумму чисел в первое окно. 2. Запиши сумму чисел во второе окно. Выполняя команду номер 1, СУММАТОР складывает числа в двух окнах и записывает результат в первое окно, а выполняя команду номер 2, заменяет этой суммой число во втором окне. Напишите программу, содержащую не более 5 команд, которая из пары чисел 1 и 2 получает пару чисел 13 и 4. Укажите лишь номера команд. 17. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: − вверх, − вниз, − влево, − вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно (по отношению к наблюдателю): вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ (также по отношению к наблюдателю): − сверху свободно − снизу свободно − слева свободно − справа свободно Цикл ПОКА < условие > последовательность команд КОНЕЦ ПОКА выполняется, пока условие истинно. В конструкции ЕСЛИ < условие > ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ выполняется команда1 (если условие истинно) или команда2 (если условие ложно) �Содержание Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся. Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)? НАЧАЛО ПОКА снизу свободно ИЛИ справа свободно ПОКА снизу свободно вниз КОНЕЦ ПОКА вправо КОНЕЦ ПОКА КОНЕЦ 1) 7 2) 12 3) 17 4) 21 18. Исполнитель МАШИНКА «живет» в ограниченном прямоугольном лабиринте на клетчатой плоскости, изображенном на рисунке. Серые клетки – возведенные стены, светлые – свободные клетки, по которым МАШИНКА может свободно передвигаться. По краю поля лабиринта также стоит возведенная стенка с нанесенными номерами и буквами для идентификации клеток в лабиринте. Система команд исполнителя МАШИНКА: − вверх, − вниз, − влево, − вправо. При выполнении любой из этих команд МАШИНКА перемещается на одну клетку соответственно (по отношению к наблюдателю): вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится МАШИНКА (также по отношению к наблюдателю): − сверху свободно, − снизу свободно, �Содержание − слева свободно, − справа свободно. Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. При попытке передвижения на любую серую клетку МАШИНКА разбивается о стенку. Сколько клеток приведенного лабиринта соответствуют требованию, что, стартовав в ней и выполнив предложенную ниже программу, МАШИНКА не разобьется? НАЧАЛО ПОКА <снизу свободно> вниз ПОКА <справа свободно> вправо вверх вправо КОНЕЦ 1) 0 2) 7 3) 1 4) 3 19. Автомат получает на вход трёхзначное число. По этому числу строится новое число по следующим правилам. 1. Складываются первая и вторая, а также вторая и третья цифры исходного числа. 2. Полученные два числа записываются друг за другом в порядке убывания (без разделителей). Пример: исходное число 348; суммы: 3+4=7 и 4+8=12; результат: 127. Сколько существует чисел, в результате обработки которых автомат выдаст число 1715? 20. Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями: F(1)=1; F(2)=1; F(n)=F(n- 2)*(n-1), при n>2. Чему равно значение функции F(8)? В ответе запишите только натуральное число. 21. Алгоритм вычисления значения функции F(n) и G(n), где n–натуральное число, задан следующими соотношениями: F(1)=0 F(n)=F(n–1)+n, при n>1 G(1)=1 G(n)=G(n–1)*n, при n>1 �Содержание Чему равно значение функции F(5) + G(5)? 22. Последовательность чисел Фибоначчи задается рекуррентным соотношением: F(1)=1 F(2)=1 F(n)= F(n–2) + F(n–1), при n>2, где n – натуральное число. Чему равно восьмое число в последовательности Фибоначчи? Дополнительные задания Составьте точный план действий, приводящий к решению следующих задач. Можно ли каждый конкретный план назвать алгоритмом? Ответ обоснуйте. 1. Волк, коза и капуста. На берегу реки стоит крестьянин с лодкой, а рядом с ним волк, коза и капуста. Крестьянин должен переправиться сам и перевезти волка, козу и капусту на другой берег. Однако в лодку, кроме крестьянина, помещается либо только волк, либо только коза, либо только капуста. Оставлять же волка с козой или козу с капустой без присмотра нельзя волк может съесть козу, а коза капусту. Как должен вести себя крестьянин? 2. Два встречных поезда, в каждом из которых паровоз и 21 вагон, встретились на дороге с одним тупиком (рис. 2). Тупик вмещает 11 вагонов или 10 вагонов и паровоз. Как поездам разъехаться (т. е. как должны маневрировать машинисты, чтобы каждый поезд продолжил движение в своем направлении)? Рис. 2 3. Ханойская башня. На подставке укреплены три стержня, на левый стержень нанизано несколько колец уменьшающегося размера внизу самое большое кольцо, на нем поменьше, сверху еще меньше и т. п. (рис. 3). Рис. 3 Надо, перемещая по одному кольцу со стержня на стержень, переместить все кольца на правый �Содержание стержень, но при этом ни в какой момент времени большее кольцо на меньшее класть нельзя. Опишите, как надо перекладывать кольца, если в начальный момент на левом стержне: а) 1; б) 2; в) 3; г) 4; д*) 64 кольца. (По преданию перекладыванием 64 колец занимаются монахи в одном из буддийских монастырей. Согласно легенде, в момент, когда они кончат перекладывать кольца, наступит конец света. Прикиньте приблизительно, когда это произойдет, если считать, что монахи перекладывают примерно 1 кольцо в секунду.) 4. Фирма «Электронные приборы» выпустила автоматизированную ванну «Банный комплекс 10», управляемую с помощью 10 кнопок «долить 1 л», «долить 2 л», …, «долить 5 л»; «слить 1 л», «слить 2 л», …, «слить 5 л», при нажатии на которые доливается или сливается указанное количество литров воды. Однако в результате ошибки фирмы все кнопки, кроме «долить 5 л» и «слить 3 л», не работают. Как долить в ванну 3 л воды? Сколько воды при этом пропадет впустую из-за брака фирмы? 5. Два солдата подошли к реке, по которой на лодке катаются двое мальчиков. Как солдатам переправиться на другой берег, если лодка вмещает только одного солдата либо двух мальчиков, а солдата и мальчика уже не вмещает? 6. Петя и Коля играют в следующую игру: на стол кладется 15 спичек. Ребята по очереди берут их со стола, причем за один ход разрешается взять 1, 2 или 3 спички. Выигрывает тот, кто возьмет последнюю спичку. Первым ходит Петя. Как он должен играть, чтобы выиграть? 7. Автоматическое устройство имеет 2 кнопки и экран. При включении на экране загорается число 0. При нажатии на одну кнопку число на экране удваивается (вместо х появляется 2х). При нажатии на другую кнопку число увеличивается на 1 (вместо х появляется х+1). Как надо нажимать на кнопки, чтобы на экране появилось: 1) число 5; 2) число 99; 3) число 99, если разрешается нажимать на кнопки не более 10 раз? 8. Придумайте способ нахождения самой легкой и самой тяжелой из 100 монет различной массы, если можно сделать не более 150 взвешиваний на чашечных весах без гирь. 9. Имеется а) 3, б) 4, в) 5, г) 6 монет, среди которых одна фальшивая (легче других). Придумайте способ нахождения фальшивой монеты за минимальное число взвешиваний на чашечных весах без гирь. 10. Имеется 1000 монет, из которых одна фальшивая (легче других). Придумайте способ нахождения фальшивой монеты за 7 взвешиваний на чашечных весах без гирь. Докажите, что нельзя придумать способ, который гарантирует нахождение фальшивой монеты за 6 взвешиваний. �Содержание Глава 2. Класс рекурсивных функций В первой главе мы говорили о том, что центральным вопросом в теории алгоритмов явился вопрос формализации интуитивного понятия «алгоритм». Попытки различных ученых дать точный математический эквивалент для общего интуитивного представления об алгоритме привели к тому, что были предложены несколько моделей алгоритма (машина Тьюринга, машина Поста, рекурсивные функции, нормальные алгоритмы Маркова и др.). В данной главе мы рассмотрим такую модель алгоритма, как частично-рекурсивные функции. § 1. Введение в теорию рекурсивных функций § 2. Примитивно рекурсивные функции § 3. Частично рекурсивные функции § 4. Взаимосвязь между различными классами рекурсивных функций § 5. Тезис Черча Вопросы к главе 2 Задания к главе 2 �Содержание 2.1. Введение в теорию рекурсивных функций Всякий алгоритм однозначно сопоставляет допустимым начальным данным результат. Это означает, что с каждым алгоритмом однозначно связана функция, которую он вычисляет. Кроме того, возникают естественные вопросы: «Для всякой ли функции существует вычисляющий ее алгоритм?», «Если нет, то для каких функций существует вычисляющий их алгоритм, как описать такие, как говорят, алгоритмически или эффективно вычислимые функции?». Исследование данных вопросов привело ученых (Геделя, Клини, Черча) к созданию в 1930-х гг. теории рекурсивных функций. При этом класс вычислимых функций (названных здесь рекурсивными) получил такое описание, которое весьма напоминает процесс построения аксиоматической теории на базе некоторой системы аксиом. Сначала были выбраны простейшие функции, вычислимость которых очевидна (своего рода аксиомы). Затем были сформулированы некоторые правила, названные операторами, на основе которых можно строить новые функции из уже имеющихся (своего рода «правила вывода»). Тогда требуемым классом функций будет совокупность всех функций, получающихся из простейших с помощью выбранных операторов. Прежде чем приступить к описанию класса рекурсивных функций, приведем ряд вспомогательных определений. Определение 1 Пусть A , B некоторые множества. Совокупность всех упорядоченных пар вида ( a, b) , где a  A , b  B называется декартовым (прямым) произведением A на B и обозначается A  B . Определение 2 Пусть X , Y некоторые множества. Если некоторым элементам множества X поставлены в соответствие однозначно определенные элементы множества Y , то говорят, что задана частичная функция из X в Y . Совокупность тех элементов множества X , у которых есть соответствующие в Y , называется областью определения функции. Совокупность тех элементов множества Y , которые соответствуют некоторым элементам множества X , называется областью значений функции. Если область определения функции из X в Y совпадает с множеством X , то функция называется всюду определенной. Определение 3 X X  X  X (n )    Частичные функции из  в Y называются частичными функциями от n n переменных или n -местными функциями из X в Y . Для записи функций и изучения их свойств пользуются особым формальным языком. Алфавит этого языка состоит из символов, разбитых на три группы: 1. предметные символы a0 , a1 , x1 , y0 ,  ; 2. функциональные символы это буквы a , b, x , y ,  или буквы с нижними индексами это буквы с верхними и, возможно, нижними индексами: �Содержание f (1) , g ( 2 ) , f 0(1) ,  ; 3. символы третьей группы это символы левой, правой скобок и запятой: «(», «)», «,». Конечные последовательности символов, записанные в этом функциональном алфавите, (слова) называются термами. Пример x терм длины 1; f (a ) g ( x, a ) терм длины 4; терм длины 6. �Содержание 2.2. Примитивно рекурсивные функции Подчеркнем, что здесь и в дальнейшем (во всей главе 2) будут рассматриваться функции, заданные на множестве натуральных чисел и принимающие натуральные значения. Функции предполагается брать частичные, т. е. определенные, вообще говоря, не для всех значений аргументов. Определение 1 Функции: 1) O ( x )  0 (нуль-функция), 2) S ( x )  x  1 (функция следования), n 3) I m ( x1 , x 2 ,..., x n )  x m (функция проекции, 1  m  n ) называются простейшими (базисными) функциями. Определение 2 Пусть 1) f – m-местная функция на множестве натуральных чисел N ; 2) g1 , g 2 ,..., g m – n-местные функции на множестве N (считаем, что все функции g1 , g 2 ,..., g m зависят от одних и тех же переменных x1 , x2 ,  xn ). Оператор G, ставящий в соответствие функциям f , g1 , g 2 ,..., g m n -местную h ( x1 ,..., xn )  f ( g1 ( x1 ,..., xn ), g 2 ( x1 ,..., xn ),..., g m ( x1 ,..., xn )) , удовлетворяющую тождеству оператором суперпозиции (подстановки). функцию Причем функция h обозначение  G ( f , g1 , g 2 ,..., g m ) h, называется является, очевидно, суперпозицией функций f и g1 , g 2 ,..., g m . Замечания 1. Если среди функций f , g1 , g 2 ,..., g m из определения 2 имеются частичные функции, то и функция h будет частичной. 2. Функция h на наборе переменных x1 , x2 ,  xn определена тогда и только тогда, когда определены все функции g1 ( x1 ,..., xn ), g 2 ( x1 ,..., xn ),..., g m ( x1 ,..., xn ) и функция f определена на наборе g1 ( x1 ,..., xn ), g 2 ( x1 ,..., xn ),..., g m ( x1 ,..., xn ) . Пример 1 2 4 4 Найдем значение термов G ( I1 , I 3 , I 2 ) и G ( I12 , I13 , I 22 ) . �Содержание Решение 1) G ( I12 , I 34 , I 24 )  I12 ( I 34 , I 24 )  <перейдем к полной форме записи функций I 34 и I 24 >  I12 ( I 34 ( x1 , x2 , x3 , x4 ), I 24 ( x1 , x 2 , x3 , x 4 ))   I 12 ( x3 , x 2 )  x3 . 2 3 2 2 3 2 2 3 2 2) G ( I1 , I1 , I 2 )  I1 ( I1 , I 2 )  I1 ( I1 ( x1 , x 2 , x3 ), I 2 ( x1 , x 2 )) – не определено, так как функции I13 и I 22 имеют различную местность, а не одинаковую. Определение 3 Оператор примитивной рекурсии R каждой ( n  2) -местной функции f ( x1 ,  , xn , y , z ) и n -местной функции g ( x1 ,  , x n ) на множестве N ставит в соответствие ( n  1) -местную функцию обозначение h  R ( f , g ) , удовлетворяющую следующей схеме примитивной рекурсии: h( x1 ,..., xn ,0)  g ( x1 ,..., xn ),  h( x1 ,..., xn , y  1)  f ( x1 ,..., xn , y , h( x1 ,..., xn , y )). Замечания 1. Важно отметить, что независимо от числа аргументов в h , рекурсия ведется только по одной переменной y ; остальные n переменных x1 ,  , xn на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров. 2. Очевидно, что схема примитивной рекурсии однозначно определяет функцию h . Причем, схема примитивной рекурсии выражает каждое значение функции h не только через данные функции f и g , но и через так называемые предыдущие значения определяемой функции h : прежде чем получить значение h ( x1 ,  xn , k ) , придется проделать k  1 вычисление по указанной схеме для y  0, 1, 2,  , k . 3. Про функцию h говорят, что она получена рекурсией из функций f и g . (Напомним, что рекурсией называется способ задания функции, при котором значение функции при определенных значениях аргументов выражается через уже заданные значения функции при других значениях аргументов.) 4. Если функции g и f частичные, то h ( x1 ,  xn , y  1) считается определенной в том и только том случае, когда определены h ( x1 ,  xn , y ) и f ( x1 ,  xn , y , t ) при t  h ( x1 ,  xn , y ) . Иными словами, если h( x1 ,  xn , y0 ) неопределенно, то и h ( x1 ,  xn , y ) неопределенно при y  y0 . 5. Оператор примитивной рекурсии в соответствии с определением 3 мы будем применять и при n  0 . В этом случае схема примитивной рекурсии будет иметь следующий вид: h(0)  const ,  h( y  1)  f ( y , h( y )), �Содержание где g – постоянная одноместная функция, равная числу const . Пример 2 Покажем, что функция s ( x , y )  x  y может быть получена из простейших с помощью оператора примитивной рекурсии. Решение Переобозначим: s 2 ( x, y )  h 2 ( x, y )  x  y . Будем искать: f 3 ( x, y, z ) и g 1 ( x ) . Из схемы примитивной рекурсии имеем: опр  2 1 h ( x,0)  x  0  x  I1 ( x ),  схема пр. рек . опр опр 3 h 2 ( x, y  1)  x  ( y  1)  x  y  1   f ( x , y , h ( x , y ))  опр  f 3 ( x, y ,  x  y) . z Следовательно, g 1 ( x )  I11 ( x ) , а f 3 ( x, y , z )  z  1  S ( z ) . Определение 4 Функция называется примитивно рекурсивной, если она может быть получена из простейших функций O , S , I mn с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии. Пример 3 Функция сложения s ( x , y )  x  y является примитивно рекурсивной. �Содержание 2.3. Частично рекурсивные функции Определение 1 Будем говорить, что n -местная функция  ( x1 , x 2 ,  x n ) получается из ( n  1) -местных функций f1 ( x1 , x2 ,  xn , y ) и f 2 ( x1 , x2 ,  xn , y ) с помощью оператора минимизации M наименьшего числа), если: (или оператора для любых x1 , x2 ,..., xn , y равенство  ( x1 , x2 ,..., xn )  y выполнено тогда и только тогда, когда значения функций f i ( x1 , x2 ,..., xn ,0),..., f i ( x1 , x2 ,..., xn , y  1) f1 ( x1 , x2 ,..., xn ,0)  f 2 ( x1 , x2 ,..., xn ,0),..., (i  1, 2) определены и попарно неравны [т. е. f1 ( x1 , x2 ,..., xn , y  1)  f 2 ( x1 , x2 ,..., xn , y  1) ], а значение f1 ( x1 , x2 ,..., xn , y )  f 2 ( x1 , x2 ,..., xn , y ) . Замечание 1 1. Функции  , f1 , f 2 заданы на множестве натуральных чисел и принимают натуральные значения. 2. Величина  ( x1 , x2 ,..., xn ) в определении 1 равна наименьшему значению аргумента y , при котором выполняется равенство f1 ( x1 , x2 ,..., xn , y )  f 2 ( x1 , x2 ,..., xn , y ) . 3. Используют следующее обозначение: обозн.  ( x1 , x2 ,..., xn )   y  f1 ( x1 , x2 ,..., xn , y )  f 2 ( x1 , x2 ,..., xn , y )  . 4. В частном случае может быть f 2 ( x1 , x2 ,..., xn , y )  0 . Тогда:  ( x1 , x 2 ,..., x n )   y  f1 ( x1 , x 2 ,..., x n , y )  0  . 5. Оператор минимизации называют также  -оператором. Пример 1 Рассмотрим функцию d ( x, y )   z  y  z  x  . Вычислим d (7,2) и d (3,4) . Решение 1). Вычислим d (7,2) . Для этого нужно положить y  2 и, придавая переменой z значения 1, 2, 3…, каждый раз вычислять сумму y  z . Как только она станет равной 7, то соответствующее значение z принять за d (7,2) . z  1: 2  1  3  7 ; z  2: 2 2  4  7 ; �Содержание z  3: 2  3  5  7 ; z  4: 2 4  6  7 ; z  5: 2  5  7 . Следовательно, d (7,2)  5 . 2). Аналогично вычислим d (3,4) . z  1: 4  1  5  3 ; z  2: 4 2  6  3 ; ……………………. Видим, что данный процесс будет продолжаться бесконечно. Следовательно, d (3,4) не определено. Заметим, что вычисления в 1) и 2) можно осуществить более рационально. Действительно: d ( x, y )   z  y  z  x  определено. замечание 1 ( 2 )  x y . Поэтому d (7, 2)  7  2  5 , а d (3,4)  3  4  N , т. е. не Замечание 2 Подчеркнем, что операция минимизации может давать частичные функции даже при применении к всюду определенным функциям. Действительно, в примере 1 функции f1 ( x , y , z )  y  z и f 2 ( x, y , z )  x всюду определены (т. е. определены на всем множестве  ( 3) ), а функция d ( x, y )   z  y  z  x   x  y определена только при x y . В отличие же от оператора минимизации операторы суперпозиции и примитивной рекурсии, примененные к всюду определенным функциям, дают также всюду определенные функции. Замечание 3 Оператор минимизации является удобным средством для построения обратных функций к одноместным функциям. Действительно, функция f 1 ( x )   y  f ( y )  x  (наименьший y , такой, что f ( y )  x ) является обратной для функции f (x ) . Поэтому в применении к одноместным функциям оператор минимизации иногда называют оператором обращения. Пример 2 Найдем функцию, обратную к функции следования S ( x )  x  1 . �Содержание Решение Переобозначим: S ( x )  f ( x )  x  1 . 1 Тогда f ( x )   y  y  1  x   x  1 . Итак, S 1 ( x )  x  1 , x  2,3,4,... . Определение 2 Функция называется частично рекурсивной, если она может быть получена из простейших функций O , S , I mn с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и  -оператора. Определение 3 Если функция частично рекурсивна и всюду определена, то она называется общерекурсивной. Пример 3 Определим, является ли функция d ( x, y )   z  y  z  x  частично рекурсивной. Решение Заметим, что функция d ( x, y )   z  y  z  x  получена с помощью оператора минимизации из функций f1 ( x , y , z )  y  z и f 2 ( x , y , z )  x . В свою очередь: 1) функция f1 ( x, y, z )  y  z является примитивно рекурсивной (поясните, почему), т. е. может быть получена с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии; 2) функция f 2 ( x, y , z )  x равна I11 ( x) , т. е. может быть получена из простейших функций. Таким образом, функция d ( x, y )   z  y  z  x  может быть получена из простейших функций с помощью конечного числа применений операторов суперпозиции, примитивной рекурсии и  оператора, поэтому данная функция является частично рекурсивной. �Содержание 2.4. Взаимосвязь между различными классами рекурсивных функций Обозначим: Ч класс частично рекурсивных функций; класс примитивно рекурсивных функций. Чо класс общерекурсивных функций, Ч пр Рассмотрим вопрос о соотношении введенных классов Ч , Ч о , Ч пр . Очевидны следующие соотношения: 1. Класс частично рекурсивных функций Ч шире класса примитивно рекурсивных функций Ч пр (т. е. Ч пр  Ч ), поскольку для построения частично рекурсивных функций из простейших используется больше средств, чем для построения примитивно рекурсивных функций. 2. Класс примитивно рекурсивных функций Ч пр включается в класс общерекурсивных функций Ч о (т. е. Ч пр  Ч о ), так как все примитивно рекурсивные функции всюду определены. 3. Класс общерекурсивных функций Ч о включается в класс частично рекурсивных функций Ч (т. е. Ч о  Ч ), поскольку среди частично рекурсивных функций встречаются функции, как всюду определенные, так и не всюду определенные (например, d ( x, y )   z  y  z  x  ), и даже нигде не определенные (например, f ( x )   y x  1  y  0  ). Из положений 1–3 можно сделать вывод, что Ч пр  Ч о  Ч (1). Замечание При выяснении соотношений между классами Ч , Ч о , Ч пр ученые долгое время не могли обосновать справедливость следующего включения: Ч пр  Ч о (1). Дело в том, что на тот момент очевидным являлось нестрогое включение ( Ч пр  Ч о ), а вот строгое включение ( Ч пр  Ч о ) оставалось спорным. Ученые не могли указать функцию, которая являлась бы общерекурсивной, но не являлась бы примитивно рекурсивной. Первый пример общерекурсивной функции, не являющейся примитивно рекурсивной, был дан Аккерманом в 1928 г. Построенная им функция в теории алгоритмов получила название функции Аккермана. Раскроем ее суть. Функция Аккермана  ( x, y ) задается соотношениями: (1)  ( x,0)  y  1,  ( 2)  ( x  1,0)   ( x,1),  ( x  1, y  1)   ( x,  ( x  1, y )). (3)  Можно доказать, что данные соотношения однозначно определяют функцию  ( x, y ) . Попробуем вычислить некоторые значения функции Аккермана в соответствии с ее определением: �Содержание 1  (0,0)  1 ; 1  (0,1)  2 ; 2  (1,0)  (0,1)  2 ; 3 1  (1,1)   (0,  (1,0))   (0,2)  3 ; 2  ( 2,0)  (1,1)  3 ; 3 1  (1,2)   (0,  (1,1))   (0,3)  4 ; 2 3 3 1  (3,0)   ( 2,1)   (1,  ( 2,0))   (1,3)   (0,  (1,2))   (0,4)  5. Результаты приведенных вычислений убеждают, что найдется алгоритм вычисления значений функции  ( x, y ) . При этом в процессе вычисления какого-либо значения функции  ( x, y ) в некоторой точке используются вычисленные ранее ее значения в неких предыдущих точках. Этим соотношения (1)–(3) похожи на схему примитивной рекурсии. Но примитивная рекурсия ведется по одному аргументу, а в соотношениях (1)–(3) рекурсия ведется сразу по двум аргументам. Причем существенно усложняется характер упорядочения точек, а, следовательно, и понятие предшествующей точки. Это упорядочение не предопределено заранее, как в схеме примитивной рекурсии, где число n всегда предшествует числу n  1 , а выясняется в ходе вычислений. Возникает вопрос, можно ли вычисление функции Аккермана свести к вычислению по схеме примитивной рекурсии, т. е. будет ли функция Аккермана примитивно рекурсивной. Оказывается, нет, в 1928 г. этот факт доказал Аккерман (идея доказательства того, что функция Аккермана не является примитивно рекурсивной, состоит в обосновании того, что функция Аккермана растет быстрее, чем любая примитивно рекурсивная функция, и поэтому не может быть примитивно рекурсивной). �Содержание 2.5. Тезис Черча Понятие частично рекурсивной функции оказалось исчерпывающей формализацией понятия вычислимой функции. При построении аксиоматической теории высказываний исходные формулы (аксиомы) и правила вывода выбирались так, чтобы полученные в теории формулы исчерпали бы все тавтологии алгебры высказываний. К чему же стремимся мы в теории рекурсивных функций, почему именно так выбрали простейшие функции и операторы для получения новых функций? Рекурсивными функциями мы стремимся исчерпать все мыслимые функции, поддающиеся вычислению с помощью какой-нибудь определенной процедуры механического характера. В теории рекурсивных функций выдвигается соответствующая естественнонаучная гипотеза, носящая название тезис Черча. Тезис Черча Числовая функция тогда и только тогда алгоритмически вычислима, когда она частично рекурсивна. Эта гипотеза не может быть доказана строго математически, она подтверждается практикой, опытом, ибо призвана увязать практику и теорию. Все рассматривавшиеся в математике конкретные функции, признаваемые вычислимыми в интуитивном смысле, оказывались частично рекурсивными. �Содержание Вопросы к главе 2 1. Когда и кем была создана теория рекурсивных функций? Какова ее роль в теории алгоритмов? 2. Раскройте идею построения всех примитивно рекурсивных (частично рекурсивных) функций. 3. Какие функции называются простейшими? Какова область определения каждой простейшей функции? 4. Дайте определение оператора суперпозиции. 5. Приведите пример функции, полученной с помощью оператора суперпозиции. 6. Как вы считаете, какие функции (частичные или всюду определенные) могут быть получены из простейших с помощью оператора суперпозиции? 7. Дайте определение оператора примитивной рекурсии. 8. Приведите пример функции, полученной с помощью оператора примитивной рекурсии. 9. Как вы считаете, какие функции (частичные или всюду определенные) могут быть получены из простейших с помощью оператора примитивной рекурсии? 10. Какие функции называются примитивно рекурсивными. Приведите пример примитивно рекурсивной функции. 11. Дайте определение оператора минимизации. 12. Приведите пример функции, полученной с помощью оператора минимизации. 13. Как вы считаете, какие функции (частичные или всюду определенные) могут быть получены из простейших с помощью оператора минимизации? 14. Проиллюстрируйте, как с помощью оператора минимизации можно построить функцию, обратную к одноместной функции. 15. Какие функции называются рекурсивной функции. частично рекурсивными? Приведите пример частично 16. Какие функции называются общерекурсивными? Приведите пример общерекурсивной функции. 17. Как связаны между собой класс частично рекурсивных функций, класс общерекурсивных функций, класс примитивно рекурсивных функций? 18. Сформулируйте тезис Черча и раскройте его роль в теории алгоритмов. �Содержание Задания к главе 2 1. Докажите, что простейшие функции вычислимы. 2. Найдите значения следующих термов: а) G ( I12 , I13 , I 23 ) ; б) G ( I12 , I13 , I 22 ) ; в) G ( S , G ( S , I11 )) ; г) G ( I11 , O ) ; д) G ( S , G ( S , G ( S , G ( S , I 22)))) ; е) G ( S , G ( S , G ( S , G ( S , G ( I 22 , S , O ))))) . 3. Определите, можно ли получить функцию f ( x )  1 из простейших функций с помощью конечного числа применений оператора суперпозиции? А функции f ( x )  2 , f ( x )  3 и т. д.? 4. Найдите результат применения операции суперпозиции G ( j , f 1, f 2) , если j ( x , y )  x  y и: а) f1 (u , v, z )  u 2 vz , f 2 (u , v, z )  2 u vz ; б) f1 ( x, y , z )  xyz , f 2 ( x, y )  xy 3 ; в) f1 (u , v, z )  u 2 v 2 z , f 2 (u , v, t )  uvt 2 5. Найдите результат применения операции суперпозиции G ( , f 1, f 2 , f 3 ) , если  ( x , y , z )  xy  z и: а) f1 (u , v , z )  uvz 2 , f 2 (u , v , z )  2vz u , f 3 (u , v , z )  u  v  z ; б) f1 ( x, y , z )  xy 3 z , f 2 ( x, y )  xy , f 3 ( x, z )  x  z 2 ; в) f1 (u , v , z )  uv 2 z , f 2 (u , v , t )  u 2  vt , f 3 (v , z , t )  v 2  2 z  5t. 6. Покажите, что следующие функции могут быть получены из простейших с помощью оператора примитивной рекурсии: а) f ( x , y )  xy ; б) f ( x, y )  x y ; 0, если x  0, в) sg ( x)   1, если x  0; 1, если x  0, г) sg ( x )   0, если x  0. �Содержание д) Поскольку рассматриваются лишь функции с целыми неотрицательными аргументами и значениями, то вводиться функция «усеченного вычитания». Она определяется следующим образом: определение x  y  0, если x  y ,   x  y , если x  y. В этом контексте покажите, что функции f ( x )  x  1 и f ( x , y )  x  y могут быть получены из простейших с помощью оператора примитивной рекурсии. е) f ( x, y )  x  y . 7. Найдите арифметическую функцию f  R ( h, g ) , полученную операцией примитивной 3 3 1 1 рекурсии, если g ( x )  I ( x ) , h ( x , y , z )  I ( x , y , z )  1 . Вычислите f ( 2,5) . 8. Найдите результат применения операции примитивной рекурсии h  R ( f , g ) , если g (u )  2u , f (u , y , z )  uyz . 9. Найдите результат применения операции примитивной рекурсии h  R( f , g ) , если f (u , v, y , z )  2 u vz и g (u , v )  u 2 v . 10. Какая функция получается из функций g и h с помощью схемы примитивной рекурсии, если: а) g ( x )  x , h ( x, y , z )  z x ; б) g ( x )  x , h ( x, y , z )  x z ; в) g ( x )  1 , h ( x , y , z )  z  ( x  1) ; г) g ( x )  x , h ( x , y , z )  x  y  f ( x ,0) ? 11. Докажите, что следующие функции примитивно рекурсивны: а) f ( x )  x  6 ; з) f ( x )  x 2  3 x  2 ; б) f ( x )  2 x  1 ; ж) f ( x)  3 x  5 ; в) f ( x )  x  x 2 ; г) f ( x )  x 3  3 ; 2 и) f ( x )  6 x  2 x  8 ; к) f ( x , y )  2 x  3 y ; x д) f ( x )  2 ; л) f ( x, y )  x 2 y ; е) f ( x)  x x ; ё) f ( x)  3x 2 1 м) f ( x, y )  xy  5 ; ; н) f ( x , y )  2 x  y . 12. Верны ли следующие равенства: а)  z [ y  z  x ]  x  y ; в)  y [ y  x  0]  0 ; �Содержание б)  z [ sg z  1]  1 ; г)  y [ y ( y  ( x  1))  0]  0 ? 13. Найдите результат применения операции минимизации  ( x )   y [ f ( x , y )  0] к следующим функциям: а) f ( x, y )  x  2 y ; г) f ( x , y )  y  x  1 ; б) f ( x , y )  y  x ; д) f ( x , y )  x  y  1 ; в) f ( x, y )  8 ; е) f ( x , y )  xy . 14. Докажите, что функция q ( x, y )  x является частично рекурсивной. y 15. Докажите, что функция h( x, y )   z [ y  z  x ] является общерекурсивной. 16. Докажите, что функция f ( x )   y [ x  1  y  0] является частично рекурсивной функцией, нигде не определенной. 17. Найдите функции, обратные к следующим функциям: 0, если x  0, а) sg x   1, если x  0 : б) f ( x )  3 x ; в) f ( x )  x 2 . 18. Изобразите с помощью кругов Эйлера взаимосвязь между следующими классами рекурсивных функций: 1) частично рекурсивные функции всюду определенные (общерекурсивные функции); 2) частично рекурсивные функции не всюду определенные; 3) частично рекурсивные функции нигде не определенные; 4) примитивно рекурсивные функции. �Содержание Глава 3. Машина Тьюринга § 1. Назначение и предпосылки создания машины Тьюринга § 2. Устройство машины Тьюринга § 3. Команды и порядок работы машины Тьюринга § 4. Вычислимые по Тьюрингу функции § 5. Основные операции над машинами Тьюринга § 6. Тезис Тьюринга § 7. Машины Тьюринга и современные электронно-вычислительные машины Вопросы к главе 3 Задания к главе 3 �Содержание 3.1. Назначение и предпосылки создания машины Тьюринга Возникновение машины Тьюринга связано с поиском ученых дать точный математический эквивалент для интуитивного представления об алгоритмах. Данная машина является еще одной широко известной моделью алгоритма. Машина Тьюринга была предложена в 1936 г. (за 9 лет до появления первой ЭВМ) английским математиком Аланом Тьюрингом как абстрактная вычислительная конструкция. Целью ее создания было получение возможности доказательства существования или несуществования алгоритмов решения различных задач. Руководствуясь этой целью, Тьюринг искал как можно более простую, «бедную» алгоритмическую схему, лишь бы она была универсальной. Прежде чем мы начнем знакомиться с машиной Тьюринга, необходимо сделать два общих замечания относительно объектов, с которыми работают алгоритмы. Замечание 1 Одной из причин расплывчивости интуитивного понятия алгоритма является разнообразие объектов, с которыми работают алгоритмы. В вычислительных алгоритмах объектами являются числа. В алгоритме шахматной игры объектами являются фигуры и их позиции на шахматной доске. В алгоритме форматирования текста слова некоторого языка и правила переноса слов. Однако во всех этих и других случаях можно считать, что алгоритм имеет дело не с объектами реального мира, а с некоторыми изображениями этих объектов. Например, есть алгоритм сложения двух целых чисел. Результатом сложения числовых объектов 26 и 22 будет числовой результат 48 . Но мы можем считать, что объектом этого алгоритма является входная последовательность, состоящая из пяти символов: « 26  22 », а результатом является последовательность, состоящая из двух символов « 48 ». При этом мы исходили из того, что имеется набор из 11 различных символов {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, } . Используемые символы будем называть буквами, а их набор алфавитом. В общем случае буквами могут служить любые символы, требуется только, чтобы они были различны между собой, а их число было конечным. Определение 1 Произвольная конечная совокупность символов называется алфавитом. Определение 2 Любая конечная последовательность букв (символов) из некоторого алфавита называется словом в этом алфавите. Количество букв в слове называется длиной слова. Слово, в котором нет букв, называется пустым словом. Пример �Содержание A  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, } 48 алфавит, слово в алфавите A , длина которого равна 2 ; 26  22 слово в алфавите A , длина которого равна 5 . Алгоритм сложения двух целых чисел перерабатывает слово « 26  22 » в слово « 48 ». Итак, объекты реального мира можно изображать словами в различных алфавитах. Это позволяет считать, что объектами работы алгоритмов могут быть только слова. Определение 3 Слово, к которому применяется алгоритм, называется входным словом; слово, получаемое в результате работы алгоритма, называется выходным. Совокупность слов, к которым применим алгоритм, называется областью применимости алгоритма. К сожалению, нельзя доказать, что все возможные объекты можно описать словами, так как само понятие объекта не было формально (т. е. строго) определено. Но можно проверить, что для любого наугад взятого алгоритма, работающего не над словами, его объекты можно выразить так, что они становятся словами, а суть алгоритма от этого не меняется. Замечание 2 Любой алфавит можно заменить другим. Такая замена называется кодированием. Например, пусть каждой букве из первого алфавита ставится в соответствие код, представляющий собой слово во втором алфавите. В качестве второго алфавита достаточно иметь алфавит из двух букв, так как любое слово из любого алфавита можно закодировать в двухбуквенном алфавите с гарантией однозначного восстановления исходного слова. Следовательно, любой алгоритм можно свести к алгоритму над словами в алфавите {0, 1} , а перед применением алгоритма входное слово следует закодировать, после применения алгоритма выходное слово надо раскодировать. Будем считать, что алгоритмы работают со словами, и мы формально описываем объекты-слова, над которыми работают алгоритмы, в некотором алфавите. В дальнейшем для уточнения понятия алгоритма следует формально описать действия над объектамисловами и порядок выполнения этих действий. В качестве такой формальной схемы мы и рассмотрим машину Тьюринга. �Содержание 3.2. Устройство машины Тьюринга Машина Тьюринга является абстрактной машиной, т.е. существует не реально, а лишь в воображении. Машина Тьюринга это строгое математическое построение, математический аппарат (аналогичный, например, аппарату дифференциальных уравнений), созданный для решения определенных задач. Этот математический аппарат был назван «машиной» по той причине, что по описанию его составляющих частей и функционированию он похож на вычислительную машину. Принципиальное отличие машины Тьюринга от вычислительных машин состоит в том, что ее запоминающее устройство представляет собой бесконечную ленту: у реальных же вычислительных машин запоминающее устройство может быть как угодно большим, но обязательно конечным. Машину Тьюринга нельзя реализовать именно из-за бесконечности ее ленты. В этом смысле она мощнее любой вычислительной машины. Машина Тьюринга представляет собой систему, работающую в дискретные моменты времени t  0, 1, 2, 3,  и состоящую из следующих частей (рис. 4): 1. Ленты, разбитой на ячейки и бесконечной в обе стороны. В каждой ячейке может быть записан один символ из конечного алфавита A  {a0 , a1 , a2 ,  , am } , называемого внешним алфавитом. 2. Управляющего устройства, которое может находиться в одном из конечного числа внутренних состояний Q  {q0 , q1 , q 2 ,  , q n } . Число элементов в Q характеризует объем внутренней памяти машины. 3. Считывающей/пишущей головки (автомата), которая может перемещаться вдоль ленты и в каждый момент времени обозревает (считывает) одну из ячеек ленты. С каждой машиной Тьюринга связаны два конечных алфавита: 1) алфавит входных символов A  {a0 , a1 , a2 ,  , am } , в котором условимся считать a0 символом пустой ячейки; 2) алфавит внутренних состояний Q  {q0 , q1 , q 2 ,  , q n } , в котором условимся считать состояние q1 начальным (в этом состоянии машина всегда начинает работать), состояние q0 – заключительным (в этом состоянии машина всегда останавливается). Входное слово размещается на ленте по одной букве в расположенных подряд ячейках. Слева и справа от входного слова находятся только пустые ячейки (в алфавит A всегда входит «пустая» буква a0 символ того, что ячейка пуста). Пример �Содержание На ленте машины Тьюринга записано слово 11*111; автомат обозревает второй символ входного слова, считая справа. �Содержание 3.3. Команды и порядок работы машины Тьюринга Опишем, как машиной Тьюринга осуществляются алгоритмы по переработке входных слов. Функционирование машины Тьюринга происходит в дискретные моменты времени t  0,1, 2, 3, и заключается в следующем. В зависимости от того, какая буква ai обозревается автоматом, а также в зависимости от своего внутреннего состояния q j , автомат машины Тьюринга может выполнять следующие действия: − записать новую букву в обозреваемую ячейку; − выполнить сдвиг по ленте на одну ячейку вправо или влево, остаться на месте; − перейти в новое внутреннее состояние. Таким образом, работа машины Тьюринга определяется системой команд вида: q j ai  q k al X (1) , где qj исходное внутреннее состояние машины; ai считываемый символ; qk новое внутреннее состояние машины; al новый записываемый символ в обозреваемую изначально ячейку ленты машины Тьюринга; X  {Л , П , С} направление движения автомата, обозначаемое одним из символов: Л (влево), П (вправо), С (стоим на месте). Предполагается, что для каждой пары q j ai , где j  1, n , i  0, m имеется точно одна команда вида (1). Как же работает машина Тьюринга? Как этот универсальный исполнитель осуществляет переработку входного слова в выходное слово в соответствии с определенным алгоритмом? Опишем эту работу. Находясь в какой-либо момент времени в незаключительном состоянии (т. е. в состоянии, отличном от q0 ), машина совершает шаг, который полностью определяется ее текущим состоянием q j и символом ai , воспринимаемым ею в данный момент на ленте. При этом содержание шага регламентировано соответствующей командой q j a i  q k a l X , где X  { Л , П , С } . Шаг заключается в том, что: 1) содержимое ai обозреваемой на ленте ячейки стирается и на его место записывается символ al ; 2) машина переходит в новое состояние qk ; 3) машина переходит к обозреванию следующей правой ячейки от той, которая обозревалась только что, если Х  П , или к обозреванию следующей левой ячейки, если Х  Л , или же продолжает обозревать ту же ячейку, если Х  С . �Содержание В следующий момент времени (если qk  q0 ) машина делает шаг, регламентированный командой q k al  q r a s X и т. д. до тех пор, пока не будет достигнуто состояние останова q0 . Как только будет достигнуто заключительное состояние q0 машина Тьюринга остановится, при этом последовательность символов, записанных в этот момент на ленте машины Тьюринга, будет являться выходным словом. Ниже приведем несколько определений основных понятий, связанных с функционированием машины Тьюринга. Определение 1 Совокупность всех команд машины Тьюринга, описывающей определенный алгоритм, называется программой (или функциональной схемой) машины Тьюринга. Замечание Программа машины Тьюринга может записываться либо «цепочкой» команд через запятую, либо в виде таблицы (см. табл. 5), в каждой клетке которой записана команда. Отметим, что таблица, определяющая порядок работы машины Тьюринга, не является в прямом смысле слова программой, так как ее предписания выполняются не последовательно, одно за другим, а описывают преобразования символов входного слова, находящегося на ленте. Кроме того, подчеркнем, что программа машины Тьюринга с внешним алфавитом A  {a0 , a1 , a2 ,  , am } и алфавитом внутренних состояний Q  {q0 , q1 , q 2 ,  , q n } содержит ровно n ( m  1) команд (поясните почему). Таблица 5 Общий вид записи программы машины Тьюринга A a0 a1  ai  am q0       q1                Q qj    Л  q k al  П С         qn       �Содержание Определение 2 Под k -й конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k -го шага (или слово в алфавите A , записанное на ленту к началу k -го шага), с указанием того, какая ячейка обозревается в этот шаг и в каком внутреннем состоянии находится машина. Конфигурация называется заключительной, если состояние, в которой при этом находится машина, заключительное. Определение 3 Активной зоной конфигурации назовем минимальную часть ленты машины, обозреваемую ячейку, а также все ячейки, в которых записаны непустые символы. содержащую Определение 4 Будем говорить, что непустое слово  в алфавите A \ {a0 }  {a1 , a 2 ,  , am } воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю справа ячейку из тех, в которых записано слово  . Определение 5 Стандартное положение называется начальным, если машина, воспринимающая стандартном положении, находится в начальном состоянии q1 . слово в Определение 6 Будем говорить, что слово  перерабатывается машиной в слово  , если от слова  , воспринимаемого в начальном стандартном положении, машина после выполнения конечного числа команд приходит к слову  , воспринимаемому в положении останова (в заключительном состоянии). Определение 7 Если в программе машины Тьюринга нет команды, приводящей машину в состояние останова, или машина в процессе работы не приходит в состояние q0 , то говорят, что машина Тьюринга неприменима к данному входному слову. Машина Тьюринга применима к входному слову только в том случае, если, начав работу над этим входным словом, она рано или поздно дойдет до состояния останова. �Содержание Пример Дана машина Тьюринга с внешним алфавитом A  {a0 ,1} , алфавитом внутренних состояний Q  {q0 , q1 , q2 } и со следующей функциональной схемой: q1a0  q2 a0 П ; q2 a0  q01C ; q11  q11П ; q21  q21П . Определим, в какое слово перерабатывает эта машина слово 1 a0 1, исходя из стандартного начального положения. Решение Будем последовательно выписывать конфигурации машины при переработке ею данного слова. Конфигурация (1) является начальной. Здесь автомат обозревает крайний правый символ входного слова, а машина находится в состоянии q1 . Поэтому применяем команду q11  q11П , в результате чего будет осуществлен переход к следующей конфигурации (2). В конфигурации (2) автомат обозревает пустую ячейку (символ a0 ), а машина находится в состоянии q1 . Поэтому используем команду q1a0  q2 a0 П . После ее применения состояние машины Тьюринга будет характеризоваться конфигурацией (3). В конфигурации (3) автомат обозревает символ a0 , а машина находиться в состоянии q2 , поэтому применяем команду q2 a0  q01С . В результате мы будем иметь конфигурацию (4). В конфигурации (4) машина находится в состоянии q0 , т. е. в состоянии останова. Поэтому последовательность символов внешнего алфавита на ленте в этот момент времени образует выходное �Содержание слово. Иными словами, исходное слово 1 a0 1 переработано данной машиной Тьюринга в выходное слово 1 a0 1 a0 1. Полученную последовательность конфигураций (1)–(4) можно записать более коротким способом: 1a0 q11  1a01q1a0  1a01a0 q2 a0  1a01a0 q01 (5) Подчеркнем, что в записи (5) важно следить за тем, чтобы в каждый момент времени внутреннее состояние машины Тьюринга qi было записано перед символом обозреваемой ячейки. �Содержание 3.4. Вычислимые по Тьюрингу функции В связи с тем, что машина Тьюринга осуществляет переработку каждого входного слова в выходное слово в соответствии с определенным алгоритмом, можно сказать, что машине Тьюринга соответствует некоторая словарная функция, которая каждому элементу из области определения (входному слову) ставит в соответствие единственный элемент из области значений (выходное слово). Здесь областью определения и областью значения словарной функции являются множества конечных слов в некоторых алфавитах, причем в случае, когда будут существовать слова из области определения, к которым данная машина Тьюринга неприменима, словарная функция будет являться частичной. Вышесказанное раскрывает взаимосвязь машины Тьюринга с понятием функции. Определение 1 Функция называется вычислимой по Тьюрингу, если существует машина Тьюринга, вычисляющая ее, т. е. такая машина Тьюринга, которая вычисляет ее значения для тех наборов значений аргументов, для которых функция определена, и работающая вечно, если функция для данного набора значений аргументов не определена. Замечания 1. Подчеркнем, что в определении 1 речь идет о функциях (возможно частичных, т. е. не всюду определенных), заданных на множестве натуральных чисел и принимающих также натуральные значения. 2. Условимся, как записывать на ленте машины Тьюринга значения x1 , x2 ,  , xn аргументов функции f ( x1 , x2 ,  , xn ) , из какого положения начинать переработку исходного слова и, наконец, в каком положении получать значение функции. Это можно делать, например, следующим образом. Значения x1 , x2 ,  , xn 01 101 10  01 10 x1 x2 xn аргументов будем располагать на ленте в виде следующего слова: x 1  1 , 0  0  0 x . Таким (1). Здесь полезно ввести следующие обозначения: 1 x x1 x x2 xn образом, предыдущее слово (1) можно представить следующим образом: 01 01 0  01 0 . Далее начинать переработку данного слова будем из стандартного начального положения, т. е. из положения, при котором в состоянии q1 обозревается крайняя правая единица записанного слова. Если функция f ( x1 , x2 ,  , xn ) определена на данном наборе значений аргументов, то в результате на ленте должно быть записано подряд f ( x1 , x2 ,  , xn ) единиц, т. е. 1 f ( x , x 1 2 ,, x n ) ; в противном случае машина должна работать бесконечно, т. е. никогда не приходить в состоянии останова q0 . При выполнении всех перечисленных условий будем говорить, что машина Тьюринга вычисляет данную функцию. Таким образом, сформулированное определение 1 становится строгим. Пример 1 �Содержание Разработаем программу машины Тьюринга, вычисляющую функцию S ( x )  x  1 . Решение Запишем исходную конфигурацию машины Тьюринга. Для того чтобы входное слово 01x 0 было переработано машиной Тьюринга в слово 01 x 10 , нужно применить следующие команды: q11  q11П ; q1 0  q01С . В результате заключительная конфигурация будет иметь вид: Отметим, что приведенное решение не единственное. Замечание При составлении программы машины Тьюринга, вычисляющей некоторую функцию f , мы не очень строго относимся к тому, в каком начальном положении машина начинает работать (часто это бывает стандартное начальное положение), в каком завершает работу и как эта работа протекает. В связи с этим, рассматривают более сильное понятие вычислимости функции на машине Тьюринга понятие правильной вычислимости. Определение 2 Будем говорить, что машина Тьюринга правильно вычисляет функцию f ( x1 , x2 ,  , xn ) , если начальное слово q1 01x 01x 0  01x 0 она переводит в слово q0 01 f ( x , x 1 2 n 1 2 ,, x n ) 0  0 и при этом в процессе работы не пристраивает к начальному слову новых ячеек на ленте ни слева, ни справа. Если же функция f не определена на данном наборе значений аргументов, то, начав работать из указанного положения, она никогда в процессе работы не будет надстраивать ленту слева. Пример 2 Разработаем программу машины Тьюринга, правильно вычисляющую функцию S ( x )  x  1 . �Содержание Решение Запишем исходную конфигурацию машины Тьюринга (1). Для того чтобы входное слово 01x 0 было переработано машиной Тьюринга в слово 01x 10 (причем заключительная конфигурация должна иметь вид q0 01x 10 ), нужно применить следующие команды: q1 0  q2 0 П , q21  q21П , q2 0  q31Л , q31  q31Л , q3 0  q0 0С . В итоге получим заключительную конфигурацию (2). �Содержание 3.5. Основные операции над машинами Тьюринга Прямое построение машин Тьюринга для решения даже простых задач может оказаться затруднительным. Однако существуют приемы, которые облегчают данный процесс, если использовать способы сочетания программ нескольких машин в результирующую программу. Рассмотрим основные способы сочетания машин Тьюринга. 1. Суперпозиция машин Пусть даны две машины Тьюринга T1 и T2 , которые вычисляют соответственно словарные функции f1 ( P ) и f 2 ( P) в одном и том же алфавите. Тогда существует машина Тьюринга T , которая вычисляет функцию f ( P )  f 2 ( f1 ( P )) . При этом для любого слова P функция f (P ) определена в том и только том случае, когда f1 ( P ) определена и f 2 ( f1 ( P )) определена. Программа машины T строится так: состояния машины T2 переобозначим так, чтобы они отличались от состояний машины T1 . Начальное состояние q11 машины T1 объявим начальным q1 для машины T , заключительное состояние q02 машины T2 объявим заключительным q0 для машины T . Заключительное состояние q01 машины T1 отождествим с начальным состоянием q12 машины T2 . Полученные T2 команды для обеих машин объединяем в одну программу. Рассмотрим начальную конфигурацию q1 P (в состоянии q1 обозревается первый символ входного слова P ). Поскольку q1  q11 начальное состояние машины T1 , то вначале машина T будет работать как T1 . Если машина T1 будет применима к q11 P , то на некотором шаге получим конфигурацию q01 f1 ( P ) 1 2 . А так как q0  q1 начальное состояние для машины T2 , то теперь машина T будет действовать как T2 . Если машина T2 будет применима к q01 f1 ( P ) , то на некотором шаге будет получена конфигурация q 02 f 2 ( f1 ( P )) , которая является заключительной для машины T , так как q02  q0 . Если машина T1 1 окажется неприменимой к q11 P или машина T2 окажется неприменимой к q0 f1 ( P ) , то машина T будет неприменимой к q1 P . называется суперпозицией Машина T суперпозицию изображают так: машин T1 и T2 P  f1 ( P )  f1 ( f 2 ( P )) T1 T2 и обозначается T1T 2 . Схематически . 2. Соединение машин Пусть даны машины Тьюринга T1 и T2 , вычисляющие словарные функции f1 ( P ) и f 2 ( P) соответственно. Тогда существует машина T , которая начальную конфигурацию q1 P переводит в заключительную конфигурацию q0 f1 ( P ) * f 2 ( P ) , если f1 ( P ) и f 2 ( P) определены, и неприменима в противном случае. Здесь * новый символ, не входящий во внешний алфавит машин T1 и T2 . Машина T называется соединением машин T1 и T2 и обозначается T1 *T2 . Существование машины T вытекает из следующих неформально описываемых конструкций. �Содержание Лента машины T является двухэтажной. В качестве внешнего алфавита T берут двухэтажные буквы b    , где a и b буквы внешнего алфавита машин T1 и T2 . Каждой букве a внешнего алфавита a  a0  машин T1 , T2 ставится в соответствие двухэтажная буква   , где a0 a  символ пустой буквы. Тогда  a0  a0   . Машина T будет работать слову P  ai  ai ставится в соответствие двухэтажное слово   a  a i i k   1  a 0  a 0   ai  ai   ai  ai   f 2 ( P )    a0  a0           . Причем здесь существование так:        a i  a i   a i  a i   f1 ( P )   f1 ( P )   f1 ( P ) * f 2 ( P )  машин Тьюринга для реализации каждого шага очевидно. 1 1 k k 1 k 1 k 1 k 3. Ветвление машин Пусть даны машины Тьюринга T1 и T2 , вычисляющие словарные функции f1 ( P ) и f 2 ( P) соответственно, которые заданы в одном и том же алфавите. Тогда существует машина Тьюринга T , которая начальную конфигурацию q1 * P , где   {0,1} , переводит в заключительную конфигурацию q0 f1 ( P ) , если   0 и в q0 f 2 ( P ) , если   1 . Машина T называется разветвлением машин T1 и T2 и обозначается T1vT2 . Схематически разветвление представлено на рис. 6. Рис. 6. Схематическое представление операции разветвления машин Тьюринга Существование машины T вытекает из следующих конструкций. Пусть q11 и q12 начальные состояния машин T1 и T2 соответственно. Считаем, что множества внутренних состояний машин не пересекаются. Объединим программы машин T1 и T2 , добавив новое начальное состояние q1 и 1 2 2 2 следующие команды: q1 0  q11a0 П , q11 *  q11a0 П , q1 1  q1 a 0 П , q1 *  q1 a 0 П . Теперь заключительные состояния q01 и q02 машин T1 и T2 объединим, а полученное состояние q0 считаем заключительным для машины T . Если q1 * P начальная конфигурация, то машина T через 2 шага перейдет в конфигурацию q11 P , если   0 , и в конфигурацию q12 P , если   1 , а затем будет работать как машина T1 или T2 соответственно. �Содержание 4. Реализация цикла Важным приемом в программировании является разбиение решаемой задачи на циклы. После выполнения каждого «прохода» цикла проверяется выполнимость некоторого условия. Если условие выполнено, то выдается результат, если нет, то цикл повторяется. Точнее, процедура задается так. Пусть имеем словарные функции f1 и f 2 и некоторый предикат  на словах. (Напомним, что n местным предикатом, определенным на множествах M 1 ,  , M n , называют выражение, содержащее n переменных x1 ,  , xn , превращающееся в высказывание при подстановке вместо этих переменных конкретных элементов из множеств M 1 ,  , M n соответственно.) Условимся значения предиката  обозначать 0, 1. Для произвольного слова P проверяется верно ли, что  ( P )  1 , если да, то выдается ответ f1 ( P ) . Если  ( P )  0 , то вычисляется P  f 2 ( P) . Затем проверяется верно ли, что  ( P )  1 , если да, то выдается ответ f1 ( P) ; если же окажется, что  ( P )  0 , то вычисляется P  f 2 ( P) и т. д. Оказывается, существует машина Тьюринга T , реализующая данную процедуру. Пусть существуют машины Тьюринга для вычисления функций f1 и f 2 и предиката  . Обозначим их T1 , T2 , T соответственно. Пусть T0 машина, которая оставляет всякое слово P без изменения. Машина T строится в соответствии со схемой, представленной на рис. 7. 2 Дадим некоторые пояснения к представленному рисунку. Заключительные состояния q01 и q 0 машин T1 и T2 не объединяются, а считаются различными. Состояние q01 объявляется заключительным для T1 , а q02 отождествляется с начальным состоянием q1 для T . Заключительное состояние для машины T *T0 объявляется начальным для T1vT2 . Из изложенного следует, что если T1vT2 работает как T1 , то полученное ею значение является выходом T , если же T1vT2 работает как T2 , то полученное ею значение снова подается на вход машины T . Рис. 7. Схематическое представление реализации цикла в машине Тьюринга Описанные выше операции над машинами Тьюринга (суперпозиция машин, соединение машин, ветвление машин, реализация цикла), являются удобным инструментом для конструирования машин Тьюринга. Ниже приведем список машин Тьюринга, которые часто используются в качестве составляющих для других машин: 1. A (перенос нуля): q1 001 x 0  q0 01 x 00 . 2. Б  (сдвиг вправо): q1ai 1x 0  ai 1x q0 0 . 3. Б  (сдвиг влево): 01x q1ai  q0 01x ai . �Содержание 4. B (транспозиция): q1 01 x 01 y 0  q0 01 y 01 x 0 . x x x x 5. K (копирование): q1 01 00 0  q 0 01 01 0 . x x 6. Л (стирающая машина): q1 01 0  q 0 00 0 . x 1 x 7. R (удаление 1): q1 01 0  q 0 01 00 . x x 1 8. S (добавление 1): q1 01 0  q 0 01 0 . В качестве упражнения читателю предлагается написать программы для вышеуказанных машин Тьюринга. Мы же приведем пример, как могут быть использованы эти машины для конструирования более сложной машины Тьюринга. Пример Разработаем машину Тьюринга, правильно вычисляющую функцию I 23 ( x1 , x2 , x3 )  x2 . Решение В соответствии с определением функции, правильно вычислимой на машине Тьюринга, мы должны переработать начальное слово q1 01x 01x 01x 0 в слово q0 01x 0 . Для этого будем использовать машины Тьюринга из списка (1)–(8). 1 2 3 2 q1 01x1 01x2 01x3 0  (указано, что будем применять машину (4)); ( 4) q 01x2 01x1 01x3 0 i1 B:     (результат применения машины (4)); ( 2) Б : 01x2 qi2 01x1 01x3 0    (результат применения машины (2)); (6) 01x2 qi3 00 x1 01x3 0 Л :    (результат применения машины (6)); ( 2) Б : 01x2 00 x1 qi4 01x3 0    (результат применения машины (2)); Л : 01x2 00 x1 qi5 00 x3 0    (результат применения машины (6)); (6) ( 3) 01x2 qi6 00 x1 00 x3 0 Б :    (результат применения машины (3));  ( 3) x x x Б  : q0 01 2 00 1 00 3 0 (результат применения машины (3)). �Содержание 3 Таким образом, функция I 2 ( x1 , x 2 , x3 )  x 2 вычисляется путем последовательного применения машин B , Б  , Л , Б  , Л , Б  , Б  . Подчеркнем, что нами приведена лишь общая схема реализации машины Тьюринга, правильно вычисляющей данную функцию (для написания же полной программы нужно строго следить за внутренним состоянием машины на каждом шаге ее работы). �Содержание 3.6. Тезис Тьюринга Вернемся к интуитивному представлению об алгоритмах. Напомним, что одно из свойств алгоритма заключается в том, что он представляет собой единый способ, позволяющий для каждой задачи из некоего бесконечного множества задач за конечное число шагов найти ее решение. На понятие алгоритма можно взглянуть и с несколько иной точки зрения. Каждую задачу из бесконечного множества задач можно выразить (закодировать) некоторым словом некоторого алфавита, а решение задачи каким-то другим словом того же алфавита. В результате получим функцию, заданную на некотором подмножестве множества всех слов выбранного алфавита и принимающую значения на множестве всех слов того же алфавита. Решить какую-либо задачу значит найти значение этой функции на слове, кодирующем данную задачу. А иметь алгоритм для решения всех задач данного класса значит иметь единый способ, позволяющий за конечное число шагов «вычислить» значения построенной функции для любых значений аргументов из ее области определения. Таким образом, алгоритмическая проблема по существу, проблема о вычислении значений функции, заданной в некотором алфавите. Остается уточнить, что значит уметь вычислять значения функции. Это значит вычислять значения функции с помощью подходящей машины Тьюринга. Для каких же функций возможно их тьюрингово вычисление? Многочисленные исследования ученых, обширный опыт показали, что такой класс функций чрезвычайно широк. Каждая функция, для вычисления значений которой существует какойлибо алгоритм, оказывалась вычислимой посредством некоторой машины Тьюринга. (Это можно обосновать тем, что язык Тьюрингова программирования содержит основные операторы программирования и позволяет осуществлять последовательное выполнение программ, параллельное их соединение, использовать условные переходы, реализовать цикл). Это является основанием для предположения о том, что для всех процедур, претендующих называться алгоритмическими, существует (при подходящем кодировании) реализующая их машина Тьюринга. Данное предположение носит название тезиса Тьюринга. Тезис Тьюринга Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция является вычислимой по Тьюрингу, т. е. когда она может вычисляться на подходящей машине Тьюринга. Это означает, что строго математическое понятие вычислимой (по Тьюрингу) функции является по существу идеальной моделью взятого из опыта понятия алгоритма. Данный тезис есть не что иное, как аксиома, постулат, выдвигаемый нами, о взаимосвязях нашего опыта с той математической теорией, которую мы под этот опыт хотим подвести. Конечно же, данный тезис в принципе не может быть доказан средствами математики, потому что он не имеет внутриматематического характера (одна сторона в тезисе понятие алгоритма не является точным математическим понятием). Он выдвинут исходя из опыта, и именно опыт подтверждает его состоятельность. Впрочем, не исключается принципиальная возможность того, что тезис Тьюринга будет опровергнут. Для этого должна быть указана функция, которая вычислима с помощью какого-нибудь алгоритма, но не вычислима ни на какой машине Тьюринга. Но такая возможность представляется маловероятной (в этом одно из значений тезиса): всякий алгоритм, который будет открыт, может быть реализован на �Содержание машине Тьюринга. �Содержание 3.7. Машины Тьюринга и современные электронно-вычислительные машины Изучение машин Тьюринга и практика составления программ для них закладывают фундамент алгоритмического мышления, сущность которого состоит в том, что нужно уметь разделять тот или иной процесс вычисления или какой-либо другой деятельности на простые составляющие шаги. В машине Тьюринга расчленение (анализ) вычислительного процесса на простейшие операции доведено до предельной возможности: распознавание единичного рассмотренного вхождения символа, перемещение точки наблюдения данного ряда символов в соседнюю точку и изменение имеющейся в памяти информации. Конечно, такое мелкое дробление вычислительного процесса, реализуемого в машине Тьюринга, значительно его удлиняет. Но логическая структура процесса, расчлененного, образно выражаясь, до атомарного состояния, значительно упрощается и предстает в некотором стандартном виде, весьма удобном для теоретических исследований (именно такое расчленение на простейшие составляющие вычислительного процесса на машине Тьюринга дает еще один косвенный аргумент в пользу тезиса Тьюринга: всякая функция, вычисляемая с помощью какого-либо алгоритма, может быть вычислена на машине Тьюринга, потому что каждый шаг данного алгоритма можно расчленить на еще более мелкие операции, которые реализуются в машине Тьюринга.) Таким образом, понятие машины Тьюринга есть теоретический инструмент анализа алгоритмического процесса, а значит, анализа существа алгоритмического мышления. В современных ЭВМ алгоритмический процесс расчленен не на столь мелкие составляющие, как в машинах Тьюринга. Наоборот, создатели ЭВМ стремятся к известному укрупнению выполняемых машиной процедур (на этом пути, конечно, есть свои ограничения). Так, для выполнения операции сложения на машине Тьюринга составляется целая программа, а в современной ЭВМ такая операция является простейшей. Машина Тьюринга обладает бесконечной внешней памятью (неограниченная в обе стороны лента, разбитая на ячейки). Но ни в одной реально существующей машине бесконечной памяти быть не может. Это говорит о том, что машины Тьюринга отображают потенциальную возможность неограниченного увеличения объема памяти современных ЭВМ. Можно провести более подробный сравнительный анализ работы современной ЭВМ и машина Тьюринга. В большинстве ЭВМ принята трехадресная система команд, обусловленная необходимостью выполнения бинарных операций, в которых участвует содержимое сразу трех ячеек памяти. Например, число из ячейки a умножается на число из ячейки b, и результат отправляется в ячейку c. Существуют ЭВМ двухадресные и одноадресные. Так, одноадресная ЭВМ работает следующим образом: вызывается (в сумматор) число из ячейки a; в сумматоре происходит, например, умножение этого числа на число из ячейки b; результат отправляется из сумматора в ячейку c. Машину Тьюринга можно считать одноадресной машиной, в которой система одноадресных команд упрощена еще больше: на каждом шаге работы машины команда предписывает замену лишь единственного знака, хранящегося в обозреваемой ячейке, а адрес обозреваемой ячейки при переходе к следующему такту может меняться лишь на единицу (обозрение соседней справа или слева ячейки ленты) или не меняется вовсе. Это удлиняет процесс, но в то же время резко унифицирует его, делает стандартным. Подводя итоги, можно сказать, что современные ЭВМ есть некие реальные физические модели машин Тьюринга, огрубленные с точки зрения теории, но созданные в целях реализации конкретных вычислительных процессов. В свою очередь, понятие машины Тьюринга и теория таких машин есть теоретический фундамент и обоснование современных ЭВМ. �Содержание Вопросы к главе 3 1. Кем и когда была разработана машина Тьюринга? 2. Сформулируйте цель создания машины Тьюринга. 3. Что называется алфавитом? Приведите пример какого-либо алфавита. 4. Что называется словом? Какое слово считается пустым? Приведите пример слова, длина которого равна 7. 5. Поясните, что применительно к алгоритму называют входным словом, выходным словом. 6. Поясните сущность операции кодирования. Приведите пример какой-либо кодировки. 7. Как вы считаете, машина Тьюринга 8. Опишите основные составные части машины Тьюринга. Ответ проиллюстрируйте. 9. Раскройте суть алфавитов (внешнего и внутреннего), с которыми работает машина Тьюринга. это реальная или абстрактная машина? Ответ поясните. 10. В каком внутреннем состоянии машина Тьюринга начинает работать? В каком останавливается? 11. В чем суть следующей команды машины Тьюринга: q s an  qt am X , где X  { П , Л , С } ? 12. Что представляет собой программа (функциональная схема) машины Тьюринга? 13. Сколько команд может содержать программа машины Тьюринга, если ее внешний алфавит A  {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} , а алфавит внутренних состояний Q  {q0 , q1 , q2 , q3 } ? 14. Что представляет собой конфигурация машины Тьюринга на i -шаге ее работы? 15. Что понимают под активной зоной конфигурации машины Тьюринга? 16. Что означают слова «слово p положении»? воспринимается машиной Тьюринга в стандартном 17. Чем характеризуется стандартное начальное положение машины Тьюринга? 18. Что означают слова «слово p1 перерабатывается машиной Тьюринга в слово p2 »? 19. Когда говорят, что машина Тьюринга применима (неприменима) к входному слову? 20. Какая функция называется вычислимой по Тьюрингу? 21. Что означают слова «машина Тьюринга работает вечно»? 22. Запишите начальную и заключительную конфигурацию для машины Тьюринга, вычисляющей функцию f ( x, y , z )  x  y  z , в том числе и для вычисления ее значения в точке ( 4,1,5) . 23. Какая функция называется правильно вычислимой по Тьюрингу? Является ли правильно вычислимая по Тьюрингу функция вычислимой по Тьюрингу? 24. Перечислите, какие основные операции можно выполнять с машинами Тьюринга. 25. Раскройте суть суперпозиции машин Тьюринга. �Содержание 26. Раскройте суть соединения машин Тьюринга. 27. Раскройте суть ветвления в машине Тьюринга. 28. Раскройте суть реализации цикла в машине Тьюринга. 29. Назовите, какие машины Тьюринга часто используются в качестве составляющих для других машин Тьюринга. 30. Сформулируйте тезис Тьюринга и раскройте его роль в теории алгоритмов. 31. Выделите общее и различное между машинами Тьюринга и современными электронновычислительными машинами. �Содержание Задания к главе 3 1. Опишите, какой алгоритм выполняет данная машина Тьюринга. Известно, что в начальном состоянии автомат обозревает самый левый символ входного слова. К каким словам, составленным из символов внешнего алфавита применима эта машина Тьюринга? 2. Опишите, какой алгоритм выполняет данная машина Тьюринга. К каким словам, составленным из символов внешнего алфавита, применима машина? Какое условие надо наложить на начальное положение автомата для того, чтобы результат применения машины к произвольному слову из алфавита был одним и тем же? 3. Опишите, какой алгоритм выполняет данная машина Тьюринга. Автомат в начальном состоянии обозревает самый правый символ входного слова. К каким словам, составленным из символов внешнего алфавита применима машина? 4. Покажите, что машина Тьюринга обладает всеми свойствами алгоритма. 5. Дана машина Тьюринга с внешним алфавитом A  {a01} , алфавитом внутренних состояний Q  {q0 , q1 , q 2 , q3 , q 4 , q5 , q6 , q7 } и со следующей функциональной схемой (программой): Изображая на каждом такте работы машины получающуюся конфигурацию, определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из начального стандартного положения: а) 11111; е) 1 a0 111 a0 a0 1111; �Содержание б) 111111; в) 1111; г) 1111111; д) 111; ж) 11 a0 a0 111111; з) 11 a0 111. 6. Остановится ли когда-нибудь заданная машина Тьюринга, если она начнет перерабатывать следующее слово, начав в состоянии q1 обозревать ячейку, в которой записана самая левая буква перерабатываемого слова: а) 1111 a0 1; б) 11111; в) 1 a0 1 a0 1? Если машина остановится, то какова ее заключительная конфигурация? 7. Машина Тьюринга с внешним алфавитом A  {a0 ,1} определяется следующей функциональной схемой: Остановится ли когда-нибудь эта машина, если она начнет перерабатывать следующее слово (в начальный момент в состоянии q1 машина обозревает ячейку, в которой записана самая левая буква перерабатываемого слова): а) 111 a0 a0 1; б) 11 a0 a0 11 a0 1; в) 111111? Если остановка происходит, то какое слово получается в результате, какая ячейка и в каком (перед остановкой) состоянии обозревается? 8. Остановится ли когда-нибудь машина Тьюринга с внешним алфавитом A  {a0 ,1} и функциональной схемой: при переработке следующих слов (в начальный момент головка машины обозревает ячейку ленты, в которой записана самая левая буква перерабатываемого слова): �Содержание а) 111 a0 1 a0 1; в) 1 a0 1 a0 1 a0 1? б) 1111; 9. Машина Тьюринга определяется следующей функциональной схемой. Определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из начального стандартного состояния. После этого постарайтесь усмотреть общую закономерность в работе машины: а) 111*111; б) 1111*11; в) 111*1; г) 1*11; д) 11*111; е) 11111*; ж) *1111 10. Машина Тьюринга определяется следующей функциональной схемой. Определите, в какое слово перерабатывает машина каждое из следующих слов, исходя из стандартного начального состояния: а) 111*11; б) 11*11; в) 1111*1; г) 11111*111; д) 11111*1111. Постарайтесь выявить общую закономерность в работе машины. 11. На ленте записаны два числа в двоичной системе счисления, разделенные звездочкой: Определите, какую операцию проделает с ними машина Тьюринга, начиная из стандартного начального положения, если программа машины задается таблицей: q1 q2 q3 q4 q5 q6 �Содержание a0 q0 a0 С q11Л q5 a 0 П q6 a0 Л 1 q2 0 Л q21Л q4 0 Л q41Л q51П q6 0 Л 0 q2 0 Л q3 0 Л q4 0 Л q5 0 П q6 0 Л * q3 * Л q5 * П q3 * Л 12. Вопрос, аналогичный вопросу из предыдущей задачи, для ленты и для машины Тьюринга с программой: q11  q1 0 Л , q1 0  q1 0 Л , q21  q2 0 Л , q 2 0  q3 0 Л q 3 1  q 4 1Л , q1*  q2 * Л , q41  q1 0 Л , q1 a 0  q 0 a 0 С , . 13. Постройте такую машину Тьюринга, которая из n записанных подряд единиц оставляла бы на ленте ( n  2) единицы, также записанные подряд, если n  2 , и работала бы вечно, если n  0 или n 1 . ... 11 , n  1 . Постройте машину Тьюринга с внешним  14. Известно, что на ленте записано слово 11 n алфавитом A  {a0 ,1} , которая отыскивала бы левую единицу этого слова (т. е. приходила бы в состояние, при котором обозревалась бы ячейка с самой левой единицей данного слова, и в этом положении останавливалась), если в начальный момент головка машины обозревает одну из ячеек с буквой данного слова. 15. Сконструируйте машину Тьюринга с внешним алфавитом A  {a0 ,1} , которая каждое слово в алфавите A1  {1} перерабатывает в пустое слово, исходя из стандартного начального положения. 16. Сконструируйте машину Тьюринга с внешним алфавитом A  {a0 ,1} , которая каждое слово длиной n в алфавите A1  {1} перерабатывает в слово длиной n  1 в том же алфавите A1 . 17. Постройте машину Тьюринга для подсчета на ленте количества штрихов, которые располагаются �Содержание подряд и образуют входное слово, при этом требуется стереть все штрихи и записать на ленте их количество в десятичной системе. Кроме самой программы-таблицы опишите словами, что выполняется машиной в каждом состоянии. 18. Постройте машину Тьюринга, которая во входном слове все буквы «а» заменит на буквы «б». Кроме самой программы-таблицы опишите словами, что выполняется машиной в каждом состоянии. 19. Дано число в восьмеричной системе счисления. Разработайте машину Тьюринга, которая увеличивала бы заданное число на 1. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы опишите словами, что выполняется машиной в каждом состоянии. 20. Дано натуральное число n  1 . Разработайте машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было «100», то выходным словом должно быть «99», а не «099». Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы опишите словами, что выполняется машиной в каждом состоянии. 21. Даны два натуральных числа m и n , представленные в унарной системе счисления. Соответствующие наборы символов (последовательности единиц) разделены пустой клеткой. Автомат в состоянии q1 обозревает самый правый символ входной последовательности. Разработайте машину Тьюринга, которая на ленте оставит сумму чисел m и n . Кроме самой программы-таблицы опишите словами, что выполняется машиной в каждом состоянии. 22. Даны два натуральных числа m и n , представленные в унарной системе счисления. Соответствующие наборы символов (последовательности единиц) разделены пустой клеткой. Автомат в состоянии q1 обозревает самый правый символ входной последовательности. Разработайте машину Тьюринга, которая на ленте оставит разность чисел m и n . Известно, что m  n . Кроме самой программы-таблицы опишите словами, что выполняется машиной в каждом состоянии. 23. На ленте машины Тьюринга записаны два набора единиц. Они разделены *. Составьте функциональную схему машины так, чтобы она выбрала больший из этих наборов, а меньший стерла, исходя из стандартного начального положения. Звездочка должна быть сохранена, чтобы было видно, какой из массивов выбран. 24. На ленте машины Тьюринга находится десятичное число. Определите, делится ли это число на 5 без остатка. Если делится, то запишите справа от числа слово «да», иначе – «нет». Автомат обозревает некую цифру входного числа. Кроме самой программы-таблицы опишите словами, что выполняется машиной в каждом состоянии. �Содержание 25. Дан массив из открывающихся и закрывающихся скобок. Постройте машину Тьюринга, которая удаляла бы пары взаимных скобок, т. е. расположенных подряд «( )». Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы опишите словами, что выполняется машиной в каждом состоянии. 26. Дана строка из букв a и b . Разработайте машину Тьюринга, которая переместит все буквы a в левую, а буквы b в правую часть строки. Каретка находится над крайним левым символом строки. Кроме самой программы-таблицы опишите словами, что выполняется машиной в каждом состоянии. 27. На ленте машины Тьюринга находится число, записанное в десятичной системе счисления. Умножьте это число на 2. Автомат в состоянии q1 обозревает крайнюю левую цифру числа. Кроме самой программы-таблицы опишите словами, что выполняется машиной в каждом состоянии. 28. Алфавит {0, 1, 2, 3}. Стереть четвертую слева цифру «3». Если это удастся (т. е. если четвертая слева тройка существует), записать в этой клетке символ, который стоит непосредственно после нее. Если нет, то стереть всё слово. 29. Алфавит {0, 1, 2}. Определить, есть ли в слове два подряд вхождения символа «2». Если да, то каждую пару символов «2» заменить на пару символов «1». Если нет, то стереть все слово и записать вместо него символ «*». 30. Алфавит {0, 1}. Стереть вторую справа цифру «0». Если это удастся, то после выполнения данной операции записать в этой клетке символ, который стоит непосредственно перед ней. Если нет, стереть слово. 31. Алфавит {0, 1, 2}. Определить, есть ли в слове последовательность «012». Если есть одна или больше, то все такие последовательности заменить на последовательность «***». Если нет ни одной искомой последовательности, то приписать к концу слова символ «–». 32. Постройте следующие машины Тьюринга: а) A (перенос нуля): q1 001 x 0  q 0 01 x 00 . x x б) Б  (сдвиг вправо): q1 a i 1 0  a i 1 q 0 0 . x x в) Б  (сдвиг влево): 01 q1a i  q 0 01 a i . x y y x г) B (транспозиция): q1 01 01 0  q 0 01 01 0 . �Содержание x x x x д) K (копирование): q1 01 00 0  q 0 01 01 0 . x x е) Л (стирающая машина): q1 01 0  q 0 00 0 . x 1 x ж) R (удаление 1): q1 01 0  q 0 01 00 . x x 1 з) S (добавление 1): q1 01 0  q 0 01 0 . 33. Докажите, что следующие функции вычислимы по Тьюрингу, для чего постройте машины Тьюринга, вычисляющие их: а) f ( x , y )  x  y ; 0, если x  0, б) f ( x)  x  1    x  1, если x  0; 0, если x  0, в) sg ( x )   1, если x  0; 0, если x  0, г) sg ( x )   1, если x  0; 0, если x  y , д) f ( x, y )  x  y   1, если x  y; е) f ( x , y )  x  y ; x ж) f ( x )  ; 2 x з) f ( x )    2 целая часть числа x ; 2 и) f ( x, y )  НОД ( x, y ) ; к) f ( x )  2 x  1 ; 1 л) f ( x )    ; x м) f ( x )  1 ; x2 1, если x делится на 3, н) f ( x )   0, если x не делится на 3. �Содержание 34. Машина Тьюринга имеет следующую функциональную схему: q1 q2 q3 0 q21Л q31П q0 0С 1 q11П q21Л q01С Найдите формульное выражение функции f (x ) , вычисляемой машиной. Изначально машина находится в стандартном начальном положении. 35. По программе машины Тьюринга напишите вычисляемой этой машиной: формульное выражение q1 q2 q3 q4 q5 q6 0 q2 0 П q1 0 Л q4 0 Л q4 0 Л q6 0 П q0 0С 1 q11П q3 0 П q3 0 П q51Л q51Л q0 1С функции f ( x, y ) , Изначально машина находится в состоянии q1 и обозревает самый левый символ входного слова. 36. Какую функцию f (x ) вычисляет машина Тьюринга со следующей программой: q1 0  q2 0 П , q11  q01C , q1 0  q31C , q21  q21П , q3 0  q0 0C , q31  q31Л ? 37. Пусть машина Тьюринга имеет следующую программу: q1 0  q0 0С . Какие функции f (x ) , f ( x1 , x2 ) , …, f ( x1 ,  , xn ) вычисляет эта машина? 38. Постройте машины Тьюринга для правильного вычисления функций: а) О ( х )  0 ; б) f ( x )  x  1 ; в) f ( x )  sg ( x ) ; г) f ( x )  sg ( x ) ; д) f ( x )  x  y ; е) f ( x )  x  y . 39. Обоснуйте, что машина Тьюринга является конечным автоматом. (Конечным автоматом называется шестерка объектов: A = {S,X,Y,s0,d,v}, где �Содержание S – конечное непустое множество (состояний); X – конечное непустое множество входных сигналов (входной алфавит); Y – конечное непустое множество выходных сигналов (выходной алфавит); s0 Є S – начальное состояние; d: S×X → S – функция переходов; v: S×X → Y – функция выходов.) 40. Покажите на конкретном примере, как машину Тьюринга (по аналогии с конечным автоматом) можно задать в виде ориентированного графа. �Содержание Глава 4. Машина Поста § 1. Назначение и устройство машины Поста § 2. Команды и порядок работы машины Поста § 4. Тезис Поста Вопросы к главе 4 Задания к главе 4 �Содержание 4.1. Назначение и устройство машины Поста Почти одновременно с Тьюрингом американский математик Эмиль Пост в 1937 году предложил иную абстрактную машину (алгоритмическую модель), характеризующуюся еще большей простотой, чем машина Тьюринга. Это строгое математическое построение было также предложено в качестве уточнения понятия алгоритма. Идеи Эмиля Поста оказались настолько фундаментальны, что к ним вернулись через 30 лет. В 1967 г. профессор В.А. Успенский пересказывает их с новых позиций, именно он вводит термин машины Поста, трактуя ее как абстрактную машину, которая работает по алгоритмам, разработанным человеком. Машина Поста, как и машина Тьюринга, представляет собой универсального исполнителя, являющегося полностью детерминированным, позволяющему «вводить» начальные данные и после выполнения программ «читать» результат. Машина Поста является менее популярной, чем машина Тьюринга, хотя она устроена проще в том отношении, что ее элементарные действия проще, чем элементарные действия машины Тьюринга, и способы записи менее разнообразны. Именно по этим причинам запись и переработка информации на машине Поста требует, вообще говоря, большего объема «памяти» и большего числа шагов, чем на машине Тьюринга. В основе создания машины Поста лежат следующие идеи: − вся информация, которая должна быть обработана по существу, должна быть обработана по форме, т. е. с помощью двоичного алфавита; − вся информация должна обрабатываться побуквенно. В соответствии с указанными идеями машина Поста была разработана как абстрактная конструкция, представляющая собой бесконечную ленту, разделенные на одинаковые клетки, каждая из которых может быть либо пустой, либо заполненной меткой «V» (рис. 8). Подчеркнем, что это ограничение не влияет на универсальность машины Поста, так как любой алфавит может быть закодирован двумя знаками. Кроме ленты в машине Поста имеется каретка (головка чтения/записи), которая: − умеет перемещаться вдоль ленты на одну клетку вправо или влево; − умеет наносить в обозреваемую клетку метку, если этой метки там ранее не было; − умеет стирать метку, если она была в обозреваемой ячейке; − умеет проверять наличие в клетке метки. Рис. 8 Информация о заполненных метками клетках ленты характеризует состояние ленты, которое может меняться в процессе работы машины. В каждый момент времени каретка находится над одной из клеток ленты (обозревает ее). Информация о местоположении каретки вместе с состоянием ленты �Содержание характеризует состояние машины Поста. Замечание Состояние машины Поста отличается от состояния машины Тьюринга: − в машине Тьюринга состояние определяет, что следует записать в обозреваемую ячейку для каждого определенного символа, задает характер движения каретки и, наконец, указывает новое состояние машины; − в машине Поста состояние описывает местонахождение каретки и состояние ленты. �Содержание 4.2. Команды и порядок работы машины Поста Все команды машины Поста имеют следующую структуру: nKm , где n номер текущей команды; K действие, выполняемое кареткой; m номер следующей команды, подлежащей выполнению. Существует всего шесть действий, выполняемых кареткой машины Поста, а поэтому существует всего шесть команд машины Поста (таблица 6). �Содержание Таблица 6 Система команд машины Поста �Содержание �Содержание Подчеркнем, что ситуации, в которых каретка должна наносить метку там, где она уже есть, или, наоборот, стирать метку там, где ее нет, являются аварийными (недопустимыми). Программой для машины Поста будем называть непустой список команд, такой, что: 1) на n -ом месте команда с номером n ; 2) номер m каждой команды совпадает с номером какой-либо команды списка. Работа машины Поста состоит в том, что каретка передвигается вдоль ленты и печатает или стирает метки. Чтобы машина Поста работала, надо задать некоторую программу и некоторое состояние машины (т. е. нужно как-то расставить метки по ячейкам ленты, в частности, можно все секции оставить пустыми и поставить каретку против одной из ячеек). �Содержание Работа машины на основании заданной программы происходит следующим образом: машина приступает к выполнению первой команды программы; эта команда выполняется за один шаг, после чего машина приступает к выполнению той команды, номер которой равен отсылке первой команды. Эта команда также выполняется за один шаг, после чего начинается выполнение той команды, номер команды которой равен отсылке предыдущей команды и т. д. Вообще каждая команда выполняется за один шаг, а переход от выполнения одной команды к выполнению другой происходит по следующему правилу: пусть на k -ом шаге выполнялась команда с номером n , тогда: 1) если эта команда имеет единственную отсылку m , то на ( k  1) -ом шаге выполняется команда с номером m ; 2) если эта команда имеет две отсылки m1 и m2 , то на (k  1) -ом шаге выполняется одна из двух команд с номером m1 или с номером m2 ; 3) если же выполняющаяся на k -ом шаге команда вовсе не имеет отсылки, то на (k  1) -ом шаге и на всех последующих шагах не выполняется никакая команда – машина останавливается. Возможны следующие случаи останова машины Поста: 1) в ходе выполнения программы машина дойдет до выполнения команды остановки; программа в этом случае считается выполненной, машина останавливается происходит результативная остановка; 2) в ходе выполнения программы машина дойдет до выполнения невыполнимой команды; выполнение программы прекращается, машина останавливается происходит безрезультативная остановка. Кроме того, возможна программа, при выполнении которой машина не останавливается никогда; в этом, как и в предыдущем случае, мы имеем дело с некорректным алгоритмом (программой). �Содержание 4.3. Примеры типичных программ машины Поста Пример 1 На ленте проставлена отметка в одной-единственной ячейке. Каретка стоит на некотором расстоянии слева от этой ячейки. Необходимо подвести каретку к ячейке, стереть отметку и остановить каретку слева от нее. Решение Исходное состояние машины следующее: Сначала попробуем описать алгоритм обычным языком. Поскольку нам известно, что каретка стоит напротив пустой ячейки, но неизвестно, сколько шагов нужно совершить до непустой ячейки, мы можем сразу сделать шаг вправо, проверить, заполнена ли ячейка, после чего повторять эти действия до тех пор, пока не наткнемся на заполненную ячейку. Как только мы ее найдем, мы выполним операцию стирания, после чего нужно будет лишь сместить каретку влево и остановить выполнение программы. Программа для машины Поста: 1 2 2 ?1,3 3X 4 45 5! Проиллюстрируем состояние машины Поста на каждом шаге ее работы: �Содержание Замечание Команда передачи (условного перехода) n ? m1, m 2 является одним из основных средств организации циклических процессов, например, для нахождения первой метки справа (или слева) от каретки, расположенной над пустой ячейкой; нахождение слева (или справа) от каретки пустой клетки, если она расположена над меткой и т. д. �Содержание Остановимся на представлении чисел на ленте машины Поста и выполнении операций над ними. Число k представляется на ленте машины Поста идущими подряд k метками. Между двумя числами делается интервал, как минимум, из одной пустой ячейки на ленте. Например, запись чисел 3 и 4 на ленте машины Поста будет выглядеть так: Пример 2 Составим программу для прибавления к произвольному числу единицы. Предположим, что на ленте записано только одно число и головка находится над одной из клеток, в которой находится метка, принадлежащая этому числу: Решение Для решения задачи можно перенести каретку влево (или вправо) до первой пустой клетки, а затем нанести метку. Программа, добавляющая к числу метку слева, имеет вид: 1 2 2 ? 3,1 3V 4 4! Программа, добавляющая к числу метку справа, имеет вид: 1 2 2 ? 3,1 3V 4 4! Пример 3 Приведем программу для сложения двух натуральных чисел a и b . Между числами – несколько неотмеченных клеток. Каретка находится где-то над первым числом: �Содержание Решение Реализуем следующий алгоритм сложения двух чисел: будем двигаться к первой левой метки первого числа, затем первую левую метку сотрем, и будем двигаться к крайней правой метки первого числа, затем припишем недостающую у первого числа метку справа (теперь первое число будет придвинуто ко второму на одну ячейку); так будем действовать до тех пор, пока числа a и b не сольются на ленте машины Поста. Приведем соответствующую программу машины Поста с кратким комментарием сущности каждой используемой в ней команды: Коман да Комментарий к команде 1 2 Поиск начала первого числа: сдвигаемся влево 2 ? 3,1 до тех пор, пока не встретим неотмеченную ячейку. 34 Сдвигаемся вправо, на первую метку первого числа и 4X 5 удаляем ее. 56 Ищем конец первого числа: сдвигаемся вправо 6 ? 7,5 пока каретка не встанет на неотмеченную ячейку и 7V 8 ставим метку. 89 Проверяем, заполнился ли промежуток между числами: 9 ?1,10 если не заполнился – переход на первую команду, иначе – 10! конец. �Содержание 4.4. Тезис Поста Тезис Поста Всякий алгоритм представим в форме машины Поста. Этот тезис одновременно является формальным определением алгоритма: алгоритм (по Посту) программа для машины Поста, приводящая к решению поставленной задачи. Тезис Поста является гипотезой. Его невозможно строго доказать (так же, как и тезис Тьюринга), потому что в нем фигурирует, с одной стороны, интуитивное понятие алгоритма, а с другой точное понятие «машина Поста». Обоснование тезиса Поста сегодня происходит не путем строго математического доказательства, а путем эксперимента действительно, всякий раз, когда указывается какой-либо алгоритм, его можно перевести в форму программы машины Поста, приводящей к тому же результату. Замечание Машину Поста, как и машину Тьюринга, можно рассматривать как упрощенную модель ЭВМ. В самом деле, как ЭВМ, так и машина Поста имеют: – неделимые носители информации (клетки незаполненными; – ограниченный набор элементарных действий такт (шаг). биты), которые могут быть заполненными или команд, каждая из которых выполняется за один Обе машины работают на основе программы. Однако в машине Поста информация располагается линейно и читается подряд, а в ЭВМ можно читать информацию по адресу; набор команд ЭВМ значительно шире и выразительнее, чем команды машины Поста и т. д. �Содержание Вопросы к главе 4 1. Кем и когда была разработана машина Поста? 2. Сформулируйте идеи, которые легли в основу создания машины Поста. 3. Опишите основные составные части машины Поста. 4. Что называют состоянием машины Поста? 5. Чем состояние машины Поста отличается от состояния машины Тьюринга? 6. Сколько существует основных типов команд машины Поста? Раскройте их суть. 7. При выполнении каких команд машины Поста может произойти аварийная ситуация (остановка)? Как этого избежать? 8. Что представляет собой программа машины Поста? 9. Опишите, как происходит работа машины Поста на основе программы. 10. Какие случаи останова машины Поста возможны? Какие из них являются некорректными? 11. Сформулируйте тезис Поста. 12. Раскройте роль машины Поста в теории алгоритмов �Содержание Задания к главе 4 1. Начальное состояние: лента машины Поста пуста. Что будет находиться на ленте в результате работы следующей программы? 1V 2 23 3 1 2. Известно, что на ленте машины Поста находится метка. Напишите программу, которая находит ее. 3. На ленте имеется массив из n отмеченных ячеек. Каретка обозревает крайнюю левую отметку. Справа от данного массива на расстоянии в m ячеек находится еще одна отметка. Составьте для машины Поста программу, придвигающую данный массив к данной ячейке. 4. На ленте расположены два массива разной длины. Они разделены одной пустой ячейкой. Каретка обозревает крайний элемент одного из них. Составьте программу для машины Поста, сравнивающую длины массивов и стирающую больший из них. Отдельно продумайте случай, когда длины массивов равны. 5. Дан массив из n меток (т. е. идущих подряд отмеченных ячеек). Каретка обозревает крайнюю левую ячейку. Составьте для машины Поста программу, расставляющую эти метки на ленте так, чтобы между каждой парой было по одной пустой ячейке. 6. На ленте машины Поста расположен массив в n ячейках. Необходимо справа от данного массива через одну пустую ячейку разместить массив, вдвое больший (он должен состоять из 2n меток). При этом исходный массив может быть стерт. 7. На ленте машины Поста расположен массив из n меток (метки расположены через пробел). Нужно сжать массив так, чтобы все n меток занимали n расположенных подряд ячеек. 8. На ленте машины Поста расположено n массивов меток, отделенных друг от друга свободной ячейкой. Каретка находится над крайней левой меткой первого (левого) массива. Определите количество массивов. 9. На ленте машины Поста расположен массив из n меток. Составьте программу, действуя по которой, машина выяснит, делится ли число n на 3. Если да, то после массива через одну пустую секцию поставьте метку. �Содержание 10.На ленте задан массив. Вычислите остаток от деления длины заданного массива на 3. Каретка располагается над первой ячейкой массива. 11.На ленте машины Поста расположен массив из 2n  1 меток. Составьте программу нахождения средней метки массива и стирания ее. 12.На ленте машины Поста расположен массив из 2n отмеченных секций. Составьте программу, по которой машина Поста раздвинет на расстояние в 1 секцию две половины данного массива. 13.На ленте машины Поста находятся два массива из m и n меток. Составьте программу выяснения, одинаковы ли массивы по длине. 14.На ленте задан массив меток. Нужно увеличить длину массива в 2 раза. Каретка находится либо слева от массива, либо над одной из ячеек самого массива. 15.На ленте заданы два массива – m и n, m > n. Вычислить разность этих массивов. Каретка располагается над левой ячейкой правого массива. 16.На ленте имеется некоторое множество меток (общее количество меток не менее 1). Между метками множества могут быть пропуски, длина которых составляет одну ячейку. Заполнить все пропуски метками. 17.Дан массив меток. Каретка располагается где-то над массивом, но не над крайними метками. Стереть все метки, кроме крайних, и поставить каретку в исходное положение. 18.Дано N массивов меток. Массивы разделены тремя пустыми ячейками. Количество меток в массиве не меньше двух. Если количество меток в массиве кратно трем, то стереть метки в этом массиве через одну, в противном случае стереть весь массив. Каретка находится над крайней левой меткой первого массива. �Содержание Глава 5. Машины произвольного доступа В данной главе рассмотрим такую алгоритмическую модель (уточнение понятия алгоритма), как машины произвольного доступа. Они были предложены достаточно недавно (в 1970-х годах) с целью моделирования реальных вычислительных машин и анализа сложности вычислений. § 1. Устройство и порядок работы машины произвольного доступа § 2. Вычисление функций на машине произвольного доступа § 3. Композиция программ машин произвольного доступа Вопросы к главе 5 Задания к главе 5 �Содержание 5.1. Устройство и порядок работы машины произвольного доступа Машина произвольного доступа (МПД) состоит из бесконечного числа регистров R1, R2, R3…, в каждом из которых может быть записано натуральное число или нуль. Определение Пусть rn – число, записанное в регистре Rn, n Є N. Состоянием машины произвольного доступа или конфигурацией назовем последовательность чисел (r1, r2, r3,…). Функционирование машины произвольного доступа заключается в изменении конфигураций путем выполнения команд в порядке их написания. Машина произвольного доступа имеет следующие типы команд: 1. Команды обнуления. Для всякого n Є N имеется команда Z(n). Действие команды Z(n) заключается в замене содержимого регистра Rn на 0. Содержимое других регистров не меняется. Обозначение действия Z(n)-rn: 0. 2. Команды прибавления единицы. Для всякого n Є N имеется команда S(n). Действие команды S(n) заключается в увеличении содержимого регистра Rn на 1. Содержимое других регистров не меняется. Обозначение действия S(n)-rn: rn+1. 3. Команды переадресации. Для всех m,n Є N имеется команда T(m,n). Действие команды T(m,n) заключается в замене содержимого регистра Rn числом rm, хранящемся в регистре Rт. Содержимое других регистров не меняется (включая и регистр Rт). Обозначение действия: T(m,n)-rn: rm или rm → Rn. 4. Команды условного перехода. Для всяких m,n,q Є N имеется команда J(m,n,q). Действие этой команды заключается в следующем: «Сравнивается содержимое регистров Rm и Rn, затем: − если rn = rm то МПД переходит к выполнению команды с номером q в списке команд; − если rn ≠ rm то МПД переходит к выполнению следующей команды в списке команд». Конечная, упорядоченная последовательность команд данных типов составляет программу МПД. Рассмотрим порядок работы машины произвольного доступа. Пусть зафиксирована начальная конфигурация K0(a1 ,a2,…) чисел и программа P = I1I2…Is. Тогда однозначно определена последовательность конфигураций: K0 , K1, K2, …, Kt , Kt+1, … , (1) где K1 есть конфигурация, полученная из K0 применением команды I1. Пусть на некотором шаге выполнена команда It и получена конфигурация Kt. Тогда: �Содержание если It не есть команда условного перехода, следующая конфигурация Kt+1 есть конфигурация, полученная из Kt применением команды It+1; если It есть команда условного перехода, т. е. It = J(m,n,q), то Kt+1 получается из Kt применением команды Iq, если rn = rm в конфигурации Kt и команды It+1, если rn ≠ rm. Последовательность (1) будет обозначаться также P(a1,a2,…) или P(K0) и называться вычислением. Вычисление (работа машины) останавливается в следующих случаях: 1) выполнена последняя команда, т. е. t = s и It не есть команда условного перехода; 2) если It = J(m,n,q), rn = rm в конфигурации Kt и q > s; 3) если It = J(m,n,q), rn ≠ rm в конфигурации Kt и t = s. Если вычисление остановилось, то последовательность (r1,r2,…) содержимого регистров R1,R2,… называется заключительной конфигурацией. Если последовательность (1) конечна, то говорят, что МПД применима к начальной конфигурации K0(a1 ,a2,…) и пишут P(a1 ,a2,…)↓ или P(K0)↓. В противном случае говорят, что МПД неприменима к начальной конфигурации K0(a1 ,a2,…) и пишут P(a1 ,a2,…)↑ или P(K0)↑. Замечание В дальнейшем будем рассматривать только такие начальные конфигурации, в которых имеется конечное число элементов, отличных от нуля. Будем писать (a1 ,a2,…,an) вместо (a1 ,a2,…,an,0,…) для таких конфигураций. (Ясно, что для любого t конфигурация Kt будет содержать конечное число отличных от нуля элементов, если этим свойством обладает конфигурация K0 .) Пример Разработаем программу МПД, которая к каждому входному натуральному числу х прибавляет 2. Решение Идея разработки данной программы очевидна: к входному числу х, содержащемуся в некотором регистре, нужно дважды применить команду прибавления единицы S(n). Пусть входное число х записано в регистр R1. Тогда искомая программа будет иметь следующий вид: 1) S(1), 2) S(1). Проиллюстрируем работу машины на конкретном примере. Пусть х = 37, т. е. в регистр R1 записано число 37 (таблица 7). �Содержание Таблица 7 Вычисление МПД искомого числа х+2 Номер команды Команда Содержимое регистра R1 37 1 S(1) 38 2 S(1) 39 Остановка работы машины будет происходить после выполнения последней (т. е. второй) команды, которая не является командой условного перехода. �Содержание 5.2. Вычисление функций на машине произвольного доступа Условимся, что будем понимать под вычислением функций на МПД. Определение Пусть P = I1I2…Is – фиксированная программа. Пусть a1 ,a2,…,an,b Є N0. Будем говорить, что вычисление дает результат b, если P(a1 ,a2,…)↓ и в заключительной конфигурации r1 = b. Обозначение: P(a1 ,a2,…)↓b. Будем говорить, что программа Р вычисляет функцию f, если  a1 ,a2,…,an,b Є N0 выполнимо P(a1 ,a2,…)↓b (f определена на (a1 ,a2,…,an) и f(a1 ,a2,…,an) = b). Назовем функцию f вычислимой на МПД, если существует программа P, которая вычисляет f. Замечание 1. В определении рассматриваются частичные функции f: N 0n  N 0 . ( N 0  N  {0}) . 2. Любая программа Р для любого n ≥ 1 на начальных конфигурациях К0(a1 ,a2,…,an,0,…) определяет nn местную частичную функцию f p (x1,…,xn) такую, что  a1 ,…,an Є N0: b, если P ( a1 , a2 ,...)  и P ( a1 , a2 ,...)  b, f pn ( x1 ,..., xn )   неопределе на , если P ( a1 , a2 ,...)  . 3. Ясно, что разные программы могут вычислять одну и ту же функцию. Пример 1 Программа МПД, разработанная в примере § 1: 1) S(1), 2) S(1), вычисляет функцию f(x) = x+2, где х Є N. Пример 2 Разработаем программу МПД, которая вычисляет функцию f(x,y) = x+y. Решение Условимся, что начальной конфигурацией МПД будет выступать последовательность чисел (х,у,0,0,…), т. е. в регистре R1 будет записано число х, в регистре R2 будет записано число у, а в остальных регистрах R3, R4, … будет содержаться 0. На данном этапе ясно, что в программе будут использоваться как минимум два регистра R1 и R2; �Содержание понадобятся ли нам еще регистры и какое количество – будет выяснено в ходе разработки программы. Для того чтобы составить искомую программу МПД, нужно догадаться, как используя ее команды (команду обнуления, команду прибавления единицы, команду переадресации, команду условного перехода), можно найти сумму двух чисел х и у. Оказывается, сумму двух произвольных чисел можно найти, используя команду прибавления единицы. Действительно, для того чтобы найти сумму двух чисел х и у, нужно к числу х прибавить у раз единицу. Воспользуемся этим положением для составления искомой программы. Кроме того, опишем назначение используемых регистров: R1 – предназначено для записи числа х, кроме того именно в этом регистре будет «накапливаться» искомая сумма; R2 – предназначено для записи числа у; R3 – предназначено для подсчета количества единиц, прибавленных к числу х. Остановка программы должна происходить, когда в регистре R1 будет записана искомая сумма х+у, т. е. когда к числу х будет прибавлено у единиц, а содержимое регистра R3 будет равняться содержимому регистра R2. Составим словесный алгоритм нахождения искомой суммы: 1) сравниваем содержимое регистров R3 с содержимым регистра R2: если равно, то остановка МПД, если неравно, то переход к п. 2; 2) прибавляем к содержимому регистра R1 единицу; 3) прибавляем к содержимому регистра R3 единицу; 4) возвращаемся к п. 1. Соответствующая программа МПД может быть, например, следующей: 1) J(3,2,5), 2) S(1), 3) S(3), 4) J(1,1,1). Проиллюстрируем работу МПД на конкретном примере. Пусть х = 5, у = 3, т. е. в регистре R1 записано число 5, а в регистре R2 – число 3 (таблица 8). �Содержание Таблица 8 Вычисление МПД искомого числа х+у Номер команды Содержимое регистров Команда R1 R2 R3 5 3 0 1 J(3,2,5) 5 3 0 2 S(1) 6 3 0 3 S(3) 6 3 1 4 J(1,1,1) 6 3 1 1 J(3,2,5) 6 3 1 2 S(1) 7 3 1 3 S(3) 7 3 2 4 J(1,1,1) 7 3 2 1 J(3,2,5) 7 3 2 2 S(1) 8 3 2 3 S(3) 8 3 3 4 J(1,1,1) 8 3 3 1 J(3,2,5) 8 3 3 5 – Из таблицы видно, что как только в регистре R1 будет «накоплена» искомая сумма х+у, машина перейдет к выполнению команды 5. А так как команды с таким номером в программе МПД нет, то машина остановится. �Содержание 5.3. Композиция программ машин произвольного доступа Поскольку доказательства вычислимости конкретных функций на МПД связаны с предъявлением конкретных программ, их вычисляющих, то следует ввести некоторые соглашения о составлении и записи программ на МПД. Аналогично композиции машин Тьюринга можно ввести композицию программ МПД. Пусть программа P = I1I2…Is. Будем говорить, что программа Р имеет стандартный вид, если для всякой команды условного перехода J(m,n,q) выполнимо q ≤ s+1. Две программы Р и Р' назовем эквивалентными, если они определяют одни и те же n-местные n n функции, т. е. f P  f P ' для всех n > 0. Теорема Для всякой программы Р существует эквивалентная ей программа стандартного вида Р'. Доказательство Пусть P = I1I2…Is. Тогда определим P' = I'1I'2…I's, где  k Є {1,…,s}:  I k , если I k не есть команда условног о перехода ,  I   I k , если I k  J (m, n, q ) и q  s  1,  J (m, n, s  1), если I  J (m, n, q ) и q  s  1. k  ' k Ясно, что Р' удовлетворяет нужным требованиям, что и требовалось доказать. Пусть теперь даны две программы P и Q стандартного вида. Образуем программу PQ = I1I2…IsIs+1… Is+t, где P = I1I2…Is, Q = Is+1Is+2…Is+t с учетом нумерации, т. е. команды J(m,n,q) заменены на J(m,n,s+q). Тогда результат действия программы PQ совпадает с результатом вычисления по программе P, к которому применена программа Q. Заметим, что для всякой программы P существует минимальное натуральное число r(P), такое, что для всех m,n Є N, входящих в команды из P, т. е. Z(n), S(n), T(m,n), J(m,n,q) выполнено m,n < r(P). Это число r(P) называют шириной (или рангом) программы P. Смысл ранга r(P) состоит в том, что регистры Rt, где t > r(p), в ходе вычисления по программе P не будут менять свое содержание и не будут влиять на содержимое регистров R1, R2, …, Rr, поэтому их можно использовать для других вычислений. Заметим также, что можно организовать вычисление, используя программу P, в случае, когда входы программы находятся в регистрах Rl1, Rl2, …, Rln, а результат заносится в регистр Rl. Пусть программа P вычисляет функцию f в стандартном понимании вычислимости. Тогда следующая программа P[l1,… ,ln → l] будет вычислять f(xl1,xl2,…,xln) и результат запишет в Rl: �Содержание T(l1,1) … T(ln,n) Z(n+1) … Z(r(P)) P T(1,l) Далее, будем считать, что регистры Rl1, Rl2, …, Rln отличны от R1, R2, …, Rn. Пример Покажем, что следующая программа P вычисляет функцию f(x,y) = xy: 1) J(2,3,6), 2) S(3), 3) H[1,4 → 5], где H – программа, вычисляющая функцию f(x,y) = x+y (см. пример 2 из 5.2) 4) T(5,4), 5) J(1,1,1), 6) T(5,1). Здесь начальной конфигурацией МПД выступает последовательность чисел (х,у,0,0,…). Решение Прежде всего, отметим следующее: «рабочими» регистрами в данной программе машины являются только регистры R1,R2,R3,R4,R5; запись H[1,4 → 5] означает, что будет вычисляться сумма чисел, записанных в регистрах R1 и R4, а найденная сумма будет помещаться в регистр R5. Для того чтобы понять принцип действия программы МПД, рассмотрим ее работу на конкретном примере. Пусть х = 7, у = 3, т. е. в регистре R1 записано число 7, а в регистре R2 – число 3 (таблица 9). �Содержание Таблица 9 Вычисление МПД искомого числа ху Номер команды Содержимое регистров Команда R1 R2 R3 R4 R5 7 3 0 0 0 1 J(2,3,6) 7 3 0 0 0 2 S(3) 7 3 1 0 0 3 H[1,4 → 5] 7 3 1 0 7 4 T(5,4) 7 3 1 7 7 5 J(1,1,1) 7 3 1 7 7 1 J(2,3,6) 7 3 1 7 7 2 S(3) 7 3 2 7 7 3 H[1,4 → 5] 7 3 2 7 14 4 T(5,4) 7 3 2 14 14 5 J(1,1,1) 7 3 2 14 14 1 J(2,3,6) 7 3 2 14 14 2 S(3) 7 3 3 14 14 3 H[1,4 → 5] 7 3 3 14 21 4 T(5,4) 7 3 3 21 21 5 J(1,1,1) 7 3 3 21 21 1 J(2,3,6) 7 3 3 21 21 6 T(5,1) 21 3 3 21 21 Из таблицы становится понятен принцип работы данной программы МПД: произведение двух чисел х и у находится через операцию суммирования, а именно число х суммируется у раз. Например, в случае, когда х=7, у=3, имеем: 7·3=7+7+7=14+7=21. Опишем теперь назначение используемых в программе регистров: R1 – предназначено для записи числа х, кроме того именно в этот регистр будет помещено искомое произведение ху; �Содержание R2 – предназначено для записи числа у; R3 – предназначено для записи количества суммируемых чисел х; R4 – предназначено для записи очередного слагаемого для следующего суммирования с числом х; R5 – предназначено для записи очередного ответа суммирования. Остановка программы происходит после выполнения последней (шестой) команды, которая не является командой условного перехода. Замечание Как следует из вышеизложенного, язык программ МПД содержит основные процедуры языков программирования и позволяет устраивать композицию (соединение) программ и использовать программы в качестве подпрограмм других программ. Это является основанием для предположения о том, что введенный класс вычислимых функций в точности отвечает классу алгоритмически вычислимых функций. Данное предположение называется тезисом Черча (для МПД). Как и тезисы Тьюринга, Поста, данный тезис доказать нельзя, однако принятие его позволяет истолковывать утверждения о несуществовании алгоритмов вообще. �Содержание Вопросы к главе 5 1. Когда была разработана МПД? 2. Раскройте назначение МПД. 3. Из каких элементов состоит МПД? 4. Что называется состоянием (конфигурацией) МПД? 5. Сколько типов команд МПД существует? Раскройте их суть. 6. Что называется программой МПД? Приведите пример программы МПД. 7. Опишите порядок работы МПД. 8. Когда происходит остановка работы МПД? 9. Что называется заключительной конфигурацией МПД? 10. Что означают слова «МПД применима к начальной конфигурации (a1 ,a2,…)», «МПД неприменима к начальной конфигурации (a1 ,a2,…)»? 11. Какая функция называется вычислимой на МПД? 12. Что означают слова «программа МПД имеет стандартный вид»? 13. Какие программы МПД называются эквивалентными? Приведите пример эквивалентных программ МПД. 14. Сформулируйте теорему о существовании для любой программы МПД эквивалентной ей программы. 15. Опишите суть композиции (соединения) двух программ МПД. 16. Что называется рангом программы МПД? 17. Что означает запись P[l1,…,ln → l], где Р – программа МПД? 18. Сформулируйте тезис Черча для МПД и раскройте его роль в теории алгоритмов. �Содержание Задания к главе 5 1. Разработайте программу МПД, которая вычисляет функцию f ( x )  x , где х – четное натуральное 2 число. 2. Запишите представленную программу МПД, вычисляющую функцию f(x,y) = xy, без использования в ней операции композиции машин МПД (т. е. без H[1,4 → 5]): 1) J(2,3,6), 2) S(3), 3) H[1,4 → 5], где H – программа, вычисляющая функцию f(x,y) = x+y (см. пример 2 из 5.2) 4) T(5,4), 5) J(1,1,1), 6) T(5,1). 3. Разработайте программу МПД, которая вычисляет следующие функции: а) f ( x )  x  5 ; б) f ( x )  3 x  5 ; 0, если x  1 ; в) f ( x )  x  1    x  y , если x  1 0, если x  0 г) sg ( x)   ; 1, если x  0 1, если x  0 д) sg ( x)   ; 0, если x  0 е) f ( x, y )  I 22 ( x, y )  1 ; ё) f ( x, y , z )  I 23 ( x, y , z )  1 ;  x, если x  y ж) f ( x, y )  max( x, y )   ;  y, если x  y з) f ( x )  x! 4. Покажите, что для каждой команды переадресации существует программа без команд переадресации, которая на всякой конфигурации МПД дает тот же результат, что и T(m, n). Это означает, что команды �Содержание переадресации на самом деле избыточны в нашем определении МПД. Тем не менее, представляется естественным и удобным иметь такие команды, облегчающие построение алгоритмов. �Содержание Глава 6. Нормальные алгоритмы Маркова В данной главе рассмотрим еще один подход к уточнению понятия алгоритма, предложенный российским математиком А.А. Марковым (1903–1979) в конце 1940-х начале 1950-х годов, – нормальные алгоритмы (в авторской транскрипции – алгорифмы). Данный подход связывает понятие алгоритма с переработкой слов в некотором алфавите в соответствии с определенными правилами. В качестве элементарного преобразования используется подстановка одного слова вместо другого. Множество таких подстановок определяют схему алгоритма. Правила, определяющие порядок применения подстановок, а также правила останова являются общими для всех нормальных алгоритмов. § 1. Марковские подстановки § 2. Нормальные алгоритмы и их применение к словам § 3. Нормально вычислимые функции § 4. Способы сочетания нормальных алгоритмов § 5. Принцип нормализации Маркова Вопросы к главе 6 Задания к главе 6 �Содержание 6.1. Марковские подстановки Алфавитом будем называть произвольный конечный набор различных символов. Составляющие его символы будем называть буквами, а любую конечную последовательность букв алфавита – словом в этом алфавите. Допускаются пустые слова (не содержащие ни одной буквы): пустое слово обозначают . Одно слово может быть составной частью другого слова. Тогда первое называется подсловом второго или вхождением во второе. Пример 1 A = {а,б,в,г,д,…,э,ю,я} – алфавит. α = параграф, β = граф, γ = ра – слова в алфавите А, β – это подслово α, γ – это подслово α и β, причем в α слово γ входит дважды. Определение Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (P,Q), состоящая в следующем: «В заданном слове R находят первое вхождение слова P (если таковое имеется) и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q». Полученное слово называется результатом применения марковской подстановки (P,Q) к слову R. Если же первого вхождения P в слово R нет (и, следовательно, вообще нет ни одного вхождения P в R), то считается, что марковская подстановка (P,Q) неприменима к слову R. Пример 2 Пусть (78,0) – марковская подстановка. Определим результат ее применения к словам 96747878, 100078, 78. Решение 96747878 => 9674078 => 967400, 100078 => 10000, 78 => 0. Замечание Частными случаями марковских подстановок являются подстановки с пустыми словами: ( ,Q), (P, ), ( , ). Их действие рассмотрим на конкретном примере. Пусть есть марковские подстановки ( ,д), (у, ), ( , ). Определим результат их применения к слову �Содержание «удочка»: ( ,д) удочка  дудочка, ( у,) удочка  дочка, (,) удочка  удочка. Для обозначения марковской подстановки (P,Q) используется запись P → Q. Она называется формулой подстановки (P,Q). Слово P называется левой частью, а Q – правой частью в формуле подстановки. Подстановки (P,Q), приводящие к остановке нормального алгоритма, называют заключительными. Для обозначения таких подстановок будем использовать запись P → .Q, называя ее формулой заключительной подстановки. (Здесь предполагается, что символы «→», «.» не входят в алфавит А входных слов.) �Содержание 6.2. Нормальные алгоритмы и их применение к словам Определение 1 Упорядоченный конечный список формул подстановок в алфавите А называется схемой нормального алгоритма и обозначается Sα. Схема нормального алгоритма имеет вид: P1 → (.)Q1 Sα: P2 → (.)Q2 …………. Pr → (.)Qr (Запись (.) означает, что она может стоять в этом месте, а может отсутствовать.) Данная схема Sα определяет алгоритм α, перерабатывающий слова в алфавите A. Этот алгоритм преобразования слов называют нормальным алгоритмом Маркова. Определение 2 Нормальным алгоритмом (Маркова) в алфавите А называется следующее правило построения последовательности Vi слов в алфавите А, исходя из данного слова V в этом алфавите: «В качестве начального слова V0 последовательности берется слово V. Пусть для некоторого i ≥ 0 слово Vi построено и процесс построения рассматриваемой последовательности еще не завершился. Если при этом в схеме нормального алгоритма нет формул, левые части которых входили бы в Vi, то Vi +1 полагают равным Vi, и процесс построения последовательности считается завершившимся. Если же в схеме имеются формулы с левыми частями, входящими в Vi, то в качестве Vi+1 берется результат марковской подстановки правой части первой из таких формул вместо первого вхождения ее левой части в слово Vi; процесс построения последовательности считается завершившимся, если на данном шаге была применена формула заключительной подстановки, и продолжающимся – в противном случае». Если процесс упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгоритм применим к слову V. Последний член W последовательности называется результатом применения нормального алгоритма к слову V. Последовательность Vi будем записывать так: V0 =>V1 =>V2 = … => Vm-1 =>Vm, где V0 = V, Vm = W. Замечание 1 Используют следующие обозначения: Sα:V (запись означает, что схема нормального алгоритма Sα неприменима к слову V); Sα:V => W (запись означает, что схема нормального алгоритма Sα применима к слову V и результатом ее �Содержание применения является слово W). Замечание 2 Мы определили понятие нормального алгоритма в алфавите А. Если же алгоритм задан в некотором расширении алфавита А, то говорят, что он есть нормальный алгоритм над А. (Алфавит В называется расширением алфавита А, если B A.) Пример 1 Пусть А = {a0,a1,a2.…,an} – алфавит. Рассмотрим схему нормального алгоритма: a0 → a1 → Sα: ………. an-1 → →. Определим результат применения данного нормального алгоритма к слову a1a2a1a3a0. Решение a1a2a1a3a0 => a1a2a1a3 => a2a1a3 = a2a3 => a3 => => . Данный нормальный алгоритм перерабатывает всякое слово (в алфавите А) в пустое слово. Пример 2 Пусть А = {a1,a2} – алфавит. Рассмотрим схему нормального алгоритма: Sα: a1 → . a2 → a2 Определим результат применения данного нормального алгоритма к словам, составленным из алфавита А. Решение Всякое слово P в алфавите А данный нормальный алгоритм переводит в слово Q, полученное из P путем вычеркивания первого вхождения буквы a1. Данный нормальный алгоритм неприменим к словам, не содержащим вхождений буквы a1. �Содержание Пример 3 Пусть А = {a1,a2,…,an} – алфавит. Рассмотрим алфавит B = A {γ,β}, γ,β  А, и соответственно схему нормального алгоритма Sα: 1. γγ → β 2. βa → aβ для любого a из алфавита А 3. βγ → β 4. β → . 5. γab → bγa для любых элементов a и b из алфавита А 6. →γ Покажем, что данный алгоритм осуществляет обращение слов в алфавите А. (Обращением слова P = ai0…aik назовем слово P* = aik…ai0.) Решение Пусть P = aj0…ajk произвольное слово в алфавите А. Тогда: 6 5 5 5 6 P => γP => aj1γaj0 …ajk => aj1aj2γaj0 aj3 …ajk => aj1aj2 … ajkγaj0 => 5 5 => γaj1aj2 … ajkγaj0 => … => aj2aj3 … ajkγaj1γaj0. Далее, повторяя этот процесс получим: 6 1 2 γajkγajk-1 … γaj1γaj0 => γγajkγajk-1 … γaj1γaj0 => βajkγajk-1 … γaj1γaj0 => 3 4 => ajkβγajk-1 … γaj1γaj0 => ajkβajk-1 … γaj1γaj0 => …=> ajkajk-1 … aj1aj0β => => .ajkajk-1 … aj1aj0, что и требовалось показать. �Содержание 6.3. Нормально вычислимые функции Определение Функция f, заданная на некотором множестве слов алфавита А, называется нормально вычислимой, если найдется такое расширение В данного алфавита (B A) и такой нормальный алгоритм в B, что каждое слово V (в алфавите А) из области определения функции f этот алгоритм перерабатывает в слово f(V). Пример 1 Пусть А = {a0,a1,a2.…,an} – алфавит, схема нормального алгоритма Sα: вычисляет функцию f(P) = P для любого P. →. . Данный алгоритм Пример 2 В алфавите A = {1} схема Sα: → .1 определяет нормальный алгоритм, который к каждому слову в алфавите А приписывает слева 1. Следовательно, алгоритм вычисляет функцию f(x) = х+1 (в унарной системе счисления). Пример 3 Составим нормальный алгоритм, вычисляющий значения положительное число) в десятичной системе счисления. функции f(x) = х+1 (х – целое Решение Определим алфавит А: А = {0,1,2,3,4,5,6,7,8,9,+}. Условимся обозначать входное слово следующим образом: «123+1». Ясно, что на выходе нормального алгоритма в этом случае должно получиться число «124». Рассмотрим два случая: 1) разряд единиц у числа х есть цифра из множества {0,1,2,3,4,5,6,7,8} (иными словами, в этом случае при прибавлении 1 к х не происходит переполнение разряда единиц у числа х); 2) разряд единиц у числа х есть цифра 9 (иными словами, в этом случае при прибавлении 1 к х происходит переполнение разряда единиц у числа х, а поэтому нужно обращаться к разряду десятков). Случай 1 Очевидно, что для нахождения суммы чисел х и 1, необходимо задать следующую схему нормального алгоритма Sα: 0+1 → 1 1+1 → 2 2+1 → 3 3+1 → 4 4+1 → 5 �Содержание 5+1 → 6 6+1 → 7 7+1 → 8 8+1 → 9 →. (данная подстановка обеспечивает остановку алгоритма). Случай 2 Очевидно, что если в разряде единиц у искомой суммы будет стоять цифра «9», то разряд десятков нужно увеличить на 1. Этого можно достичь, применив к входному слову следующую подстановку: 9+1 → +10 В результате, далее, нужно будет увеличить на 1 разряд десятков у исходного числа х. Этого можно добиться, применяя марковские подстановки, указанные в первом случае. Если при этом окажется, что увеличиваемый разряд числа х равен нулю (он отсутствует), то на его месте нужно написать 1 и остановить алгоритм. Это позволяет обеспечить следующая подстановка: +1 → .1 Рассмотренные выше случаи исходного числа х позволяют записать схему искомого нормального алгоритма Sα: 1. 0+1 → 1 5. 4+1 → 5 9. 8+1 → 9 2. 1+1 → 2 6. 5+1 → 6 10.9+1 → +10 3. 2+1 → 3 7. 6+1 → 7 11.+1 → .1 4. 3+1 → 4 8. 7+1 → 8 12. → . Проиллюстрируем работу приведенного нормального алгоритма на нескольких примерах. 1) 9+1 → +10 → .10 2) 37+1 → 38 → .38 3) 123+1 → 124 → .124 4) 999+1 → 99+10 → 9+100 → +1000 → .1000 5) 7899+1 → 789+10 → 78+100 → 7900 → .7900 Пример 4 Составим нормальный алгоритм, вычисляющий значения функции f(x) = 2х (х – целое положительное число) в десятичной системе счисления. Решение Определим алфавит А: А = {0,1,2,3,4,5,6,7,8,9,*}. Условимся обозначать входное слово следующим образом: «23*2». Ясно, что на выходе нормального �Содержание алгоритма в этом случае должно получиться число «46». Для получения искомого произведения (также как и предыдущем примере) будем двигаться справо налево, от разряда единиц в исходном числе х к более высоким разрядам, умножая при этом цифры разрядов на 2. При этом движении необходимо учесть два момента: 1) для продолжения умножения на 2 более высоких разрядов нужно смещать вправо символы «*2»; 2) в случае, когда происходит переполнение разряда при умножении необходимо запоминать «в уме» 1 (это происходит в следующих случаях: 5*2 = 10, 6*2 = 12, 7*2 = 14, 8*2 = 16, 9*2 = 18); эту «особенную» единицу мы будем фиксировать в ходе преобразований символом а. С учетом вышесказанного запишем марковские подстановки, которые необходимо применить к разряду единиц исходного числа х. 0*2 → *20 (правая часть этой подстановки означает, что в разряде единиц остается 0, а далее будет происходить умножение на 2 разряда десятков.) 1*2 → *22 (правая часть этой подстановки означает, что в разряде единиц остается 2, а далее будет происходить умножение на 2 разряда десятков.) 2*2 → *24 (правая часть этой подстановки означает, что в разряде единиц остается 4, а далее будет происходить умножение на 2 разряда десятков.) 3*2 → *26 4*2 → *28 5*2 → *2а0 (правая часть этой подстановки означает, что в разряде единиц остается 0, далее символ а означает, что была запомнена 1, которую нужно будет учесть при дальнейшем умножении на 2 разряда десятков.) 6*2 → *2а2 (правая часть этой подстановки означает, что в разряде единиц остается 2, далее символ а означает, что была запомнена 1, которую нужно будет учесть при дальнейшем умножении на 2 разряда десятков.) 7*2 → *2а4 (правая часть этой подстановки означает, что в разряде единиц остается 4, далее символ, а означает, что была запомнена 1, которую нужно будет учесть при дальнейшем умножении на 2 разряда десятков.) 8*2 → *2а6 9*2 → *2а8 Далее, запишем подстановки, которые необходимо применить к разряду десятков исходного числа х. 0*2а → *21 (здесь к результату умножения 0 на 2, т. е. к 0, была прибавлена запомненная ранее 1.) 1*2а → *23 (здесь к результату умножения 1 на 2, т. е. к 2, была прибавлена запомненная ранее 1.) 2*2а → *25 (здесь к результату умножения 2 на 2, т. е. к 4, была прибавлена запомненная ранее 1.) 3*2а → *27 4*2а → *29 5*2а → *2а1 6*2а → *2а3 �Содержание 7*2а → *2а5 8*2а → *2а7 9*2а → *2а9 Заметим, что вышеуказанные подстановки будут действовать нужным нам образом и на более высоких разрядах исходного числа (разрядах сотен, тысяч и т. д.), если таковые будут иметься. Наконец, определим марковские подстановки, которые обеспечат остановку алгоритма: *2а → . 1 *2 → . Итак, запишем схему искомого нормального алгоритма Sα. 1. 0*2а → *21 8. 7*2а → *2а5 15.4*2 → *28 2. 1*2а → *23 9. 8*2а → *2а7 16.5*2 → *2а0 3. 2*2а → *25 10.9*2а → *2а9 17.6*2 → *2а2 4. 3*2а → *27 11.0*2 → *20 18.7*2 → *2а4 5. 4*2а → *29 12.1*2 → *22 19.8*2 → *2а6 6. 5*2а → *2а1 13.2*2 → *24 20.9*2 → *2а8 7. 6*2а → *2а3 14.3*2 → *26 21.*2а → . 1 22.*2 → . Приведенный нормальный алгоритм нахождения значений функции f(x) = 2х в десятичной системе счисления станет более понятным, если рассмотреть несколько конкретных примеров: 1) 0*2 → *20 → .0 2) 1*2 → *22 → .2 3) 5*2 → *2а0 → .10 4) 10*2 → 1*20 → *220 → .20 5) 16*2 → 1*2а2 → *232 → .32 6) 99*2 → 9*2а8 → *2а98 → .198 7) 100*2 → 10*20 → 1*200 → *2200 → .200 8) 489*2 → 48*2а8 → 4*2а78 → *2978 → .978 9) 92589*2 → 9258*2а8 → 925*2а78 → 92*2а178 → 9*25178 → → *2а85178 → .185178 �Содержание 6.4. Способы сочетания нормальных алгоритмов Способы сочетания нормальных алгоритмов позволяют строить новые алгоритмы из уже известных. Перечислим способы сочетания нормальных алгоритмов. 1. Суперпозиция алгоритмов. При суперпозиции двух алгоритмов А и В выходное слово первого алгоритма рассматривается как входное слово второго алгоритма В, результат суперпозиции С может быть представлен в виде С(Р) = В(А(Р)). 2. Объединение алгоритмов. Объединение алгоритмов А и В в одном и том же алфавите называется алгоритм С в том же алфавите, преобразующий любое слово Р, содержащееся в пересечении областей определения алгоритмов А и В, в записанные рядом слова А(Р) и В(Р). 3. Разветвление алгоритмов. Разветвление алгоритмов представляет собой композицию D трех алгоритмов А, В и С, причем область определения алгоритма D является пересечением областей определения всех трех алгоритмов А, В и С, а для любого слова Р из этого пересечения D(P) = А(Р), если С(Р) = ; D(P) = В(Р), если С(Р) ≠ , где – пустая строка. 4. Итерация алгоритмов. Итерация (повторение) представляет собой такую композицию С двух алгоритмов А и В, что для любого входного слова Р соответствующее слово С(Р) получается в результате последовательного многократного применения алгоритма А до тех пор, пока не получится слово, преобразуемое алгоритмом В. Пример Составим нормальный алгоритм, вычисляющий значения положительное число) в десятичной системе счисления. функции f(x) = 2х+1 (х – целое Решение В предыдущем параграфе нами были составлены нормальные алгоритмы, вычисляющие значения функций f(x) = 2х и f(x) = х+1, (х – целое положительное число) в десятичной системе счисления. Воспользуемся ими для составления искомого нормального алгоритма. Определим алфавит А: А = {0,1,2,3,4,5,6,7,8,9,*,+}. Условимся обозначать входное слово следующим образом: «23*2+1». Ясно, что на выходе нормального алгоритма в этом случае должно получиться число «47». Очевидно, что для получения выходного слова, нужно сначала применить к входному слову х нормальный алгоритм, вычисляющий значение 2х, далее нужно применить к слову 2х нормальный алгоритм, прибавляющий 1. Для этого необходимо, чтобы после вычисления 2х нормальный алгоритм не останавливался, поэтому заменим марковские подстановки, приводящие к остановке алгоритма (*2а → . 1 и *2 → . ) на «аналогичные», но не останавливающие алгоритм – *2а → 1 и *2 → . �Содержание Итак, запишем схему нормального алгоритма Sa, вычисляющего значения функции f(x) = 2х+1 (х – целое положительное число) в десятичной системе счисления: 1. 0*2а → *21 12.1*2 → *22 23.0+1 → 1 2. 1*2а → *23 13.2*2 → *24 24.1+1 → 2 3. 2*2а → *25 14.3*2 → *26 25.2+1 → 3 4. 3*2а → *27 15.4*2 → *28 26.3+1 → 4 5. 4*2а → *29 16.5*2 → *2а0 27.4+1 → 5 6. 5*2а → *2а1 17.6*2 → *2а2 28.5+1 → 6 7. 6*2а → *2а3 18.7*2 → *2а4 29.6+1 → 7 8. 7*2а → *2а5 19.8*2 → *2а6 30.7+1 → 8 9. 8*2а → *2а7 20.9*2 → *2а8 31.8+1 → 9 10.9*2а → *2а9 21.*2а → 1 32.9+1 → +10 11.0*2 → *20 22.*2 → 33.+1 → .1 34. → . Проиллюстрируем работу составленного нормального алгоритма на нескольких примерах. 1) 23*2+1 → 2*26+1 → *246+1 → 46+1 → 47 → .47 2) 999*2+1 → 99*2а8+1 → 9*2а98+1 → *2а998+1 → 1998+1 → 1999 → .1999 Замечание Отметим, что нормальные алгоритмы Маркова являются не только средством теоретических построений, но и основой специализированного языка программирования, применяемого как язык символьных преобразований при разработке систем искусственного интеллекта; это один из немногих языков, разработанных в России и получивший известность во всем мире. �Содержание 6.5. Принцип нормализации Маркова Создатель теории нормальных алгоритмов А.А. Марков выдвинул гипотезу, получившую название «принцип нормализации Маркова». Принцип нормализации Маркова Для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция нормально вычислима. Иными словами, принцип нормализации заключается в том, что все алгоритмы исчерпываются нормальными алгоритмами или, то же самое, – всякий алгоритм нормализуем. Сформулированный принцип, как и тезисы Черча, Тьюринга, Поста, носит внематематический характер (понятие произвольного алгоритма не является строго определенным) и не может быть строго доказан. Он основывается на том, что все известные в настоящее время алгоритмы являются нормализуемыми. Замечание В теории алгоритмов огромную роль играет тот факт, что все разработанные теории, уточняющие интуитивное понятие алгоритма, равносильны между собой. Другими словами, они описывают один и тот же класс алгоритмически вычислимых функций. Полезно уяснить смысл и значение этого важного результата. В разное время в разных странах ученые независимо друг от друга, изучая интуитивное понятие алгоритма и алгоритмической вычислимости, создали теории, описывающие данное понятие, которые оказались равносильными. Этот факт служит мощным косвенным подтверждением адекватности этих теорий опыту вычислений, справедливости каждого из тезисов Тьюринга, Поста, Черча и Маркова. В самом деле, ведь если бы один из классов оказался шире какого-либо другого класса, то соответствующий тезис Тьюринга, Поста, Черча или Маркова был опровергнут. Например, если бы класс нормально вычислимых функций оказался шире класса рекурсивных функций, то существовала бы нормально вычислимая, но не рекурсивная функция. В силу ее нормальной вычислимости она была бы алгоритмически вычислима в интуитивном понимании алгоритма, и предположение о ее нерекурсивности опровергало бы тезис Черча. Но классы Тьюринга, Поста, Черча и Маркова совпадают, и таких функций не существует. Это служит еще одним косвенным подтверждением тезисов Тьюринга, Поста, Черча и Маркова. �Содержание Вопросы к главе 6 1. Кем и когда были разработаны нормальные алгоритмы? 2. Определите сущность понятий «алфавит», «слово», «подслово». Приведите примеры. 3. Дайте определение марковской подстановки. Приведите пример. 4. Опишите действие частных случаев марковских подстановок: ( ,Q), (P, ), ( , ). Приведите примеры. 5. Что называют формулой подстановки? 6. В чем состоит особенность формулы заключительной подстановки? 7. Что называется схемой нормального алгоритма? Приведите пример. 8. Что называется нормальным алгоритмом Маркова? Приведите пример. 9. Раскройте смысл слов «нормальный алгоритм над алфавитом А». 10. Какая функция называется нормально вычислимой? Приведите примеры. 11. Что называется расширением алфавита А? 12. Какие способы композиции нормальных алгоритмов существуют? В чем их суть? 13. Какой способ композиции нормальных алгоритмов был использован в примере параграфа 4? 14. Сформулируйте принцип нормализации. 15. Раскройте роль эквивалентности различных формальных моделей алгоритма в теории алгоритмов. �Содержание Задания к главе 6 1. Постройте дедуктивную цепочку (последовательность слов), ведущую от слова «мука» к слову «торт», заменяя каждый раз по одной букве так, чтобы каждый раз получалось слово. 2. Пусть A = {a,b,c} и задана следующая нормальная схема: ab → c Sα: cb → a a→. Выясните, какое слово будет результатом применения этого нормального алгоритма к слову: а) abbacb; б) bc. 3. Пусть A = { a, b }. Зададим нормальный алгоритм с помощью алфавита D = { a , b,  ,  ,  } и следующей нормальной схемы: 1. aa   a a 6.  b  b b 2. ab   b a 7.   3. ba   a b 8.   4. bb   b b 9.  . 5.  a  a a 10.    Найдите результат применения данного алгоритма к словам ab, aba. Опишите, что делает данный алгоритм. 4. Пусть A = { a, b }. Зададим нормальный алгоритм с помощью алфавита D = { a , b,  ,  } и следующей нормальной схемы: 1.  a  a a 6.  bb  b b 2.  b  b b 7.   3.  aa  a a 8.  . 4.  ab  b a 9.   5.  ba  a b �Содержание Найдите результат применения данного алгоритма к словам ab, bab. 5. Постройте нормальный алгоритм побуквенного кодирования, т. е. нормальный алгоритм над алфавитом А, выполняющий замену букв m алфавита А словами Кm в этом алфавите. 6. Постройте нормальный алгоритм, преобразующий любое слово Р в алфавите А в проекцию этого слова на алфавит В. (Проекцией слова Р в алфавите А на алфавит В называется результат удаления из слова Р букв алфавита А\В.) 7. Постройте нормальный алгоритм правого присоединения слова aba в алфавите A = {a,b} над этим алфавитом. 8. Постройте нормальный алгоритм: а) преобразующий каждое слово Р в алфавите {a,b,c} в слово abcP; б) преобразующий каждое слово в алфавите {a,b,c} в слово abc. 9. Постройте нормальный алгоритм, применение которого к данному слову в алфавите {a,b,c} приведет к тому, что будет получено слово, содержащее все буквы «а», расположенные в его начале. 10. Постройте нормальный алгоритм, перерабатывающий любое слово в алфавите {a,b,c} в слово, в котором все буквы «а» (если они имеются) расположены левее остальных, а все буквы «b» левее всех букв «с». 11. Постройте нормальный алгоритм, преобразующий каждое слово в алфавите {a,b} в слово «baba». 12. Постройте нормальный алгоритм над алфавитом {1}, применение которого к слову, состоящему из четного числа «1», приводило бы к слову «*», а применение этого же алгоритма к слову, состоящему из нечетного числа «1» к слову «+». 13. Постройте нормальный алгоритм, преобразующий любое слово в алфавите {a,b}, содержащее хотя бы две буквы «a», в слово «baabab», а каждое слово, содержащее не более одной буквы «a» в слово, получающееся из исходного заменой букв «а» и «b» друг на друга. 14. Известно, что A = {0,1,2,3,4,5,6,7,8,9}; нормальный алгоритм задан в его расширении B = A U {a,b} и определен следующей схемой: �Содержание 1. 0b → .1 10. 9b → b0 2. 1b → .2 11. b → .1 3. 2b → .3 12. a0 → 0a 4. 3b → .4 13. a1 → 1a 5. 4b → .5 14. a2 → 2a 6. 5b → .6 15. a3 → 3a 7. 6b → .7 16. a4 → 4a 8. 7b → .8 17. a5 → 5a 9. 8b → .9 18. a6 → 6a 19. a7 → 7a 26. 4a → 4b 20. a8 → 8a 27. 5a → 5b 21. a9 → 9a 28. 6a → 6b 22. 0a → 0b 29. 7a → 7b 23. 1a → 1b 30. 8a → 8b 24. 2a → 2b 31. 9a → 9b 25. 3a → 3b 32.  → a Примените данный алгоритм к словам 499, 328, 789. Вычисляет ли данный алгоритм какую-либо функцию? Если да, то какую? 15. Известно, что нормальный алгоритм в алфавите A = {1} со следующей схемой Sa: 111 → 11 → . Sα: 1→. → .1 вычисляет некоторую функцию f(x) (х слова в А). Определите формульное выражение функции f(x). 16. Постройте нормальный алгоритм, вычисляющий числовую функцию f(x) = x+y (аргумент х представлен в унарной записи). �Содержание 17. Пусть M, N, Q, R обозначают натуральные числа, представленные в унарной форме. Постройте нормальный алгоритм, который перерабатывает: а) всякую пару натуральных чисел N*M в абсолютную величину их разности; б) всякое натуральное число в остаток от деления числа на 5; N  в) всякое натуральное число N в   ; 5 г) всякое натуральное число N в пару Q*R, где Q деления; частное от деления N на 5, а R остаток от этого д) всякую пару натуральных чисел N*M в наибольший общий делитель этих чисел; е) всякую пару натуральных чисел N*M в произведение этих чисел. 18. Замените в десятичном числе все четные цифры на «1», а нечетные на «0». 19. Замените все буквы «а» в слове на «?», если слово начинается на «а». 20. Замените все буквы «я» в слове на «!», если слово заканчивается на «я». 21. Удалите из слова все буквы «б», если их четное число. 22. Удалите из слова все буквы «б», если их нечетное число. 23. Удвойте в слове все одиночные буквы. 24. Если в слове есть одиночные символы, то удалите их. 25. Если в слове есть одинаковые рядом стоящие символы, то удалите их, иначе продублируйте все символы. 26. Поменяйте местами вторую и предпоследнюю буквы в слове. 27. Поменяйте местами буквы в слове попарно. �Содержание 28. Если в слове четное количество букв, то замените все «а» на «!». 29. Если в слове нечетное количество букв, то после каждой буквы поставьте «!». 30. Если в слове нечетное количество букв «и», то удалите их. 31. Если в слове четное количество букв «а», то удалите первую из них. 32. Если в слове встречаются две подряд буквы «а», то замените каждую пару на «!!», иначе вместо данного слова запишите «*». 33. Удалите в слове все символы, кроме первого и последнего. 34. Если в десятичном числе встречаются последовательности «012», то замените их на «***», иначе добавьте в конце слова знак «–». 35. Добавьте в конце слова столько «+» сколько в слове встречается символ «ы». �Содержание Заключение Рассмотренные нами алгоритмические модели (класс рекурсивных функций, машина Тьюринга, машина Поста, машины произвольного доступа, нормальные алгоритмы Маркова) отождествляют с формальным понятием алгоритма. Моделируя любые другие разумные алгоритмические модели, они универсальны, а поэтому позволяют снять возможное возражение против того, что жесткая фиксация алгоритмической модели приводит к потере общности формализации алгоритма. Основные алгоритмические модели в теории алгоритмов принято разделять на три типа. Первый тип трактует алгоритм как некоторое детерминированное устройство, способное выполнять в каждый момент лишь строго фиксированное множество операций. Основной теоретической моделью такого типа является машина Тьюринга, оказавшая существенное влияние на понимание логической природы разрабатываемых ЭВМ. К этому типу относят и такие алгоритмические модели, как машина Поста, машины произвольного доступа. Второй тип связывает понятие алгоритма с традиционным представлением процедурами вычисления значений числовых функций. Основной теоретической моделью этого типа являются рекурсивные функции исторически первая формализация алгоритма. Третий тип алгоритмических моделей это преобразования слов в произвольных алфавитах, в которых операциями являются замены частей слов другим словом. Основной теоретической моделью этого типа являются нормальные алгоритмы Маркова. Все рассмотренные нами алгоритмические модели эквиваленты, и роль их огромна. Они оказали существенное влияние на развитие ЭВМ и практику программирования. Несмотря на то, что все алгоритмические модели эквивалентны, на практике они существенно различаются сложностными эффектами, возникающими при реализации алгоритмов, что способствовало появлению различных направлений в программировании. Так, микропрограммирование строится на идеях машин Тьюринга, структурное программирование заимствовало свои конструкции из теории рекурсивных функций, языки символьной обработки информации (например, ПРОЛОГ) берут начало от нормальных алгоритмов Маркова. �Содержание Ответы, указания и решения Глава 1 Глава 2 Глава 3 Глава 4 Глава 5 Глава 6 �Содержание Глава 1 Задание 1. Решение. Алгоритм сложения в столбик двух натуральных чисел (первое слагаемое содержит m цифр, второе n , считаем, что m  n ): 1) запишем исходные числа в столбик так, чтобы разряды единиц были под разрядами единиц, разряды десятков были под разрядами десятков и т. д., т. е. числа выровнены по младшему разряду; 2) положим i  1 ( i обрабатываемый разряд, разряды пронумерованы справа налево), p  0 ( p значение переноса в старший разряд); 3) сложим цифры i -го разряда обоих слагаемых (если у первого слагаемого уже в данном разряде цифр нет, то считаем, что прибавляем 0), прибавим к результату p ; 4) если получившееся число больше либо равно 10, то в i -й разряд результата запишем младшую цифру получившегося числа (остаток от его деления на 10), а p положим равным 1, иначе в i -й разряд результата запишем получившееся число, а p положим равным 0; 5) увеличим i на единицу; 6) если i  n , то переходим на шаг 3; 7) если p  0 , то конец алгоритма, иначе в ( n  1) -й разряд результата запишем 1, конец алгоритма. При анализе этого алгоритма надо обратить внимание на тот факт, что в старший разряд может переноситься только единица. Задание 2. Указание. Для того чтобы приведенный способ стал алгоритмом, надо конкретизировать шаги 1–3, указав точные значения для радиусов окружностей. Задание 3, 4, 5. Указание. Проверьте выполнимость всех основных свойств алгоритма. Задание 6. Решение. Система команд колдуна: − поставили сосуд с эликсиром на огонь; − сняли эликсир с огня; − перевернули трехминутные часы; − перевернули восьмиминутные часы; − проверили, что часы пересыпались. Алгоритм варки эликсира бессмертия: 1) перевернули трехминутные часы; перевернули восьмиминутные часы; 2) если трехминутные часы пересыпались, то переворачиваем их и ставим эликсир на огонь; 3) если трехминутные часы пересыпались, то переворачиваем их (эликсир варится уже 3 минуты); �Содержание 4) если восьмиминутные часы пересыпались, то переворачиваем часы трехминутные (эликсир варится 5 минут; после переворота трехминутных часов в верхней колбе песка осталось на 2 минуты); 5) если трехминутные часы пересыпались, то снимаем эликсир с огня. Подчеркнем, что могут быть предложены и другие решения этой задачи. Задание 7. Указание. Составьте алгоритм, который правильно вычисляет и 0! 1 . Задание 8. Решение. Докажем, что в результате работы алгоритма «Решето Эратосфена» в последовательности чисел от 1 до N не будет зачеркнуто ни одно простое число. Действительно, на каждом шаге зачеркиваются только числа, кратные каким-то другим числам. Число k  1 из этой последовательности останется незачеркнутым только в том случае, если оно не делится ни на одно из незачеркнутых чисел, не превосходящих N , среди которых содержатся все простые числа, не превосходящие N . Докажем, что любое составное число m имеет простой делитель, не превосходящий m  pq , причем p 2 m . Пусть 2 наименьший множитель ( p  q ) . Тогда p  p  p  pq  m , т. е. p  m , т. е. p  m . Следовательно, если m составное, то его наименьший делитель меньше m , что и требовалось доказать. Таким образом, в исходной последовательности остаются незачеркнутыми все простые числа и только они. Задание 9. Указание. Введите вспомогательные обозначения: I вспомогательная переменная, Slag очередное слагаемое суммы, S искомая сумма. В качестве условия в блок-схемах попробуйте ввести следующее: i  n . Задание 10. Решение. В приведенном алгоритме есть две ошибки. Первая ошибка заключается в том, что при нечетном n и для k  m будет неверно выполняться п. 6. Для любого n количество пар, n которые надо обработать, равно , и в качестве начальных значений min и max надо брать значения 2 соответствующих элементов последней m -й полной пары для четных n или элемент an в противном случае. Вторая ошибка состоит в выборе типа циклической конструкции. В предложенном варианте алгоритма при n  1 получим зацикливание, а при n  1 алгоритм не будет обрабатывать последнюю пару. Правильный алгоритм: 1. Разобьем исходную последовательность на пары. Последняя пара может быть неполной, если число n нечетно. �Содержание 2. Положим m  n (m 2 число пар, которые надо обработать). 3. Упорядочим числа в каждой паре по возрастанию. Будем элементы в паре обозначать Pk ,1 и Pk , 2 , где k номер пары. 4. Положим min  an и max  an при нечетном n . В противном случае положим: min  Pm ,1 и max  Pm , 2 . 5. Положим k  1 . 6. Если k  m , то конец алгоритма. 7. Если Pk , 2  max , тогда max  Pk , 2 . 8. Если Pk ,1  min , тогда min  Pk ,1 . 9. Увеличим k на единицу. 10. Переходим на п. 6. �Содержание Глава 2 Задание 1. Указание. Воспользуйтесь определением вычислимой функции. Задание 2. Ответ. а) x1 ; б) не определено; в) x1  2 ; г) 0; д) x2  4 ; е) 4. Задание 3. Указание. Можно, причем только из двух простейших функций: O, S . Задание 4. Ответ. а) vz(u 2  2 u ) ; б), в) не определено. Задание 5. Ответ. а) 2uv 2 z 2  u  u  v  z ; б), в) не определено. Задание 6. Решение. а) Переобозначим: f ( x , y )  h ( x , y )  xy . Будем искать функции g 1 ( x ) и f 3 ( x, y , z ) из определения примитивной рекурсии: h( x,0)  x  0  0  g ( x)  O ( x),  h( x, y  1)  x  ( y  1)  xy  x  f ( x, y, h( x, y ))  f ( x, y, xy ).   z Следовательно, g 1 ( x )  O ( x ) , f 3 ( x, y , z )  z  x . Функция же суммы в свою очередь может быть получена из простейших с помощью оператора примитивной рекурсии (доказано ранее в § 2 главы 3). А поэтому исходная функция f ( x , y )  xy может быть получена из простейших с помощью оператора примитивной рекурсии. определение д) Используйте, что f ( x )  x  1  определение 0, если x  y , 0, если x  0,  и f ( x, y )  x  y     x  1, если x  0  x  y , если x  y. е) Используйте равенство x  y  ( x  y )  ( y  x ) . Задание 7. Решение. 1. Найдем аналитическую запись функции f 2 ( x, y ) . Из схемы примитивной рекурсии:  f ( x,0)  g ( x )  I11 ( x ),   f ( x, y  1)  h( x, y , f ( x, y ))  I 33( x, y , f ( x, y ))  1  f ( x, y )  1. Тогда: �Содержание f ( x ,0 )  x ; f ( x ,1)  f ( x ,0)  1  x  1 ; f ( x ,2)  f ( x ,1)  1  ( x  1)  1  x  2 ; …………………………………………..….. Естественно предположить, что f ( x , y )  x  y ,  y    {0}. Докажем это методом математической индукции: 1) доказательство базиса очевидно, т .к. f ( x,0)  x  0 ; 2) предположим, что f ( x , y )  x  y для некоторого y . Тогда: предположение f ( x, y  1)  f ( x, y )  1  ( x  y )  1  x  ( y  1) , что и требовалось доказать. 3 Таким образом, из функций h ( x , y , z )  I 3 ( x , y , z )  1 и g ( x )  I11 ( x ) с помощью оператора примитивной рекурсии получается функция f ( x , y )  x  y. 2. Вычислим f ( 2,5) . Так как f ( x , y )  x  y , то f ( 2,5)  2  5  7 . Или из схемы примитивной рекурсии: f ( 2,5)  f ( 2, 4  1)  f ( 2, 4 )  1 ; f ( 2, 4)  f ( 2,3  1)  f ( 2,3)  1 ; f ( 2,3)  f ( 2, 2  1)  f ( 2, 2)  1 ; f ( 2, 2)  f ( 2,1  1)  f ( 2,1)  1 ; f ( 2,1)  f ( 2,0  1)  f ( 2,0)  1 ; Но т. к. f ( 2,0)  2 , то f ( 2,1)  3 , f ( 2,2)  4 , f ( 2,3)  5 , f ( 2,4)  6 , f ( 2,5)  7 . 0, если у  N Задание 8. Ответ. h(u , y )   2u , если у  0 Задание 9. Ответ. h (u , v, y )  2 u u 2 v y 1. Задание 10. Ответ. а) f ( x, y )  x xy x x x ; б) f ( x, y )  x  . y �Содержание Задание 11. Решение. б) Попытаемся найти функции h и g , такие, что: 1 f  R ( h, g ) . Ясно, что 2 g ( x )  const , h ( x, y ) . Из схемы примитивной рекурсии:  f (0)  const  g ( x)  2  0  1  1  S (O )  G ( S , O ),   f ( y  1)  h( y, f ( y ))  h( y, 2 y  1)  2( y  1)  1  (2 y  1)  2   z Итак: 1) g ( x )  1  G ( S , O ) примитивно рекурсивна; 2) h ( y , z )  z  2 или h ( x , y )  y  2  S ( S ( y ))  G ( S , S ( y )) примитивно рекурсивна. Следовательно, исходная функция f ( x )  2 x  1 является примитивно рекурсивной. наименьшее целое неотрицательное число, Задание 12. Решение. а) Нужно показать, что ( x  y ) являющееся решением уравнения y  z  x относительно z .Это действительно так. Поэтому исходное равенство верно. г) Исходное равенство неверно, потому что значение выражения  y [ y ( y  ( x  1))  0 ] не определено при y  0 (т. к. не определено значение терма 0(0  ( x  1))  ), а именно не определена разность). 1 В то же время подчеркнем, что уравнение y ( y  ( x  1))  0 имеет решение y  x  1 . Задание 13. Решение. а)  ( x )   y [ x  2 y  0] . Отметим, что функция  определена лишь на числах вида 2 k, k   (поясните почему) и для каждого из них:  ( 2 k )   y [ 2 k  2 y  0]   y [ 2 k  y  0]  k , где k  0,1,2,3,  в)  ( x )   y [8  0] не определена на всех x . Задание 15. Указание. Используйте функцию «усеченного вычитания». Задание 16. Указание. Используйте определение оператора минимизации. . �Содержание Глава 3 Задание 1. Решение. Данная машина применима к любым двоичным словам, в том числе она применима и к нулевому входному слову. Машина Тьюринга выполняет инверсию двоичных слов (заменяет все «1» на «0» и наоборот). Задание 4. Решение. Понятность. На каждом шаге в ячейку пишется символ из внешнего алфавита, автомат делает одно движение ( Л , П , С ) и машина Тьюринга переходит в одно из допустимых состояний: все эти действия входят в систему команд данного исполнителя. Дискретность. Машина Тьюринга может перейти к ( k  1) -у шагу только после выполнения k -го шага, так как именно k -й шаг определяет, каким будет ( k  1) -й шаг. Детерминированность. В каждой клетке таблицы машины Тьюринга записан лишь один вариант действия. На каждом шаге результат определен однозначно, следовательно, последовательность шагов решения задачи определена однозначно, т. е. если машине Тьюринга на вход подают одно и то же входное слово, то выходное слово каждый раз будет одним и тем же. Результативность. Содержательно результат каждого шага и всей последовательности шагов определен однозначно, следовательно, правильно написанная машина Тьюринга за конечное число шагов перейдет в состояние q0 , т. е. за конечное число шагов будет получен ответ на вопрос задачи. Массовость. Каждая машина Тьюринга определена над всеми допустимыми словами из алфавита, в этом и состоит свойство массовости. Каждая машина Тьюринга предназначена для решения одного класса задач, т. е. для каждого класса задач пишется своя (новая) машина Тьюринга. Задание 5. Решение. (д) Выпишем последовательность конфигураций машины при переработке ею слова 111 из начального стандартного положения. �Содержание �Содержание Задание 6. Указание. а) Машина останавливается, выдав слово 1 a0 1 a0 a0 1, обозревая в состоянии q3 четвертую ячейку слева. б) Машина останавливается, выдав слово 1 a0 1 a0 1, при этом она обозревает в состоянии q3 вторую левую пустую ячейку от полученного слова. в) Машина не меняет данного слова и останавливается в состоянии q3 , обозревая вторую левую пустую ячейку от этого слова. Задание 9. Решение. (д) 11111. Данная машина Тьюринга реализует операцию сложения: в результате ее работы на ленте записано подряд столько единиц, сколько их было всего записано по обе стороны от звездочки перед началом работы машины. Задание 11. Ответ. Машина Тьюринга выполняет сложение данных чисел. Задание 13. Решение. В качестве внешнего алфавита возьмем двухэлементное множество A  {a0 ,1} , где a0 символ пустой буквы. Количество необходимых внутренних состояний будет определено в процессе составления программы. Будем считать, что машина начинает работать из стандартного начального положения, т. е. когда в состоянии q1 обозревается крайняя правая единица из n записанных на ленте. Рассмотрим три случая: 1) n  2 , 2) n  1 , 3) n  0 . Случай 1. n  2 Запишем начальную конфигурацию. Начнем с того, что сотрем первую единицу, перейдем к обозрению следующей левой ячейки и сотрем там единицу. На каждом таком переходе машина должна переходить в новое внутреннее состояние, ибо в противном случае будут стерты вообще все единицы, записанные подряд. Вот команды, осуществляющие описанные действия: q11  q 2 a0 Л , q 2 1  q3 a 0 Л . Запишем конфигурации машины Тьюринга на данных этапах ее работы. �Содержание Машина Тьюринга теперь находится в состоянии q3 и обозревает третью справа ячейку из тех, в которых было записано входное слово (последовательность из n  2 единиц). Не меняя содержимого обозреваемой ячейки, машина должна остановиться, т. е. перейти в заключительное состояние q0 , независимо от содержимого ячейки. Вот эти команды: q3 a 0  q 0 a 0 С , q31  q01С Соответствующая конфигурация машины будет иметь следующий вид: Случай 2. n  1 Если на ленте записана одна единица, то начальная конфигурация будет иметь следующий вид: Следующий шаг работы машины Тьюринга будет выполнен в соответствии с командой q11  q2 a0 Л , в результате которого машина будет находиться в состоянии q2 и обозревать вторую справа ячейку, в которой записан символ пустой буквы a0 . Запишем соответствующую конфигурацию машины: �Содержание По условию задачи необходимо, чтобы в этом случае машина работала вечно, т. е. не приходила в состояние останова q0 . Это можно обеспечить, например, такой командой: q 2 a0  q 2 a0 Л Выполняя эту команду, шаг за шагом, машина будет двигаться по ленте неограниченно влево: Случай 3. n  0 Наконец, если на ленте не записано ни одной единицы, то машина, по условию, также должна работать вечно. В этом случае в начальном состоянии q1 обозревается ячейка с содержимым a0 : Вечную работу машины можно обеспечить следующей командой: q1a0  q1a0 Л Запишем составленную программу (функциональную схему) построенной машины Тьюринга в виде таблицы: Задание 17. Решение. Будем формировать исходное число на ленте слева от штрихов (без пустого символа между числом и штрихами). В начальный момент машина Тьюринга обозревает любой из штрихов и находится в состоянии q1 . Запишем алгоритм решения задачи в текстовой форме: 1) найдем правый конец слова на ленте; 2) если слово будет оканчиваться штрихом, то сотрем этот штрих, иначе остановим машину; 3) прибавим к числу единицу и перейдем к п. 1. �Содержание В соответствии с этим алгоритмом каждый раз стирается самый правый штрих и к числу прибавляется единица. Выполнение алгоритма продолжается до тех пор, пока не будет стерт самый последний штрих, после чего, согласно условию из п. 2, машина Тьюринга остановится. Заметим, что каждый из трех пунктов алгоритма может быть реализован одним состоянием машины Тьюринга: 1) состояние q1 автомат ищет правый конец слова; 2) состояние q2 автомат стирает штрих; 3) состояние q3 прибавление к числу единицы. Ниже приведена программа машины Тьюринга для решения предлагаемой задачи. Задание 27. Ответ. Задание 34. Ответ. f ( x )  x  2 . Задание 35. Ответ. f ( x , y )  x . Задание 39. Решение. Покажем, что машину Тьюринга можно представить также, как и конечный автомат в следующем виде: А = {S,X,Y,s0,d,v}, где �Содержание S – конечное непустое множество (состояний); X – конечное непустое множество входных сигналов (входной алфавит); Y – конечное непустое множество выходных сигналов (выходной алфавит); s0 Є S – начальное состояние; d: S×X → S – функция переходов; v: S×X → Y – функция выходов. Действительно, в машине Тьюринга Т = {S,X,Y,s0,d,v}: S = Q = {q0,q1,q2,…,qn} – алфавит внутренних состояний; X = А = {a0,a1,a2,…,am} – алфавит входных символов (входной алфавит); Y = {a0П,а0Л,а0С,а1П,а1Л,а1С,…,amП,amЛ,amС} – множество выходных сигналов (выходной алфавит); s0 = q1 Є Q – начальное состояние; d: S×X → S – функция переходов и v: S×X → Y – функция выходов задается в машине Тьюринга одновременно командами вида qjai → qkalX, где Х = {П,Л,С}. В соответствии с указанной командой: d(qjai) = qk, а v(qjai) = alX, где Х = {П,Л,С}. Например, пусть дана машина Тьюринга Т с внешним алфавитом A = {а0,1} (здесь а0 – это символ пустой ячейки), алфавитом внутренних состояний Q = {q0,q1,q2} и со следующей программой: q1а0 → q2а0П, q2а0 → q01С, q11 → q11П, q21 → q21П. Зададим функции переходов d и выходов v в этой машине Тьюринга Т таблично. Функция переходов машины Тьюринга Т d а0 1 q0 – – q1 q2 q1 q2 q0 q2 Функция выходов машины Тьюринга Т v а0 1 q0 – – q1 а0П 1П q2 1С 1П �Содержание Задание 40. Решение. Рассмотрим, например, машину Тьюринга Т с внешним алфавитом A = {а0,1} (здесь а0 – это символ пустой ячейки), алфавитом внутренних состояний Q = {q0,q1,q2} и со следующей программой: q1а0 → q2а0П, q2а0 → q01С, q11 → q11П, q21 → q21П. Зададим функции переходов d и выходов v в этой машине Тьюринга Т таблично. Функция переходов машины Тьюринга Т d а0 1 q0 – – q1 q2 q1 q2 q0 q2 Функция выходов машины Тьюринга Т v а0 1 q0 – – q1 а0П 1П q2 1С 1П На основе составленных таблиц представим машину Тьюринга Т в виде ориентированного графа. Опишем процесс построения ориентированного графа на основе программы машины Тьюринга. Каждая команда программы машины Тьюринга qjai → qkalX, где Х = {П,Л,С} представляется ребром ориентированного графа (направленным отрезком), соединяющим две его вершины. Причем каждой вершине приписывается соответствующее состояние машины Тьюринга (qj или qk), а дуге – символ ai/ alX. �Содержание Глава 4 Задание 1. Решение. Программа никогда не остановится, лента машины Поста будет иметь следующий вид: Задание 2. Решение. Мы знаем, что на ленте есть метка, но не знаем, в какую сторону нужно двигаться. Каким же способом можно решить эту задачу? А вот каким. Представим, что мы стоим на бесконечной в обе стороны дороге, а где-то на этой дороге лежит камень, который мы хотим найти. Мы не знаем, где он лежит, знаем только, что где-то он непременно лежит. Как нам поступить? В какую бы сторону мы ни пошли, может случиться, что волшебный камень лежит в другой стороне. Очевидно, что нам надо двигаться попеременно то в одну сторону, то в другую, постоянно увеличивая размах своих колебаний. Сначала делаем шаг в одну сторону, потом два шага в другую сторону, потом три шага снова в первую сторону, потом четыре шага во вторую сторону и так далее до тех пор, пока не наткнемся на волшебный камень. Но возникает одна трудность: как определить момент, когда надо поворачивать, т. е. менять направление? Казалось бы очень просто. Надо вести счет шагов. Но мы имеем дело с бесконечной лентой. Нам, возможно, придется запоминать очень большие числа, которые трудно хранить в памяти, а сколь угодно большие числа хранить в памяти трудно. Однако выход из положения есть. Будем отмечать пройденный путь камешками. Дойдя по камешкам в одну сторону до конца, будем класть новый камешек, и поворачивать обратно. И так до тех пор, пока не найдем искомый камень. Недостаток этого метода состоит в том, что надо иметь неограниченный запас камешков. Хотя для машины Поста это не является препятствием. Можно обойтись и всего двумя камешками. Для этого надо вначале нужно положить один камешек слева от себя, другой справа. А затем ходить между ними и передвигать их. Запишем программу для машины Поста. 1V 2 {положили левый камешек} 23 3 ? 5,4 4! {нашли метку, конец} 5V 6 {положили правый камешек} �Содержание 6  7 {ищем левый камешек} 7 ? 6,8 8X 9 {стираем левый камешек} 9  10 10 ?11,4 11V 12 {передвигаем левый камешек} 12  13 {ищем правый камешек} 13 ?12,14 14 X 2 {стираем правый камешек и повторяем действия} Задание 3. Решение. Алгоритм решения этой задачи основан на следующей идее. К отдельно стоящей метке будем постепенно передвигать метки массива, начиная с левого края. То есть крайнюю левую метку массива будем перемещать на правый край массива, уменьшая тем самым расстояние до отдельной метки. Если метка отстоит от массива на одну ячейку, то нам достаточно выполнить только одно передвижение. В общем случае независимо от длины массива n нам придется сделать всего m передвижений. Запишем программу для машины Поста. 1X 2 23 3 ? 4,2 4V 5 56 6 ? 8,7 7! 89 9 ?10,8 10  1 Задание 4. Решение. Пусть каретка стоит на левом элементе левого числа. Будем стирать по одной левой метке у каждого числа, пока одно из чисел не кончится. Тогда образовавшееся свободное пространство между числами вновь заполним метками (мы можем это сделать, так как знаем местоположение последней стертой метки), а лишние метки (большего числа) сотрем. Обозначим �Содержание левое число a, а правое b. Запишем программу для машины Поста. 1X 2 {уменьшили a на 1} 23 3 ? 4,11 {число a закончилось?} 4V 5 {восстанавливаем метки} 56 6 ? 4,7 {число b началось?} 7 X 8 {стираем лишние метки b} 89 9 ?10,7 {число b стерто?} 10! 11  12 {ищем конец a} 12 ?13,11 13  14 {ищем начало b} 14 ?13,15 15X 16 {уменьшили b на 1} 16  17 17 ?18,26 {число b закончилось?} 18  19 19  20 20V 21 {восстанавливаем метки} 21  22 22 ? 20,23 {число a началось?} 23 X 24 {стираем лишние метки a} 24  25 25 ?10,23 {число a стерто?} �Содержание 26  27 {ищем правый конец числа a} 27 ? 26,28 28  29 {ищем начало a} 29 ? 30,27 {число a прошли?} 30  1 {повторяем действия} Задание 5. Указание. Составим пошаговый алгоритм решения этой задачи. Будем считать, что в начале работы весь массив является нераздвинутым. В результате выполнения очередной итерации алгоритма в нераздвинутой части удаляются две левых метки, а к раздвинутой части справа через пустую ячейку пара меток приписывается. Алгоритм заканчивает работу, если в нераздвинутой части осталась одна или две метки. В начале работы каретка находится на левой метке исходного массива (входного слова). 1. Если в нераздвинутой части осталось не более двух меток, то конец алгоритма. 2. Удаляем в нераздвинутой части две левых метки. 3. Ищем правый конец раздвинутого массива. 4. Ставим через пустую ячейку две метки. 5. Ищем левый конец нераздвинутого массива. Признаком окончания поиска являются две подряд идущие пустых ячейки. 6. Переход на п. 1. Задание 8. Указание. Первая идея решения: оставить в каждом массиве по одной метке, а затем все метки сдвинуть в единый массив. Вторая идея решения: будем «считать» массивы слева направо, удаляя каждый «посчитанный» массив. При этом слева от последовательности оставшихся массивов будем накапливать массив меток, длина которого соответствует числу «посчитанных» массивов. Задание 11. Указание. Идея решения состоит в следующем: во вторых ячейках от каждого края массива ставим «маячки-пузырьки» (эти ячейки делаем пустыми). Далее последовательно перемещаем к центру левый и правый пузырек. Эти пузырьки встретятся ровно на центральном элементе исходного массива. При реализации программы надо отдельно учесть три случая: n  1, n  3, n  5 . Задание 12. Указание. Идея решения состоит в следующем. Сначала между двумя левыми и двумя правыми метками ставим «маячки» пустые клетки. Первым ставим левый маячок. Затем поочередно сдвигаем эти маячки к центру. Как только маячки сомкнутся, то вместо правого маячка ставим метку, идем к правому краю массива и удаляем самую правую метку. Для простоты считаем, что каретка находится над самой левой меткой. �Содержание Глава 5 Задание 1. Решение. Условимся, что начальной конфигурацией МПД будет выступать последовательность чисел (х,0,0,…), т. е. в регистре R1 будет записано число х, а в остальных регистрах R2, R3, … – 0. Идея составления искомого алгоритма состоит в следующем: будем прибавлять 1 к r3 и 2 к r2 до тех пор, пока r2 не станет равным х; тогда r3 даст результат, т. е. значение f(x). Опишем назначение используемых регистров: R1 – предназначено для записи числа х, кроме того именно в этот регистр будет помещено искомое значение f(x); R2, R3 – вспомогательные регистры, используемые в ходе работы программы. Искомая программа будет иметь следующий вид: 1) J(1,2,6), 2) S(3), 3) S(2), 4) S(2), 5) J(1,1,1), 6) T(3,1). Проиллюстрируем работу МПД по составленной программе на конкретном примере. Пусть х = 8, т. е. в регистре R1 записано число 8. Номер команды Содержимое регистров Команда R1 R2 R3 8 0 0 1 J(1,2,6) 8 0 0 2 S(3) 8 0 1 3 S(2) 8 1 1 4 S(2) 8 2 1 5 J(1,1,1) 8 2 1 1 J(1,2,6) 8 2 1 2 S(3) 8 2 2 3 S(2) 8 3 2 �Содержание 4 S(2) 8 4 2 5 J(1,1,1) 8 4 2 1 J(1,2,6) 8 4 2 2 S(3) 8 4 3 3 S(2) 8 5 3 4 S(2) 8 6 3 5 J(1,1,1) 8 6 3 1 J(1,2,6) 8 6 3 2 S(3) 8 6 4 3 S(2) 8 7 4 4 S(2) 8 8 4 5 J(1,1,1) 8 8 4 1 J(1,2,6) 8 8 4 6 T(3,1) 4 8 4 Остановка МПД будет осуществляться после выполнения последней (шестой) команды – команды переадресации. Задание 2. Ответ: искомая программа может, например, иметь следующий вид: 1) J(2,3,9), 2) S(3), 3) J(5,4,7), 4) S(1), 5) S(5), 6) J(1,1,3), 7) T(1,4), 8) J(1,1,1). �Содержание Глава 6 Задание 1. Ответ: например, а) мука – лука – лупа – купа – кипа – кира – кора – корт – торт. б) мука – рука – река – века – вера – лера – лора – пора – порт – торт. Задание 2. Ответ: а) acb; б) неприменим. Задание 3. Ответ: abab, abaaba; алгоритм удваивает слова. Задание 4. Ответ: abab, babbab; алгоритм удваивает слова. Задание 5. Решение. Поставим в соответствие каждой букве m алфавита А определенное слово Кm в этом алфавите. Теперь, заменяя в произвольном слове Р в алфавите А каждую букву m соответствующим словом Кm, получим слово в алфавите А, которое и будет являться результатом замены в слове Р букв m словами Кm. Учитывая сказанное, построим нормальный алгоритм побуквенного кодирования:  m  K m Sα:  .   Здесь буква m пробегает алфавит А. Например, пусть A = {a,b}, Ка = aa, Кb = bab. Перепишем нормальную схему: a  aa Sα: b  bab  .   Опишем процесс работы нормального алгоритма над словом bba: bba   bba  bab  ba  babbab  a  babbabaa    .babbabaa Задание 6. Решение. Соответствующий алгоритм задается следующей нормальной схемой:  x  x Sα: h    .   �Содержание Здесь буква х пробегает множество В, h множество А\В. Например, пусть A = {a,b,c,d}, B = {a,c}, P = abcddcba. Тогда А\В = {b,d} и проекцией слова Р в алфавите А на алфавит В будет являться слово «acca» в алфавите В. Соответствующий нормальный алгоритм задается следующей нормальной схемой:  a  a  c  c b   Sα: d    .   Задание 7. ca  ac cb  bc  Ответ:  c  .aba   c Задание 14. Ответ: 500, 329, 790; данный нормальный алгоритм вычисляет функцию f(x) = x+1. Задание 15. , если х не делится на 3, Ответ: f ( x )   1, если х делится на 3. �Содержание Библиографический список 1. Герасимов, А.С. Курс математической логики и теории учеб. пособие / А.С. Герасимов. – Санкт-Петербург : Изд-во «ЛЕМА», 2011. – 284 с. вычислимости : 2. Игошин, В.И. Задачи и упражнения по математической логике и теории алгоритмов : учеб. пособие / В.И. Игошин. Москва : Академия, 2007. 303 с. 3. Игошин, В.И. Математическая логика и теория алгоритмов : учеб. пособие / В.И. Игошин. Москва : Издательский центр «Академия», 2008. 448 с. 4. Крупский, В.Н. Теория алгоритмов : учеб. пособие / В.Н. Крупский, В.Е. Плиско. – Москва : Академия, 2009. – 206 с. 5. Макконнелл, Дж. Основы современных алгоритмов / Дж. Макконнелл ; под ред. С.К. Ландо. Москва : Техносфера, 2006. 368 с. 6. Мальцев, А.И. Алгоритмы и рекурсивные функции / А.И. Мальцев. 368 с. Москва : Наука, 1986. 7. Матрос, Д.Ш. Теория алгоритмов : учебник / Д.Ш. Матрос, Г.Б. Поднебесова. – Москва : БИНОМ, Лаборатория знаний, 2008. – 202 с. 8. Могилев, А.В. Информатика : учеб. пособие / А.В. Могилев, Н.И. Пак, Е.К. Хеннер ; под ред. Е.К. Хеннера. Москва : Издательский центр «Академия», 2007. – 848 с. 9. Могилев, А.В. Практикум по информатике : учеб. пособие / А.В. Могилев, Е.К. Хеннер ; под ред. Е.К. Хеннера. М. : Издательский центр «Академия», 2001. – 608 с. Н.И. Пак, 10.Носов, В.А. Основы теории алгоритмов и анализа их сложности [Электронный ресурс]. – Режим доступа: http://intsys.msu.ru/staff/vnosov/theoralg.htm 11.Поляков, В.И. Основы теории алгоритмов : учеб. пособие / В.И. Поляков, В.И. Скорубский. – Санкт-Петербург : НИУ ИТМО, 2012. – 51 с. 12.Рублев, В.С. Основы теории алгоритмов : учеб. пособие / Р.С. Рублев. – Ярославль : ЯрГУ, 2005. – 143 с. 13.Судоплатов, С.В. Математическая логика и теория алгоритмов : учебник / С.В. Судоплатов, Е.В. Овчинникова. Новосибирск : Изд-во НГТУ, 2010. 256 с. 14.Чеботарев, С.В. Теория алгоритмов : учеб. пособие / С.В. Чеботарев. 146 с. Барнаул : БГПУ, 2005. � Dublin Core The Dublin Core metadata element set is common to all Omeka records, including items, files, and collections. For more information see, http://dublincore.org/documents/dces/. Title A name given to the resource Дронова Екатерина Николаевна Dublin Core The Dublin Core metadata element set is common to all Omeka records, including items, files, and collections. For more information see, http://dublincore.org/documents/dces/. Title A name given to the resource Основные алгоритмические модели Subject The topic of the resource 1. Математика. 2. Общие вопросы математики. 3. алгоритмические модели. 4. алгоритмы. 5. машина Тьюринга. 6. машина Поста. 7. машины произвольного доступа (МПД). 8. нормальные алгоритмы Маркова. 9. рекурсивные функции. Description An account of the resource Основные алгоритмические модели [Электронный ресурс] : учебное пособие / Е. Н. Дронова ; Алтайский государственный педагогический университет. — 1 компьютерный файл (pdf; 9.63 MB). — Барнаул : АлтГПУ, 2016. — 158 с. В пособии представлено описание таких алгоритмических моделей, как класс рекурсивных функций, машина Тьюринга, машина Поста, машины произвольного доступа, нормальные алгоритмы Маркова. Особое внимание уделено разработке вычислительных алгоритмов в указанных алгоритмических моделях. Пособие предназначено студентам педагогических вузов, изучающих теорию алгоритмов. Creator An entity primarily responsible for making the resource Дронова, Екатерина Николаевна Source A related resource from which the described resource is derived Алтайский государственный педагогический университет, 2016 Publisher An entity responsible for making the resource available Алтайский государственный педагогический университет Date A point or period of time associated with an event in the lifecycle of the resource 30.03.2016 Rights Information about rights held in and over the resource ©Алтайский государственный педагогический университет, 2016 Format The file format, physical medium, or dimensions of the resource pdf, exe Language A language of the resource русский Type The nature or genre of the resource Учебное пособие Identifier An unambiguous reference to the resource within a given context <a href="http://library.altspu.ru/dc/pdf/dronova.pdf">http://library.altspu.ru/dc/pdf/dronova.pdf</a><br /><a href="http://library.altspu.ru/dc/exe/dronova.exe">http://library.altspu.ru/dc/exe/dronova.exe</a> алгоритмические модели алгоритмы Математика машина Поста машина Тьюринга машины произвольного доступа (МПД) нормальные алгоритмы Маркова Общие вопросы математики рекурсивные функции