Алгоритмические модели и их представление

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ.. 3

ИНТУИТИВНОЕ ПОНЯТИЕ АЛГОРИТМА. НЕОБХОДИМОСТЬ ЕГО УТОЧНЕНИЯ. 4

1.1 Свойства, характерные для интуитивного понятия алгоритма. 6

1.2 История развития понятия алгоритма. 9

1.3 Алгоритмические модели и их представление. 11

1.4 Вычислительные алгоритмы.. 14

МАШИНЫ ТЬЮРИНГА (ОДНОЛЕНТОЧНЫЕ ДЕТЕРМИНИРОВАННЫЕ) 29

2.1 Неформальное описание машины Тьюринга. 29

2.2 Формальное определение машины Тьюринга. 32

2.3 Операции над машинами Тьюринга. 35

2.4 Варианты машины Тьюринга. 38

2.5 Вычислимость по Тьюрингу и разрешимость. 39

ПРОБЛЕМА САМОПРИМЕНИМОСТИ.. 42

3.1. Нумерация алгоритмов. 45

3.2 Нумерация наборов чисел. 46

3.3 Нумерация слов и словарные функции. 47

3.4 Нумерация машин Тьюринга. 48

ЗАКЛЮЧЕНИЕ.. 52

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ.. 53

КОНТРОЛЬНЫЕ ВОПРОСЫ... 54

ТЕСТ.. 56

ВВЕДЕНИЕ

В данной контролируемой самостоятельной работе я изучаю следующие вопросы:

1. Интуитивное понятие алгоритма.

2. Алгоритмические модели и их основные типа

3. Свойства алгоритма

4. Машина Тьюринга

5. Операции и применения машины Тьюринга.

6. Вычислимость по Тьюрингу и разрешимость.

7. Проблема самоприменимости.

8. Нумерация алгоритмов, наборов чисел, слов и машин Тьюринга.

Я для наглядности переместил оглавления сюда, но не надо вам этого делать – просто исправите все в своем оглавлении и заодно во введении, а также везде где надо –

Введение

Интуитивное понятие алгоритма. Необходимость его уточнения

История развития понятия алгоритма

Типовые алгоритмические конструкции и их обозначения

Свойства алгоритма

Алгоритмические модели и их основные типы

Вычислительные алгоритмы

Символьные алгоритмы

Алгоритмы для исполнителей.

Машины Тьюринга (одноленточные детерминированные), функции ими вычислимые

Неформальное описание машины Тьюринга

Формальное определение машины Тьюринга

Операции над машинами Тьюринга

Пример машины Тьюринга

Варианты машины Тьюринга

Вычислимость по Тьюрингу и разрешимость

Проблема самоприменимости

Нумерация алгоритмов

Нумерация наборов чисел

Нумерация слов или словарные функции

Нумерация машин Тьюринга

Заключение

Список использованных источников

Контрольные вопросы

Тест

===уточню, что только заголовки первого уровня начинаются с новой страницы, остальные через одеу-две пустые строки продолжаются далее

1 ИНТУИТИВНОЕ ПОНЯТИЕ АЛГОРИТМА. НЕОБХОДИМОСТЬ ЕГО УТОЧНЕНИЯ[i1] .

Интуитивное понятие алгоритма – одно из основных понятий математики, не допускающее определения в терминах более простых понятий.

Термин «алгоритм» произошел от имени среднеазиатского математика Абу Абдаллы Мухаммеда бен Мусы аль-Маджуси ал-Хорезми (787—ок. 850), который в своих трудах дал точное описание процесса выполнения основных арифметических действий (сложения, умножения, деления) в виде последовательного применения небольшого числа простых правил. Этими правилами мы пользуемся до сих пор при сложении и умножении «столбиком». Эти правила предписывали строгую последовательность действий для получения искомого результата. Так возникло понятие "алгоритм" в честь арабского имени аль-Хорезми. Первое упоминание термина «алгоритм» как системы предписаний для механического исполнения вычислений принадлежит немецкому математику Эрнсту Шредеру (1841—1902[i2] ).

Пусть задано бесконечное множество задач и указано, что понимается под решением каждой из них. Говорят, что существует алгоритм для решения данного бесконечного множества задач, если существует единый способ, позволяющий, для любой задачи этого множества, в конечное число шагов, найти ее решение.

Это не является определением, т.к. выражение «единый», «конечное число шагов» лишены математической точности.

Современная математика и вычислительная практика исходят из следующих наглядных представлений об алгоритмах как процессах обработки данных.

Алгоритм (алгорифм[i3] ) есть система предписаний, определяющая выполнение некоторого процесса над конструктивными (искусственно созданными) объектами.

Алгоритм «перерабатывает» исходные (заданные) конструктивные объекты (КО) в результирующие КО.

Понятие конструктивный объект (КО) [i4] определяется через следующие его свойства:

Идентифицируемость данных. [i5] Каждый КО должен быть идентифицирован (выделен) среди других КО по имени, по координатам или по другим признакам.

Структура данных. [i6] КО может быть изначально задан (элементарный КО) либо создан из совокупности элементарных КО при помощи каких-нибудь операций и даже алгоритмическим путем.

Конечность данных[i7] . Множество элементарных КО (каждый КО в единственном экземпляре) всегда конечно. Такое множество называют алфавитом. Из элементов алфавита может быть образовано бесконечное множество сложных КО.

[i8] Алгоритмический процесс расчленяется на отдельные шаги: каждый шаг состоит в непосредственном преобразовании возникшего к этому шагу состояния в другое последующее состояние. Состояния описываются в виде выбранных КО. Преобразование текущего состояния в последующее производится одной операций из конечного списка операций, специально придуманных для выбранных КО.

Процессор — «кто/что обрабатывает» выполняет действия (операции) по преобразованию состояний, записи и хранению информации о состояниях в специальной памяти. Действия (операции) выполняются по командам, или предписаниям процессору, для чего определяется некоторая дисциплина (порядок) выбора предписаний. Запись предписаний на каком-либо языке и соглашение по порядку их выполнения представляетконкретный[i9] алгоритм. Степень формализации языка предписаний может быть различной.

Не всякий процесс преобразования одного состояния в другое можно назвать алгоритмом. Например, физический процесс преобразования потенциальной энергии падающей воды в электрическую не принято называть алгоритмом. При математическом моделировании мы имеем дело с преобразованием не физических величин, а искусственно созданных КО, в частности, чисел. Процесс преобразования обязательно должен определяться алгоритмом.

Алгоритм [i10] - это заданное на некотором языке конечное предписание, задающее конечную последовательность выполнимых элементарных операций для решения задачи, общее для класса возможных исходных данных.

Варианты словесного определения алгоритма принадлежат российским ученым А.Н. Колмогорову и А.А. Маркову:

– алгоритм [i11] – это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи;

– алгоритм[i12] – это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

Алгоритм[i13] — набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное число действий. В старой трактовке вместо слова «порядок» использовалось слово «последовательность», но по мере развития параллельности в работе компьютеров слово «последовательность» стали заменять более общим словом «порядок». Это связано с тем, что работа каких-то инструкций алгоритма может быть зависима от других инструкций или результатов их работы[i14]

Другие формальные определения понятия алгоритма связаны с введением специальных математических конструкций (машина Поста, машина Тьюринга, рекурсивно-вычислимые функции Черча) и постулированием тезиса об эквивалентности такого формализма и понятия «алгоритм».

Примеры алгоритмов:[i15]

Алгоритмы арифметических действий с числами в двоичной системе счисления;

Алгоритм нахождения НОД (наибольший общий делитель) 2-х целых чисел, 2-х многочленов от переменной х;

Алгоритм извлечения квадратного корня N;

Алгоритм дифференцирования многочлена от переменной;

Алгоритм нахождения определителя квадратной матрицы А;

[i16]

1.1 Свойства, характерные для интуитивного понятия алгоритма[i17]

1. Дискретность. [i18] Это свойство заключается в следующем: в начальный момент задается исходная система величин, а в каждый следующий момент система величин получается из предыдущей системы величин по определенному закону (программе).

2. Детерминированность[i19] . Система величин, получаемых в любой, отличный от начального, момент времени, однозначно определяется системой величин в предшествующие моменты времени.

3. Элементарность шагов[i20] . Закон получения последующей системы величин из предыдущей должен быть простым и локальным.

4. Эффективность (результативность). [i21] Каждый шаг работы алгоритма должен заканчиваться результатом.

5. Массовость алгоритма. [i22] Начальная система величин может выбираться из некоторого бесконечного счетного множества Х.

6. Конструктивность. [i23] Объекты из Х, над которым работает алгоритм, должны быть конструктивными.

Конструктивный объект [i24] – тот, который может быть набран весь целиком и представлен для рассмотрения.

Примерами конструктивных объектов [i25] являются булевы функции, формулы алгебры логики, натуральные и рациональные числа, матрицы с натуральными или рациональными элементами, многочлены от неизвестных с рациональными коэффициентами.

Неконструктивными объектами являются, например, любые действительные числа, представления которых в десятичной записи a₀ a₁…a_n… ни для какого n из натуральных чисел не может быть целиком представлено для рассмотрения. Числа не являются конструктивными объектами[i26] .

Понятно, что понятие алгоритма, описываемое свойствами 1-6, является нестрогим: в формулировке этих свойств встречаются слова, не имеющие точного математического определения. Необходимо также отметить, что, вообще говоря, не предполагается, что процесс применения алгоритма к исходным данным обязательно должен закончиться результатом через конечное число шагов. Процесс может закончиться безрезультатно или не закончиться вообще. В этом случае говорят, что алгоритм неприменим к рассматриваемым исходным данным.

Часто алгоритмическим процессам приписывают ряд свойств с их меньшим количеством и с другим акцентом требований:

1. Детерминированность. [i27] При применении алгоритма к одним и тем же исходным данным всегда должен получаться один и тот же результат.

2. Массовость. [i28] Алгоритм должен служить для решения класса задач, а не для одной конкретной задачи с единственным набором исходных данных. Исходные данные для алгоритма могут представлять достаточно большое или, быть может, бесконечное множество.

3. Результативность алгоритма. [i29] Требуется, чтобы алгоритм, примененный к решению задачи, останавливался через конечное число шагов, и после этой остановки можно было бы прочитать полученный результат. Множество исходных данных, для которых применение алгоритма приводит к останову с получением результата, называется областью применимости алгоритма.

Типовые алгоритмические конструкции[i30]

Для описания алгоритмических конструкций могут быть использованы следующих виды обозначений: логические (словесные), графические (графы и диаграммы), табличные и специальные обозначения.

Для графического изображения основных операций на схеме алгоритма приняты обозначения основных блоков, показанные на рисунке 15.

Последовательное и/или параллельное соединение различных блоков позволяет организовать вычисление любых частично-рекурсивных функций. Общую схему соединения нескольких блоков от “начало” до “конец” называют блок-схемой алгоритма[i31] .

Рисунок 15. - Основные блоки схемы алгоритма

Выделяют также три основных типа алгоритмов[i32] :

· Линейные (следования);

· Разветвляющиеся (развилка);

· Циклические.

Ниже на рисунке 1.1 дан пример описания основных типов алгоритма в виде блок-схемы.

Блок-схема [i33] – это ориентированный граф, вершины которого могут быть одного из ниже представленных базовых типов (всегда должен быть один вход и один выход).

Рисунок 1.1 – Примеры блок-схем

1 схема – функциональная вершина[i34] . Реализуется композитная функция:

F: x --> Y

Алгоритм называется линейным, вычисления называются аддитивными (последовательными).

2 схема – предикатная вершина. [i35] Реализуется предикатная функция (выбор или альтернатива):

P: x - -> (t, f)

Алгоритм называется разветвляющимся, вычисления называются альтернативными.

3 схема – итерационная вершина[i36] . Реализуется итерационная функция:

I: x - -> (Yi, Yi+1)

Алгоритм называется циклическим, вычисления называются повторяющимися (итерационными).

[i37] Структурная блок-схема [i38] – это блок-схема, которая может быть выражена как композиция из трех представленных базовых блоков.

1.2 История развития понятия алгоритма[i39]

В двадцатых годах нашего века задача точного определения понятия алгоритма стала одной из центральных математических проблем. Решение этой проблемы развивалось по двум направлениям.

Первое направление [i40] было основано на точном описании совокупности числовых функций, которые можно вычислять посредством алгоритма, они назывались вычислимыми функциями.

Второе направление [i41] развивало точное описание процессов, которые может совершать достаточно просто устроенная «машина». В 1934 г. Курт Гёдель (1906—1978) описал класс числовых функций, вычислимых в некоторой формальной системе (исчислении). В 1936 г. Алонзо Чёрч (р.[i42] 1903) предложил другую формальную систему, названную им λ-исчислением. В 1936 г. Клини ввел строгое понятие класса рекурсивных (от лат. recurcio —возвращение) функций, которые вычислимы при помощи алгоритмов. Им было доказано совпадение классов вычислимых функций, построенных Геделем и Черчем с классом рекурсивных функций.

В 1936 г. Черч выдвинул гипотезу, которая стала называться тезисом Черча[i43] : «Класс алгоритмически вычислимых числовых функций совпадает с классом рекурсивных функций». Тезис Черча не может быть доказан, так как в нем используется интуитивное (неточное) понятие алгоритма. Однако исследования, проводившиеся математиками в течение последних 50 лет, не смогли опровергнуть тезис, то есть предложить такую числовую функцию, которая была бы с одной стороны, вычислима некоторым интуитивным алгоритмом, а с другой стороны, не была бы представима точным описанием некоторой рекурсивной функции. Все математики считают точное понятие рекурсивной функции научным эквивалентом интуитивного понятия функции, вычислимой алгоритмом.

В 1936 г. английский математик Алан Матисон Тьюринг (1912—1954) предложил точное описание алгоритма в виде некоторой машины — «машины Тьюринга», которая использует конечное множество символов, имеет процессор, выполняющий предписания определенного вида, устройство для хранения входных, промежуточных и выходных результатов. В 1937 г. Тьюринг доказал, что его машина может вычислять совокупность функций, эквивалентную λ-исчислению Черча.

В 1936 г. американский математик Эмиль Леон Пост (1897—1954) независимо от Тьюринга предложил свою конструкцию машины для уточнения понятия алгоритма. Машины Поста и Тьюринга оказались эквивалентными по своим вычислительным возможностям рекурсивным функциям.

В 1951 г. советский математик Андрей Андреевич Марков-сын (1903—1979) предложил принцип нормализации алгоритмов для приведения их к стандартной форме, которая получила название нормального алгорифма Маркова (НАМ).

[i44]

Алгоритмические модели и их представление

[i45] Модель (фр. modèle, от лат. modulus — «мера, аналог, образец») [i46] — это упрощенное представление реального устройства и/или протекающих в нем процессов, явлений.

Построение и исследование моделей, то есть моделирование, облегчает изучение имеющихся в реальном устройстве (процессе, …) свойств и закономерностей. Применяют для нужд познания (созерцания, анализа и синтеза).

Моделировани[i47] е является обязательной частью исследований и разработок, неотъемлемой частью нашей жизни, поскольку сложность любого материального объекта и окружающего его мира бесконечна вследствие неисчерпаемости материи и форм её взаимодействия внутри себя и с внешней средой.

Алгоритмическая модельили модель алгоритмов - это упрощенное представление алгоритма или алгоритмического процесса на основе чего-либо (математической конструкции или гипотетического/реального механизма[i48] )

К алгоритмическим моделям относятся такие модели, в которых критерии и ограничения описываются математическими конструкциями, включающими логические условия, приводящие к разветвлению вычислительного процесса, и так называемые имитационные модели — моделирующие алгоритмы, имитирующие поведение элементов изучаемого объекта и взаимодействие между ними в процессе функционирования.

Следующим признаком, по которому можно различать ЭММ, является связь с фактором времени:

· динамические — модели, в которых входные факторы, а следовательно, и результаты моделирования явно зависят от времени;

· статические — модели, в которых зависимость от времени отсутствует совсем либо проявляется слабо или неявно.

[i49] Понятие "алгоритм" было принято для обозначения совокупности правил вычислительных процессов, в которых искомые результаты практических задач находят последовательно из исходных данных по определенным правилам и инструкциям.

Процесс создания компьютерной программы для решения какой-либо практической задачи включает в себя формализацию этой задачи, разработку вычислительного алгоритма её решения, написание и отладку программы, наконец, решение поставленной задачи.

Основными объектами алгоритма стали данные[i50] . Для уточнения этого понятия фиксируют конечный алфавит символов (цифр, букв и т.п.) и правил построения алгоритмических объектов. Такими объектами вычислительных алгоритмов являются списки и стеки, множества и отображения. Процесс преобразования алгоритмических объектов от исходных данных до искомого результата выполняется дискретно или, как говорят, "по шагам". Преобразование за один шаг носит локальный характер, т.е. этому преобразованию подвергается не весь объект, а лишь его часть: элемент стека или компонента кортежа, столбец или строка матрицы и т.п. Последовательность шагов детерминирована, т.е. после каждого шага указывается точно, что и как следует выполнять на следующем шаге. Процесс преобразования алгоритмического объекта, включающий в себя заданную последовательность шагов, называют алгоритмическим процессом[i51] . Механизм реализации алгоритмического процесса удобнее проследить на алгоритмических моделях, использующих конечные наборы простейших объектов и конечные наборы элементарных действий. Выделяют три основных класса или типа алгоритмических моделей:

1. Вычислительные алгоритмы[i52] . Предполагается, что любые данные можно закодировать числами, а всякое их преобразование становится в этом случае арифметическим вычислением. Алгоритмом в таких моделях является вычисление значения некоторой числовой функции, а его элементарными шагами – арифметические операции. Последовательность шагов определяется способами суперпозиции и рекурсии.

2. Символьные алгоритмы[i53] . Задается алфавит, конечное множество допустимых подстановок и некоторое правило, определяющее порядок применения подстановок (например, нормальный алгоритм Маркова, формальные грамматики).

3. Алгоритмы для исполнителей. [i54] Алгоритм задается последовательностью правил (инструкций), которые может выполнить машина, удовлетворяющая требованиям простоты и универсальности (абстрактные машины Тьюринга и Поста, конечные или магазинные автоматы).

В теории алгоритмов доказана сводимость одного типа модели к другой, т.е. всякий алгоритм, описанный средствами одной модели, может быть описан также средствами другой. Рассмотрим подробнее реализацию алгоритмических процессов для вычисления числовых функций на данных трех типах моделей алгоритмов.

1.4 Вычислительные алгоритмы[i55]

Первый тип модели алгоритма основывается на вычислительных алгоритмах. Выберем в качестве числовой функции рекурсивные функции. Тогда в данном типе алгоритмической модели понятие алгоритма будет связано с элементарными вычислительными операциями на множестве целых положительных чисел.

Напомним, что общее определение рекурсии как процесс повторения элеменубратьто общее определение рекурсии как виде блок-схемы.

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

Рекурсия[i56] здесь есть способ вычисления значения числовой функции по известным значениям независимых переменных аргумента и известному значению функции в некоторой исходной точке. Поэтому любую вычислимую функцию, заданную на множестве натуральных чисел и принимающую значения на том же множестве принято называть рекурсивной функцией. [i57]

Если значения функции найдены не для всех значений области определения, то её называют частично рекурсивной функцией [i58] и, наоборот, если они найдены для всех значений области определения, то её называют общерекурсивной функцией. [i59]

Для формального построения функций вычислимых алгоритмом необходимо иметь:

1) набор элементарных функций, которые изначально считаются вычислимыми;

2) набор элементарных операций над функциями, при помощи которых можно строить более сложные вычислимые функции.

Для формирования механизма вычисления рекурсивных функций даны наборы простейших базовых функций[i60] : константы, тождества и следования и наборы элементарных операций[i61] : суперпозиции, рекурсии, минимизации и итерации.

Рекурсивная функция — это числовая функция f(n) числового аргумента, которая в своей записи содержит себя же. Такая запись позволяет вычислять значения f(n) на основе значений f(n-1),f(n-2),…, подобно рассуждению по индукции. Чтобы вычисление завершалось для любого n, необходимо, чтобы для некоторых n функция была определена нерекурсивно (например, для n=0,1). Этот вид функций определен на множестве натуральных чисел — N (точнее N и 0).

Примитивно рекурсивная функция - определение является индуктивным. Оно состоит из указания класса базовых примитивно рекурсивных функций и двух операторов (суперпозиции и примитивной рекурсии), позволяющих строить новые примитивно рекурсивные функции на основе уже имеющихся.

К числу базовых примитивно рекурсивных функций относятся функции следующих трёх видов:

Функция константа. Если f={(x₁, x₂,..., x_n, у)| x_i N, y N}=C_n или y = f(x₁, x₂,…x_n)=C_n, то любым значениям независимых переменных аргумента функции ставится в соответствие значение функции, равное постоянной величине (константе) - С_n, где n –число независимых переменных аргумента. Чаще всего C_n=0. Поэтому её называют также нуль-функцией. Например, если f={(x₁, x₂, x₃, у)}=C₃, то для x1 = 5, x₂ = 4, x₃ = 7 и C₃ = 0 имеем у=f(5, 4, 7)=0 или, если С_n=1 при тех же значениях независимых переменных, то y=f(5, 4, 7)=1.

Функция следования. Если f={(x, у)| x_i N, y N}=λ(x), то любому значению независимой переменной аргумента ставится в соответствие значение функции, равное числу, непосредственно следующему за числом, являющимся значением независимой переменной. Например, если для f={(x, у)}=λ(x) дано x = 5, то у = (5+1) = 6, если для f={(x, у)}=λ(x) дано x = 7, то у = (7+1) = 8.

Функция тождества. Если f={(x₁, x₂,..., x_n, у)| x_i N, y N}= , то любым значениям независимых переменных аргумента функции ставится в соответствие ее значение, равное значению m-го независимого переменного аргумента, где 1≤m≤n – место независимого переменного аргумента в их упорядоченном списке. Поэтому её называют также функцией выбора аргумента. Например, если f={(x₁, x₂, x₃, у)}=I₃² , то для x1 = 5, x2 = 4, x3 = 7 [i62] имеем у = 4, если f={(x₁, x₂, x₃, у)}=I₃³ , то для x₁ = 5, x₂ = 4, x₃ = 7 имеем у = 7.

Операции, с помощью которых из простейших базовых функций могут быть получены различные рекурсивные функции, называют элементарными. [i63]

В данном случае это операторы[i63] подстановки и примитивной рекурсии. Они определяются следующим образом:

Оператор суперпозиции (иногда — оператор подстановки). Пусть — функция от m[i64] переменных, а — упорядоченный набор функций от переменных каждая. Тогда результатом суперпозиции функций в функцию называется функция от переменных, сопоставляющая любому упорядоченному набору натуральных чисел число

.

Оператор примитивной рекурсии. Пусть — функция от n переменных, а — функция от переменных. Тогда результатом применения оператора примитивной рекурсии к паре функций и называется функция от переменной вида

; .

В данном определении переменную можно понимать как счётчик итераций, — как исходную функцию в начале итерационного процесса, выдающего некую последовательность функций переменных, начинающуюся с , и — как оператор, принимающий на вход переменных , номер шага итерации , функцию на данном шаге итерации, и возвращающий функцию на следующем шаге итерации.

Множество примитивно рекурсивных функций — это минимальное множество, содержащее все базовые функции и замкнутое относительно указанных операторов подстановки и примитивной рекурсии.

Таким образом, из элементарных функций С_n, I_n^m и λ(x +1) с помощью операторов суперпозиции и примитивной рекурсии были получены основные функции арифметики, алгебры и анализа. Тем самым было показано, что эти функции имеют примитивно рекурсивное описание, которое однозначно определяет процедуру их вычисления.

Последовательность рекурсивного описания, использующая базовые функции и результаты вычисления функции на всех предшествующих точках с помощью операторов суперпозиции и примитивной рекурсии, называют протоколом[i65] .

Частично рекурсивная функция - определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции и примитивной рекурсии добавляется ещё третий оператор — минимизации аргумента.

Оператор минимизации аргументаили поиск наименьшего корня. Пусть — функция от n натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции называется функция от переменной, задаваемая следующим определением:

, при условии ,

то есть функция возвращает минимальное значение последнего аргумента функции , при котором её значение равно 0.

Операция минимизации решает элементарную поисковую задачу[i66] : 1) есть функция последовательного порождения значений для y; 2) есть предикат P, истинность которого проверяется. На каждый акт порождения производится проверка предиката. Процесс заканчивается, когда P истина.

При помощи частично-рекурсивных функций можно описать все арифметические операции и организовать вычисление.

Тезис А. Чёрча: Любая интуитивно вычислимая функция является частично-рекурсивной.

Тезис А.Тьюринга: любая интуитивно вычислимая функция является вычислимой по Тьюрингу.

Эти два тезиса являются эквивалентными.

Функции, которые могут быть получены из простейших , λ(x +1), применением конечного числа раз операторов суперпозиции, примитивной рекурсии и минимизации, называются рекурсивными.[i67]

Класс рекурсивных функций шире класса примитивно рекурсивных функций хотя бы по тому, что он содержит не только всюду определенные функции. Докажем, например, что функция

является[i68] рекурсивной. Действительно, , а ранее было установлено, что функция примитивно рекурсивна.

Операция итерации. Многократное повторение данного процесса, пока не будет выполнено некоторое условие, называют итерацией[i69] . При этом на каждом шаге итерации данный процесс выполняется полностью. Условием итерации, как правило, является число повторений рекурсивной функции.

Итак, функция называется примитивно рекурсивной[i70] , если она получена из базовых функций с помощью конечного числа операторов суперпозиции и/или примитивной рекурсии. Она же называется рекурсивной[i71] , если получена с помощью примитивно рекурсивных функций и конечного числа операторов суперпозиции, примитивной рекурсии и/или минимизации. Иначе говорят так: функции, для которых существуют алгоритмы вычисления, называют рекурсивными функциями[i72] . Рекурсивная функция называется частично рекурсивной[i73] , если она определена не на всем множестве целых положительных чисел и общерекурсивной[i74] , если она определена на всем множестве целых положительных чисел.

Рекурсивные функции отражают наше интуитивное представление о функциях, вычислимых некоторым механическим устройством. В частности, они вычислимы на машинах Тьюринга. Наоборот, всякая функция, вычислимая на машине Тьюринга является рекурсивной.

Общерекурсивная функция — частично рекурсивная функция, определённая для всех значений аргументов. Задача определения того, является ли частично рекурсивная функция с данным описанием общерекурсивной или нет, алгоритмически неразрешима.

1.5 Алгоритмы[i74] для исполнителей[i75]

Третий тип модели алгоритма основывается на так называемых алгоритмах[i75] для исполнителей. Его абстрактной реализацией выбирают часто машину Тьюринга. Она связывает понятие алгоритма с механическим устройством, способным выполнять строго фиксированное множество элементарных действий над простейшими символами; [i76]

Машина Тьюринга (МТ) [i77] - это абстрактная машина (автомат), работающая с лентой отдельных ячеек, в которых записаны символы. Машина также имеет головку для записи и чтения символов из ячеек, которая может двигаться вдоль ленты. На каждом шагу машина считывает символ из ячейки, на которую указывает головка, и, на основе считанного символа и внутреннего состояния, делает следующий шаг. При этом, машина может изменить свое состояние, записать другой символ в ячейку или передвинуть головку на одну ячейку вправо или влево. Подробно МТ будет рассмотрена в следующей главе. Здесь напомним частные её реализации в виде машины Поста и автоматов (конечных, магазинных и других).

В 1936 г. Эмиль Леон Пост (Emil L. Post) опубликовал статью «Финитные комбинаторные процессы — формулировка 1», в которой было дано одно из первых уточнений понятия алгоритма. Им была предложена конструкция в виде абстрактной машины, которая выполняла очень простые операции, имитирующие действия человека. Пост сам был удивлен тем, что машина могла вычислять очень сложные функции, если их удавалось изложить на «языке» машины. Конструкция Поста положила начало целому «машинному ряду» уточнений алгоритма, насчитывающему к настоящему времени около сотни абстрактных машин[i78] .

1. Конструкция машины Поста. [i79] Машина Поста содержит следующие составные части (смотри рисунок. 3.2):

а) бесконечную входную ленту, разделенную на клетки, которая служит для записи информации; каждая клетка может быть в двух состояниях: ◊ — пустая, * — записан символ «*» (иногда используют другие символы);

б) головку считывания/записи (Г), которая может передвигаться вдоль ленты на одну клетку влево или вправо, стирать клетку (ставить ◊), записывать символ «*».

2. Работа машины. [i80] Работа машины состоит в том, что головка передвигается вдоль ленты и записывает или стирает символы. Работа производится по инструкции — программе, состоящей из отдельных команд.

3. Команды машины[i81] . Формат команд приведен в таблице 1.

4. Процесс выполнения. [i82] Он начинается с первой команды программы, на каждом шаге производится действие и переход к команде, которая должна выполняться следующей.

Текущее состояние машины Поста описывается состоянием ленты и положением каретки. Состояние ленты – информация о том, какие секции пусты, а какие отмечены. Шаг – это движение каретки на одну ячейку влево или вправо. Состояние ленты может изменяться в процессе выполнения программы. Входные данные записываются на ленте, результат получается на ленте при останове машины. У команды «стоп» отсылки нет.

Варианты окончания выполнения программы на машине Поста:

Команда "стоп" [i83] - корректная остановка. Возникает в результате выполнения правильно написанного алгоритма.

Выполнение недопустимой команды [i84] – нерезультативная остановка. Случаи, когда головка должна записать метку там, где она уже есть, или стереть метку там, где ее нет, являются аварийными (недопустимыми).

Уход в бесконечность, зацикливание. [i85] Машина Поста в результате работы алгоритма может вообще не остановиться (никогда не дойти до команды «стоп» и никогда не завершиться аварийной ситуацией).

[i86] Элементарные действия (команды) машина Поста проще команд машины Тьюринга. Поэтому программы для машины Поста имеют большее число команд, чем аналогичные программы для машины Тьюринга. Почему достаточно лишь два различных символа (есть метка, нет метки)? Дело в том, что любой алфавит может быть закодирован двумя знаками; в зависимости от алфавита возрастать может только количество двоичных символов в букве алфавита.

Машина Поста является прародителем всех процедурных языков программирования.

Таблица 1.

Рисунок 3.2

Как было указано ранее, реализация распознающей грамматики находит свое воплощение в автоматах, которые входят в рассматриваемый тип алгоритмической модели. Так конечный автомат (КА) может решать следующую задачу. Пусть задан алфавит A={,a,b,*}и пусть задано отношение L— множество слов вида ambn *для m,n=1,2,...то есть L={ ambn *} Пусть x— произвольное слово в A. Надо построить функцию (предикат) такую, что f(x) =1 или 0, если x или ∉ L. Здесь символ «*» — признак конца слова[i87] . Построим следующий «механизм» или КА: [i88]

Механизм может находиться в некоторых состояниях S_y, в том числе: начальное — S_s и конечные — S_e , при получении на входе какого-либо символа механизм переходит в другое состояние и, если оно не конечное S_e, то он может воспринимать следующий символ. Записывают конечный автомат в виде команды, графа или таблицы.

Рассматривается еще одна автоматная конструкция —так называемый магазинный (стековый) автомат (МА). У МА имеется:

1. Входная лента E, разделенная на ячейки и потенциально неограниченная в обе стороны.

2. Рабочая лента (лента магазинной памяти, или стек) M, также разделенная на ячейки и ограниченная с одной стороны (например, слева), но потенциально неограниченная с другой.

3. Управляющее устройство A с двумя головками:

— входная головка (головка чтения), читающая символы на входной ленте E;

— рабочая головка, читающая, стирающая и записывающая символы на рабочей ленте M.

Каждая головка может передвигать свою ленту по определенным правилам, которые будут уточнены.

Входная лента. [i89] До начала работы МА на входной ленте записана некоторая информация — по одному символу в каждой ячейке. Для записи ее используется входной словарь (входной алфавит):

V E [i90] ={a₁,a₂,...,a_p}. Цепочки (слова), составленные из символов входного алфавита, записываются на ленте E слева направо так, что слова и справа остаются пробелы, обозначаемые символом B.

Рабочая лента. [i91] Запись на рабочей ленте производится самим автоматом с помощью рабочего словаря (рабочего алфавита):

VM[i92] ={ А₁,A₂,..., A_q}. Алфавит VM[i93] может включать в себя и алфавит AE[i94] [i95] . Изначально в самой левой ячейке записан специальный символ ◊ — «доннышко».

Управляющее устройство. [i96] Управляющее устройство способно принимать конечное число внутренних состояний S₀,S₁,...,S_n, то есть задан алфавит внутренних состояний:

VS[i97] ={ S₀,S₁,...,S_n}. Первое из них (S₀)считается начальным, последнее (S_n) — конечным.

Функционирование МА[i98] . В каждый момент времени МА находится в некоторой ситуации, которая описывается тройкой:

< a_I[i99] , S_j, A_k,>, где a_i—символ, записанный на ленте E и обозреваемый в данный момент входной головкой, S_j — внутренее[i100] состояние управляющего устройства, A_k—символ, записанный на ленте M и обозреваемый в данный момент рабочей головкой.

Командой МА [i101] называется запись вида: <ситуация>→< S_m,x>, где ситуация определена выше, S_m - внутренее[i102] состояние, x—действие с рабочей лентой.

Абстрактным МА [i103] называется конечное множество команд указанного вида.

1.6 Символьные алгоритмы[i104]

Второй тип модели алгоритма основывается на символьных алгоритмах. В частности, сюда также можно отнести формальные грамматики. Однако сначала рассмотрим стандартного представителя данного типа алгоритмической модели – нормальный алгоритм Маркова (НАМ). [i105] Он связывает понятие алгоритма с элементарными преобразованиями слов произвольного алфавита, замещая части или всего слова другим словом. Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах.

Одним из уточнений понятия алгоритма является НАМ, введенный советским математиком А. А. Марковым. НАМ работает над конструктивными объектами [i106] — словами (цепочками символов), построенными из букв конечного алфавита. Принцип нормализации[i107] , предложенный А. А. Марковым, гласит:

а) объекты любой природы могут быть представлены (закодированы) словами в подходящем алфавите;

б) сколь угодно сложный процесс преобразования слов может быть представлен в виде НАМ.

Определение всякого нормального алгоритма состоит из двух частей[i108] : определения алфавита алгоритма V_t (к словам из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма [i109] называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки [i110] называются слова вида , где и — два произвольных слова в алфавите алгоритма (называемые, соответственно, левой и правой частями формулы подстановки). Аналогично, заключительными формулами подстановки[i111] называются слова вида , где и — два произвольных слова в алфавите алгоритма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгоритма V_t (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).

Для организации последовательного и упорядоченного просмотра формул или правил они должны быть индексированы i {1, 2, 3,...}.

Если слово Р_i есть цепочка вида (γ1[i112] αI[i113] γ2[i114] ) в алфавите Vт[i115] , где γ1[i116] и γ2[i117] – слова в этом же алфавите и среди множества правил первым в упорядоченном списке есть правило α_I→β_I[i118] , то нужно выполнить подстановку (γ₁α_iγ₂) → (γ₁β_i γ₂).

Суть упорядоченного использования правил состоит в том, что каждое переработанное слово вновь поступает в «начало» алгоритма и вновь проверяется на подстановку правил в соответствии с протоколом.

Среди множества правил выделяют заключительное αi[i119] → • β i[i120] , результатом подстановки которого формируется слово Q и дается указание об окончании работы алгоритма.

Процесс может оборваться на некотором слове Р_i, для которого нет соответствующего правил. Тогда это слово направляется в «тупик».

Для того чтобы построить модель алгоритма, необходимо выделить упорядоченную последовательность левых частей правил подстановки, так называемых распознавателей вхождения слов α_i в слово P_i, и множество соответствующих операторов подстановки слова β_I[i121] в слово P_i+1.

На схеме алгоритма (смотри Рисунок 1.2) эти блоки обозначены так:

• распознаватели вхождения - PB_i ;

• операторы подстановки - ОП_i.

Распознаватели вхождения соединяются последовательно в соответствии с заданной последовательностью правил. Второй выход распознавателя вхождения при обнаружении α_i в слове Р_i передает информацию о слове P_i=γ₁α_iγ₂ в ОП_i, где выполняется соответствующая замена слова α_i на слово β_i, т. е. γ₁α_iγ₂[i122] ⇒ γ₁β_iγ₂=P_i+1.

Оператор подстановки направляет слово P_i+1 в «начало» алгоритма, если применена простая подстановка, и в «конец» алгоритма, если применена заключительная подстановка.

Рисунок 1.2 – Схема нормального алгоритма Маркова

Примером схемы нормального алгоритма в пятибуквенном алфавите может служить схема

Процесс применения нормального алгоритма к произвольному слову в алфавите этого алгоритма представляет собой дискретную последовательность элементарных шагов, состоящих в следующем. Пусть — слово, полученное на предыдущем шаге работы алгоритма (или исходное слово , если текущий шаг является первым). Если среди формул подстановки нет такой, левая часть которой входила бы в , то работа алгоритма считается завершённой, и результатом этой работы считается слово . Иначе среди формул подстановки, левая часть которых входит в , выбирается самая первая. Если эта формула подстановки имеет вид , то из всех возможных представлений слова в виде выбирается такое, при котором — самое короткое, после чего работа алгоритма считается завершённой с результатом . Если же эта формула подстановки имеет вид , то из всех возможных представлений слова в виде выбирается такое, при котором — самое короткое, после чего слово считается результатом текущего шага, подлежащим дальнейшей переработке на следующем шаге.

Например, в ходе процесса применения алгоритма с указанной выше схемой к слову последовательно возникают слова , , , , , , , , , и , после чего алгоритм завершает работу с результатом .

Любой нормальный алгоритм эквивалентен некоторой машине Тьюринга, и наоборот — любая машина Тьюринга эквивалентна некоторому нормальному алгоритму. Вариант тезиса Чёрча — Тьюринга, сформулированный применительно к нормальным алгоритмам, принято называть «принципом нормализации».

Нормальные алгоритмы оказались удобным средством для построения многих разделов конструктивной математики. Кроме того, заложенные в определении нормального алгоритма идеи используются в ряде ориентированных на обработку символьной информации языков программирования — например, в языке Рефал.

На основе НАМ развивается одно из самых мощных и современных направлений в программировании — продукционное программирование[i123] .

Формальная[i124] грамматика или просто грамматика в теории формальных языков — способ описания формального языка, то есть выделения некоторого подмножества из множества всех слов некоторого конечного алфавита. Различают порождающие и распознающие (или аналитические) грамматики[i125] — первые задают правила, с помощью которых можно построить любое слово языка, а вторые позволяют по данному слову определить, входит оно в язык или нет. В рассматриваемый алгоритмический тип отнесем порождающие грамматики. Распознающие грамматики будут являться представителями следующего типа алгоритмов, к которому мы и перейдем.