Маркин П.М. Математическая логика

Подождите немного. Документ загружается.

Основное понятие этой теории – алгоритм – в интуитивном (наивном)

понимании существует в математике довольно давно, а точные

математические понятия, которые в том или ином смысле формализуют

интуитивное понятие алгоритма, предложены только в середине 30-х годов

20-го века. Необходимость такой формализации была обусловлена как

вопросами обоснование математики, так и вопросами доказательства

алгоритмической разрешимости тех или иных задач. Очевидно, что в

математике доказываемый объект должен быть точно определен.

В настоящее время теорию алгоритмов делят на дискретивную

(абстрактную) и метрическую (количественную). Первая исследует

алгоритмы с точки зрения устанавливаемого ими соответствия между

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

построения алгоритма, обладающего теми или иными свойствами, -

алгоритмические (массовые) проблемы (т.е. нахождение единого метода

решения бесконечной серии однотипных единичных задач) . Вторая

исследует алгоритмы с точки зрения сложности как самих алгоритмов, так и

задаваемых ими вычислений, т.е. процессов последовательного

преобразования конструктивных объектов. Важно подчеркнуть, что как

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

различными способами. Разработка методов оценки сложности алгоритмов и

вычислений имеет важное теоретическое и практическое значение, а сам

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

которые и определяют три основных класса этих моделей: арифметизация

алгоритмов, концепция абстрактной машины, принцип нормализации (т.е.

преобразование слов в произвольных алфавитах с помощью подстановок).

Замечание:

Абстрактная дискретивная теория алгоритмов не учит строить конкретные

алгоритмы. Этим занимается прикладная метрическая (количественная)

теория алгоритмов. В отличие от абстрактной теории алгоритмов прикладная

теория рассматривает не только детерминированные, но также

вероятностные (стохастические) и эвристические алгоритмы. В последнем

случае, кроме детерминированных или статически заданных правил,

алгоритм включает также содержательные указания о целесообразности

направления процесса.

Предмет и содержание читаемого курса.

Предметом изучения в читаемом курсе являются формальные уточнения

интуитивного понятия «алгоритм» с точки зрения арифметизации,

нормализации и построения абстрактной машины. Целью читаемой

дисциплины студентам специальности 2201 является усвоение

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

решения вопроса о существовании алгоритма для решения данной

бесконечной серии однотипных задач и нахождение такого алгоритма в

случае, если он существует.

Содержанием курса являются следующие вопросы:

- языки операндов и алгоритмические языки;

- рекурсивные функции как математический вариант уточнения понятия

вычислимой арифметической функции;

- машины Тьюринга как математический эквивалент для общего

интуитивного представления об алгоритме;

- нормальный алгоритм Маркова;

- сложность алгоритма.

Интуитивное (наивное) понятие алгоритма как основное первичное

понятие математики.

Алгоритм – точное предписание для свершения некоторой

последовательности элементарных дискретных действий над исходными

данными любой задачи из некоторого класса (вообще бесконечного)

однотипных задач, в результате выполнения которой получится решение

этой задачи.

Иначе: Конечный кортеж правил, обладающих свойствами массовости

(инвариантность относительно входной информации – это так называемое

уточнение понятия – решение задачи в общем виде),

детерминированности (получение после применения этих правил

информации, являющейся результатом) и элементарности (отсутствует

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

на конечном множестве шагов решаемой задачи.

Примеры:

1) «Проезд запрещен», «Не курить» - не алгоритмы;

2) «Придерживайтесь правой стороны», «Место для курения», «Вход» -

не алгоритмы;

3) Сложение (умножение, вычитание, деление) двух чисел (т.е.

) столбиком – алгоритм.

Пример:

Упорядочить в порядке возрастания конечное множество М

положительных чисел. Описание решения этой задачи может быть:

Шаг 1: В М ищется наименьшее число

Шаг 2: Найденное число приписывается справа к возрастающей

последовательности чисел R (в начальный момент R пусто) и

вычеркивается из М;

Шаг 3: Если в М не осталось чисел, то перейти к шагу 4, в противном

случае перейти к шагу 1;

Шаг 4: Конец. Результатом считать последовательность R, построенную к

данному моменту.

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

Действительно, если М=

5,

2, (1/3)



, то в предложенном варианте

решения поставленной задачи не указано, как искать наименьшее число.

Этот пример показывает, что понятие алгоритма в интуитивном смысле

требует уточнения понятия данных (т.е. указать каким требованиям

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

работать), памяти, дискретности, элементарности, конечности числа

шагов, направленности, детерминированности, результативности,

массовости.

Пояснения:

1) Приведенное наивное (интуитивное) определение алгоритма не

является точным математическим определением, а лишь объясняет

смысл слова «алгоритм», в котором это слово используется в

математике.

2) Характеристиками алгоритма являются:

- детерминированность (определенность) – однозначность результата

процесса при заданных исходных данных;

- дискретность – расчлененность процесса на отдельные элементарные

акты (шаги, действия), возможность выполнения которых человеком

или машиной не вызывает сомнений,

- массовость – исходные данные для алгоритма можно выбирать из

некоторого множества данных (потенциально бесконечного), т.е.

алгоритм должен обеспечить решение любой задачи из класса

однотипных задач.

Основные требования к алгоритмам.

1) Очевидно, что каждый алгоритм имеет дело с данными: входными,

выходными и промежуточными. В этом плане уточнение понятия

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

требованиям должны удовлетворять объекты, чтобы алгоритмы могли

с ними работать. Ясно, что эти объекты должны быть четко

определены и отличимы как друг от друга, так и от «необъектов». В

теории алгоритмов четкая определенность объектов обусловлена

заданием их в формальном языке L=<A,S>, в котором символы

конечного алфавита А рассматриваются как элементарные объекты

для построения более сложных объектов конечными средствами S

(этот язык часто называется языком операндов в отличие от языка

описания самого алгоритма – алгоритмического языка).

2) В дальнейшем будем различать:

- описание алгоритма (т.е. инструкции или программы);

- механизм реализации алгоритма (это может быть процессор),

включающий средства пуска, остановки, реализации

элементарных шагов, выдачи результатов и обеспечения

детерминированности процесса в управлении ходом вычислений;

- память данных алгоритма;

- процесс реализации алгоритма, то есть последовательность

шагов (действий), которая будет порождена при применении

алгоритма к конечным данным.

Пояснения:

1) Предположим, что описание алгоритма и механизма его реализации

конечны, а память данных алгоритма может быть и бесконечной.

Конечность процесса реализации алгоритма означает его

результативность (сходимость), то есть остановки алгоритма после

конечного числа шагов (зависящего от данных) с указанием того, что

считать результатом.

2) Предполагается также, что память данных алгоритма однородна и

дискретна, то есть состоит из одинаковых ячеек, каждая из которых

может содержать только один символ алфавита данных. Вопрос о том,

нужна ли одна память или несколько может решаться по-разному.

3) Понятие задачи «в общем виде» уточняется при помощи понятия

«массовая алгоритмическая проблема». Последняя задается серией

отдельных единичных проблем и состоит в требовании найти единый

алгоритм их решения (когда такого алгоритма не существует говорят,

что рассматриваемая массовая алгоритмическая проблема

неразрешима). Так, проблема численного решения уравнений данного

типа и проблема автоматического перевода есть массовые

алгоритмические проблемы: образующими их единичными

проблемами являются в 1-м случае проблемы численного решения

уравнений данного типа, а во 2-м случае - проблемы перевода

отдельных фраз.

4) Алгоритмический процесс – есть процесс последовательного

преобразование конструктивных объектов, происходящий

дискретными шагами; каждый шаг состоит в смене одного

конструктивного объекта другим. Так, при применении алгоритма

вычисления (f: D

 D) столбиком к паре <507, 38> последовательно

возникают конструктивные объекты:

_507 _507 _507 _507

38 38 38

469

Здесь возможными исходными данными служат пары чисел, возможными

результатами – числа (все в десятичной системе счисления), а возможные

промежуточные результаты суть трехэтажные записи вида , где q-

запись числа в десятичной системе, z- такая же запись или пустое слово, а

p- запись числа в десятичной системе с допущением точек над

некоторыми цифрами (точка означает заимствование из старшего

разряда).

Основная терминология теории алгоритмов.

Областью применимости алгоритма называется совокупность тех

объектов к которым он применим. Про алгоритм U говорят, что он:

1) «Выявляет функцию f», коль скоро его область применимости

совпадает с областью определения f, и U перерабатывает всякий х из

своей области применимости в f(x);

2) «Разрешает множество А относительно множества Х», коль скоро он

применим ко всякому х из Х и перерабатывает х из ХА в слово «да»,

а всякий х из Х\А в слово «нет»;

3) «Перечисляет множество В», коль скоро его область применимости

есть натуральный ряд, а совокупность результатов есть В.

Функция называется вычислимой, если существует вычисляющий ее

алгоритм. Множество называется разрешимым (рекурсивным)

относительно Х, если существует разрешающий его относительно Х

алгоритм. Множество называется перечислимым (рекурсивно-

перечислимым), если либо оно пусто, либо существует перечисляющий

его алгоритм.

Замечания:

1) Область возможных переходных данных и область применимости

любого алгоритма суть перечислимые множества;

2) Для любой пары вложенных одно в другое перечислимых множеств

можно подобрать алгоритм, у которого большее множество служит

областью возможных исходных данных, а меньшее областью

применимости.

3) Разрешимые и перечислимые множества являются множествами,

строение которых задается с помощью тех или иных алгоритмических

процедур.

4) Процесс выполнения алгоритма называется алгоритмическим

процессом.

Основные теоремы теории алгоритмов.

Теорема 1: Функция f вычислима тогда и только тогда, когда перечислим

ее график, то есть множество всех пар вида <x, f(x)>.

Теорема 2: Подмножество А перечислимого множества Х разрешимо

относительно Х тогда и только тогда, когда А и Х\А перечислимы.

Теорема 3: Если А и В перечислимы, то АВ и АВ также перечислимы.

Теорема 4: В каждом бесконечном перечислимом множестве Х существует

перечислимое подмножество с неперечислимым дополнением ( в силу

теоремы 2 это перечислимое подмножество будет неразрешимым

относительно Х).

Теорема 5: Для каждого бесконечного перечислимого множества Х

существует вычислимая функция, определннная на подмножестве этого

множества и не продолжаемая до вычислимой функции, определенной на

всем Х.

Параметры алгоритма.

Как правило, для данного алгоритма можно выделить семь независимых

характеризующих его параметров:

1) совокупность возможных исходных данных;

2) совокупность возможных результатов;

3) совокупность возможных промежуточных результатов;

4) правило начала;

5) правило непосредственной переработки;

6) правило окончания;

7) правило извлечения результата;

Основная гипотеза теории алгоритмов.

Любая практическая задача, приводящая к необходимости создания

эффективного вычислительного метода (алгоритма), может быть поставлена

в точных математических терминах.

Алгоритмические (формальные математические) модели.

Приведенное выше «наивное» (интуитивное) понятие алгоритма как

первичное (исходное) понятие математики не допускает его определения в

терминах более простых понятий. Возможные уточнения понятия алгоритма

приводят, строго говоря, к известному сужению этого понятия. Каждое такое

уточнение состоит в том, что для каждого из семи параметров алгоритма

точно описывается некоторый класс, в пределах которого этот параметр

может меняться. Выбор таких классов и отличает одно уточнение от другого.

Поскольку семь параметров однозначно определяют некоторый алгоритм, то

выбор семи классов изменения этих параметров определяет некоторый класс

алгоритма.

В настоящее время среди математических моделей алгоритмов описанного

типа наиболее известными являются уточнения, предложенные

А.М.Тьюрингом (модель абстрактной вычислительной машины),

А.А.Марковым (нормальные алгоритмы), А.Черчем (вычислительные

функции).

Так, понятие машины Тьюринга как F S

следующим образом может быть

использовано для уточнения общего представления об алгоритме в данном

алфавите, если Тьюринговским алгоритмом в алфавите А называется всякий

алгоритм U следующего вида:

- фиксируется некоторая машина Тьюринга в алфавите А, то есть

<A, Q, R>, здесь Q – множество внутренних состояний машины,

а R – правило перехода из одной конфигурации машины к

другой);

- задается  - слово, принимаемое в качестве исходного данного

для U (A

);

- строится исходная конфигурация машины a

a

, где q

–

начальное состояние машины q

Q, a

– пустой символ, a

А;

- машина, отправляясь из a

a

, заканчивает работу в

заключительной конфигурации.

Считается, что для всякого алгоритма U в каком-либо алфавите может быть

построен тьюринговский алгоритм, дающий при одинаковых исходных

данных те же самые результаты, что и алгоритм U. Это соглашение в теории

алгоритмов известно как тезис Тьюринга: «Всякий алгоритм может быть

реализован машиной Тьюринга».

Замечания:

1) Доказать тезис Тьюринга нельзя, поскольку само понятие алгоритма

(или эффективной процедуры) является неточным. Это не теорема и не

постулат, а утверждение, которое связывает теорию с теми объектами,

для которых она создана. По своему характеру тезис Тьюринга

напоминает гипотезы физики об адекватности математических моделей

физическим явлениям и процессам. Подтверждением правильности

тезиса Тьюринга является математическая практика, а также

эквивалентные тезисы и, в частности, тезис Черча для рекурсивных

функций: «Всякая функция, вычислимая некоторым алгоритмом,

частично-рекурсивная».

2) Из сопоставления двух вышеприведенных тезисов вытекает

утверждение: «Функция вычислима машиной Тьюринга тогда и только

тогда, когда она частично-рекурсивна». Это утверждение об

эквивалентности двух алгоритмических моделей является (в отличие от

тезисов) вполне точным математическим утверждением и,

следовательно, доказуемо, то есть имеют место две теоремы:

Теорема 1: Всякая частично-рекурсивная функция вычислима на машине

Тьюринга.

Теорема 2: Всякая функция, вычислимая на машине Тьюринга частично-

рекурсивная.

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

неточность утверждения о существовании эффективных процедур

(алгоритмов) точными утверждениями о существовании

соответствующей алгоритмической модели (например, машины

Тьюринга), а с другой стороны, утверждения о несуществовании таких

моделей истолковывать как утверждения о несуществовании алгоритма

вообще.

4) Тезисы позволяют выставлять случаи невозможности алгоритмов,

однако, не позволяют в случае существования пути построения

удобного для практики алгоритма (Напоминание: «Теория алгоритмов

не учит строить конкретные алгоритмы»).

Блок-схемы алгоритмов.

Связи между шагами алгоритма можно изобразить в виде графа (блок-

схемы) такого, как, например, следующий:

где вершинам соответствуют шаги (блоки), а ребрам – переходы между

шагами. Его вершины могут быть двух видов – операторы (из этих вершин

выходит одно ребро) и предикаты (или логические условия; из этих вершин

выходят два ребра). Кроме того, выделяют операторы начала и конца

алгоритма.

В подобных схемах шаги могут быть элементарными или могут

представлять собой самостоятельные алгоритмы (блоки).

На блок-схеме хорошо видна разница между описанием алгоритма и

процессом его реализации.

Описание – это граф; процесс реализации – это путь в графе. Различные

пути в одном и том же графе возникают при различных данных, которые

создают разные логические условия в точках разветвления.

Отсутствие сходимости означает, что в процессе вычисления не появляются

условий, ведущих к концу, и процесс идет по бесконечному пути

(зацикливается).

Отметим, что блок-схема отражает связи по управлению (что делать в

следующий момент, то есть какому блоку передать управление), а не по

информации (где этому блоку брать исходные данные).

Очевидно, что блок-схемы являются средством описания детерминизма

алгоритма.

Замечания:

1) На практике блок-схемы часть имеют точки разветвления не только

двоичными, но и многозначными, важно лишь, чтобы верным был

ровно один из возможных ответов.

2) Блок схема вида:

Ввес

ти

Шаг 1

Шаг 2

Шаг 3

Выве

сти

Ввес

ти

Выве

сти

Управляемая головка

записи-считывания

символа внешней памяти

Внутренняя память состоянеий

(инструкций Q и перемещений D)

Блок управления

БУ

Цепь

О.С.

Ячейки внешней памяти для записи-считывания символов внешнего

алфавита А

Канал

воспроизведения

(считывания)

К шаговому приводу

перемещения

управляемой головки

(или ленты)

где блок А

вычисляют функцию f

(x), а исходными данными для А

являются результаты А

, называется композицией алгоритмов А

и А

(то есть

блок-схема задает алгоритм, вычисляющий f

(x)), то есть композицию f

)

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

Машина Тьюринга Т – название, закрепившееся за вычислительными

абстрактными машинами некоторого точно охарактеризованного типа.

Машину Тьюринга Т=<A, Q, q

, q

, > удобно представлять в виде

автоматически функционирующего устройства, способного находиться в

конечном числе внутренних состояний Q=q

…q

n-2

, q

 и снабженного

бесконечной внешней памятью – лентой. Среди состояний Q имеются два

выделенных – начальное q

и заключительное q

. Лента разделена на ячейки и

потенциально бесконечна в обе стороны. В каждой ячейке ленты может быть

записана любая из букв внешнего алфавита А=a

, a

…a

 (a

– пустая буква,

то есть считается, что в пустой ячейке записана a

). Функционирование

машины обуславливает программа =q

 q

.

Схема такого устройства как совокупность стуктурно-связанных

внутренней и внешней памяти, блока управления и управляемой головки

дает возможность имитировать алгоритмические процессы распознавания и

порождения цепочек языка произвольного типа (по Хомскому).

На схеме:

а) Блок управления производит преобразование пары (цепочки из двух

символов) q

Q*A в тройку q

Q*A*D. Это означает, что если

машине находится в состоянии q

(то есть вычисляет инструкцию q

), а

управляемая головка считывает символ a

из обозреваемой ячейки внешней

память, то блок управления вырабатывает команду q

, согласно которой:

1) машина переходит в состояние q

(допускается k=j)4

2) в обозреваемую ячейку ленты вместо символа a

записывается символ

(допускается i =L);

3) управляющая головка (лента) перемещается на один шаг или остается

на прежнем месте (d

– перемещение на один шаг влево, d

–

перемещение на один шаг вправо, d

– оставаться на месте; d

, d

D).

Итак, если блок управления осуществляет функциональное отображение:

: Q*A Q*A*D,

где q

Q*A, q

Q*A*D, a

, a

А, q

, q

Q, d

D= d

, d

, то

машину Тьюринга будем называть детерминированной и всюду

определенной.

б) Данные (исходные, промежуточные и окончательные) машины есть

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

бесконечной ленте внешней памяти (каждый символ слова в отдельной

ячейке) (А=А

исх

 А

пром

А

рез

, а

А

исх

, а

А

рез

в) Элементарные шаги в рассматриваемой машине следующие:

1) изменение состояния машины и содержимого ячейки, обозреваемой

управляемой головкой;

2) перемещение управляемой головки на один шаг влево ( вправо);

г) Детерминированность работы машины обуславливается программой ее

работы , то есть совокупностью выражений (j, i) (j=0,n; i= 0,n), каждое из

которых имеет один из следующих видов:

 q

где 0  k n, 0 L m.

В дальнейшем программу будем записывать в табличном виде:

A \ Q q

… q

…

или диаграммой переходов вида:

i