Московский государственный институт электроники и математики

Московский государственный институт электроники и математики

(Технический университет)

Маркин П.М.

Дискретная математика

Теория алгоритмов

Для студентов специальности "Вычислительные машины, комплексы, системы и сети"

Учебный год

Содержание:

Общие положения. 3

Теория алгоритмов. 3

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

Метрическая теория алгоритмов. 3

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

Предмет изучения. 5

Цель. 5

Содержание курса. 5

Исходные понятия теории алгоритмов. 5

Алгоритм.. 5

Конструктивный объект. 5

Свойства и параметры алгоритма: 6

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

Формальные модели, уточнение понятия алгоритм. 7

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

Алгоритмический язык. 9

Алгоритмическая система А.Тьюринга. 9

а. Разрешимость и неразрешимость языков машиной Тьюринга. 10

б. Проблема остановки машины Тьюринга. 10

Алгоритмическая система А.Чёрча. 11

a. Базисные функции. 11

1. Нуль-функция. 11

2. Функция тождества. 12

3. Функция следования. 12

б. Операторы построения производных рекурсивных функций. 12

1. Оператором суперпозиции(подстановки) 12

2. Оператором примитивной рекурсии. 12

3. Оператор минимизации (m- оператор) 13

Примитивно-рекурсивные функции. 14

Алгоритмическая система А.А.Маркова. 15

Ассоциативное исчисление. 17

Алгоритмически неразрешимые проблемы. 18

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

Теоремы Геделя. 19

I. Теорема о неполноте. 19

II. Теорема о полноте. 19

Словарь основных терминов. 21

ТЕОРИЯ АЛГОРИТМОВ.

 

Общие положения.

 

Теория алгоритмов - раздел математической логики, в котором изучаются теоретические возможности эффективных процедур вычисления (алгоритмов) и их приложения.

Основное понятие этой теории – алгоритм – в интуитивном (наивном) понимании существует в математике довольно давно, а точные математические понятия, которые в том или ином смысле формализуют интуитивное понятие алгоритма, предложены только в середине 30-х годов 20-го века. Необходимость такой формализации была обусловлена как вопросами обоснования математики, так и вопросами доказательства алгоритмической разрешимости и неразрешимости тех или иных задач. Очевидно, что в математике доказываемый объект должен быть точно формализован.

В настоящее время теорию алгоритмов делят на дескриптивную (абстрактную) и метрическую (структурную, прикладную).

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

q = <M₁, M₂, S_f>, где M₁ -множество возможных исходных данных, M₂ – множество возможных результатов применения алгоритма S_f к M₁:

		ImSf (область значений Sf)

 

Пример:

f² : N² →N, где f² – операция сложения чисел N. В этом случае M₁ = N² = Domf², M₂ = N

 

 

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

 

Замечание:

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

 

2. Ниже изучаются сводящиеся друг к другу теоретические модели алгоритмов из 3 классов формальных систем F.S = <L, D>:

- алгоритм рассматривается как исключение формул (рекурсивные функции);

- алгоритм, как гипотетически вычислимое устройство (машины Тьюринга (МТ));

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

 

3. Проблемы построения алгоритма, обладающего теми или иными свойствами. Называется массовой (алгоритмической) проблемой.

Если искомый алгоритм не существует, то говорят, что рассматриваемая массовая проблема неразрешима.

 

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

 

5. Любой алгоритм S_f однозначно сопоставляется исходным данным (если DomS_f ≠ Ø) результат. Это означает, что с каждым алгоритмом S_f однозначно связана функция f, которую алгоритм S_f вычисляет. Однако обратное утверждение неверно (т.е. существуют невычислимые функции).

 

6. Доказательством существования алгоритма S_f вычисления функции f не означает описание этого алгоритма. Так, например, функция

f (x) = 1, если теорема Ферма верна,

0, если теорема не верна,

 

вычислима, т.к. она равна либо функции, тождественно равной 1, либо функции, тождественно равной 0, а обе эти функции вычислимы.

 

7. Множество DomS_f есть разрешимое(рекурсивное) множество исходных данных алгоритма S_f, т.к. характеристическая функция

f _DomSf (x) = 1, если x не принадлежит DomS_f,

0, если x принадлежит DomS_f,

вычислима.

В этом плане говорят о разрешающем алгоритме S_f на множестве исходных данных М₁.

 

Аналогично, ImS_f есть перечислимое (рекурсивно-перечислимое) множество, т.к. оно является областью значений рекурсивной функции f с областью определения DomS_f. Для множества ImS_f алгоритм S_f есть порождающий для М₁.
Предмет и содержание читаемого курса.

 

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

Цель читаемой дисциплины студентам специальности 2201 - усвоение необходимости формулировать алгоритмические проблемы как проблемы решения вопроса о существовании алгоритма для решения данной бесконечной серии однотипных задач и нахождение такого алгоритма в случае, если он существует.

 

Содержание курса - математические модели алгоритмических систем, формы их записи и оценки сложности алгоритмов. В этом аспекте изучаются:

- рекурсивные функции как математический вариант уточнения понятия вычислимой арифметической функции f: Nⁿ→ N;

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

- системы подстановок слов в заданном алфавите;

 

Исходные понятия теории алгоритмов.

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

 

Примеры:

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

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

Сложение (умножение, вычитание, деление) двух чисел (т.е. N²®N) столбиком – алгоритм.

 

Пример:

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

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

Шаг 2: Найденное число приписывается справа к возрастающей последовательности чисел R (в начальный момент R пусто) и вычеркивается из М;

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

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

Это описание, которое кажется вполне ясным, далеко от алгоритма. Действительно, если М=í⁹Ö5, ⁶Ö2, (1/3)^p/2ý, то в предложенном варианте решения поставленной задачи не указано, как искать наименьшее число.

 

Этот пример показывает, что понятие алгоритма в интуитивном смысле требует уточнения понятия данных (т.е. указать каким требованиям должны удовлетворять объекты, чтобы алгоритмы могли с ними работать), памяти, дискретности, элементарности, конечности числа шагов, направленности, детерминированности, результативности, массовости.

 

Конструктивный объект – объект формальной системы F.S = <L, D> = <A, S, A_x, R>, где L – формальный язык, D – дедуктивные средства конструктивного процесса построения конструктивных объектов, A_x – аксиомы(исходные данные), A_x принадлежит L, R – отношения на множестве объектов(продукции, правила вывода, правила построения объектов) исходных объектов.

Пример:

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

Так, натуральные числа, рассматриваемые как слова в алфавите A={0, 1} начинающиеся с нуля и не содержащие других вхождений нуля, т.е. как слова 0, 01, 011, 0111…

Очевидно, что рациональные числа также являются конструктивными объектами в алфавите{0, 1, -, /}.

 

Пример:

Формальный язык – конструктивный объект, лексемы которого строятся из букв заданного алфавита с привлечением заданной формальной грамматики.

 

Замечание:

Формальная система F.S., обладающая свойствами элементарности и дискретности шагов построения конструктивных объектов, может служить формальной моделью алгоритма в интуитивном смысле.

Детерминированная формальная система F.S. является формальной моделью алгоритма в абстрактной теории алгоритмов.

 

Пример:

Машина Тьюринга <A, Q, >, как модель алгоритма, есть детерминированная формальная система, порождающая множество своих конфигураций (машинных слов – конструктивных объект, построенных из букв алфавита А ленты и алфавита Q внутренних состояний блока управления головкой): ,

Здесь детерминированность означает, что к каждой конфигурации Машины только одной команды из программы .

 

Примечание:

Исходные данные алгоритма в дальнейшем формализуются как слова в алфавите этих данных. Аналогично формализуются промежуточные и выходные (т.е. результат) данные.

 

Свойства и параметры алгоритма:

Из неформального определения понятия «алгоритм» следуют его характеристические свойства:

- дискретность (каждый конструктивный объект получается из предыдущих по определенному правилу конструктивного процесса)

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

- детерминированность (однозначность выбора правил построения конструктивных объектов)

- Элементарность шагов (отсутствует необходимость уточнения правил конструктивного процесса)

- массовость (инвариантность относительно входных данных; уточнения понятия решения задачи в общем виде)

- результативность (получение требуемого конструктивного объекта по окончанию конструктивного процесса)

 

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

 

Замечание:

 

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

2. Следует различать:

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

- Система реализации алгоритма,

- Процесс реализации алгоритма (конструктивный процесс),

- Сходимость процесса реализации алгоритма (результативная остановка после конечного числа шагов алгоритма),

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

В свете изложенного 7 параметров однозначно характеризуют данный алгоритм:

- совокупность возможных исходных данных,

- совокупность возможных результатов,

- совокупность возможных промежуточных результатов,

- правило начала,

- правила конструктивного процесса.

- правило окончания.

- правило извлечения результата.

 

 

Алгоритмический язык

 

Алгоритмический язык L = <A, S₁, S₂> предназначен для записи алгоритмов и при этом

Некоторый подалфавит В алфавита А используется для кодирования исходной информации.

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

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

В этом плане алгоритмические языки являются теоретической основой языков программирования.

 

Теорема.

«Не существует алгоритма распознавания остановки произвольной МТ для произвольной начальной её конфигурации».

 

Замечание:

Известны два способа доказательства неразрешимости той или иной массовой проблемы: прямой (основанный на так называемом «диагональном» методе) и косвенный (использующий сводимость к данной проблеме другой массовой проблеме, неразрешимость которой была доказана раньше).

 

A. Базисные функции

Базисные (простейшие элементарные) функции – числовые вычислимые функции , сопутствующие алгоритмы которых – одношаговые (очевидно, что это всюду определенные рекурсивные функции)

1. Нуль-функция Z (x₁, x_2,…,x_k)=0 – k-арная функция (оператор аннулирования Z), соответствующий алгоритм вычисления которой: “Любой совокупности значений аргументов x_i функции Z ставится в соответствие ее значение 0”.

Примеры:

; ;

 

1. Функция тождества (x₁, x_2,…,x_m,…,x_n)= x_m ( - оператор проектирования) – n-арная функция, алгоритм вычисления которой: “Значением функции принять значение m-го аргумента.” (m, n>0, m n).

Примеры:

(7,6,1,4)= 6, (6)= 6, (7,15)= 15.

 

1. Функция следования (λ – оператор сдвига) – унарная функция, для которой: “Значением принять натуральное число, следующее за числом, являющимся значением аргумента x ”.

Примеры:

; .

 

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

 

Пример.

Функция f(x₁,…, x_n) возникает из функций h(x₁,…, x_m), g₁(x₁,…, x_n), …g_m(x₁,…, x_n) суперпозицией, если

f(x₁,…, x_n)= Sⁿ_m(h, g₁,…, g_m) = h(g₁(x₁,…, x_n), …, g_m (x₁,…, x_n)).

Если заданы функции Jⁿ_m и операторы Sⁿ_m, то можно считать заданными всевозможные операторы подстановки функции в функцию, а также переименования, перестановки и отождествления переменных.

Так, если f(x₁, x₂)= h(g₁(x₁, x₂), g₂(x₁)), то ее стандартный вид следующий: f(x₁, x₂)= S²₂(h(x₁, x₂), g₁ (x₁, x₂), S¹₂ (J²₁(x₁, x₂), g₂(x₁), g₃(x₁))), где g₃ – любая функция от х₁. Если же имеем f(x₂, x₁, х₃, …, x_n) и f(x₁, x_1, x₃,…, x_n), то пишем:

f(x₂, x₁, х₃, …, x_n) = f(J²₂(x₁, x₂), J²₁(x₁, x₂), х₃, …, x_n),

f(x₁, x_1, x₃,…, x_n)= f(J²₁(x₁, x₂), J²₁(x₁, x₂), х₃, …, x_n).

 

Пример:

2. Оператором примитивной рекурсии R_n[f₁^n-1,f₂ⁿ⁺¹,x₁(n)]=f_mⁿ называется процесс определения функции f (n+1) переменных через n-местную функцию g и (n+2)- местную функцию h в следующем виде:

f(x₁, x_2, …, x_n, 0)= g(x₁, x₂,…, x_n)

f(x₁, x_2, …, x_n, y+1)=h(x₁, x₂,…, x_n, y, f(x₁, x_2, …, x_n, y)),

где g и h – две различные функции соответственно n и n+2 аргументов.

Эта пара равенств называется схемой примитивной рекурсии. Тот факт, что функция f определена схемой примитивной рекурсии выражается равенством f(x₁, x_2, …, x_n, y)=R_n(g, h). В случае, когда n=0, то есть определяемая функция f является одноместной, схема примитивной рекурсии принимает более простой вид:

f(0)=с, f(у+1)=h(y, f(y)), где с – константа.

 

Схема примитивной рекурсии определяет f рекурсивно не только через другие функции g и h, но и через значения f в предшествующих точках: значение функции f в точке у+1 зависит от значения функции f в точке у. Очевидно, что для вычисления f(x₁,…, x_n, k) понадобиться k+1 вычислений по схеме примитивной рекурсии – для у=0, k.

 

Замечания:

Существенным в операторе примитивной рекурсии R_n является то, что независимо от числа переменных в f рекурсия ведется только по одной переменной у (остальные n переменных x₁, x_2, …, x_n на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров).

 

 

3. Оператор минимизации (m- оператор).

Оператором минимизации m (наименьшего числа оператора) называется преобразование (n+1)-местной функции (в общем случае частичной) j в n-местную f, такую, что для любых х₁, х₂, …х_n, у равенство f(х₁, х₂, …х_n)=у имеет место лишь в том случае, если определены и не равны нулю значения j(х₁, …, х_n, 0), …, j(х₁, …, х_n, у-1) и при этом j(х₁, х₂, …х_n, у)=0. Применение оператора минимизации обозначают m[j, (y)], где у - исчезающий аргумент.

 

Говорят, что n-местная арифметическая функция f: Nⁿ®N получается из функции j: Nⁿ⁺¹®N с помощью m-оператора, если выполнено условие: для любых k₁, k₂,…, k_n, kÎN. f(k₁, k₂,…, k_n)=k, тогда и только тогда, когда для всех l<k значения j(k₁, k₂,…, k_n, l) определены и отличны от нуля, а значение j(k₁, k₂,…, k_n, k) определено и равно нулю.

Если f получается из функции j с помощью оператора наименьшего числа m, то пишут: f(x₁, x₂,…, x_n)=my[j(x₁,…, x_n, y)=0].

 

Важным свойством m-оператора является то, что с его помощью из вычислимой функции jвсегда получается частичная вычислимая функция f. Именно, если имеется алгоритм для вычисления j, то значение f(x₁, x₂,…, x_n) может вычисляться следующим образом: вычисляется j(x₁, x₂,…, x_n, 0); если процесс вычисления закончился, то есть значение j(x₁, x₂,…, x_n, 0) определено, и j(x₁, x₂,…, x_n, 0)=0, то полагаем f(x₁, x₂,…, x_n)=0, а если j(x₁, x₂,…, x_n, 0)¹0, то начинают вычислять j(x₁, x₂,…, x_n, 1). Если процесс вычисления закончился и j(x₁, x₂,…, x_n, 1)=0, то полагают f(x₁, x₂,…, x_n)=1, а если j(x₁, x₂,…, x_n, 1)¹0, то переходят к вычислению j(x₁, x₂,…, x_n, 2) и так далее.

Процесс вычисления закончится, если найдется такое у, что для всех z < y значение j(x₁, x₂,…, x_n, z) определено и отлично от нуля, а j(x₁, x₂,…, x_n, у) определено и равно нулю. Тогда f(x₁, x₂,…, x_n) = у.

 

Пример:

f(x)=my[12*y-x½=0]. Тогда f(x)=x/2 при всех четных значениях хÎN.

Замечание:

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

Пример:

det f(x)=m[J²₁(x, y), (y)].

Полученная функция f(х) обладает следующими свойствами:

f(0)=0, f(k) не существует при k¹0. Последнее означает, что для заданной функции J²₁(x, y) m-оператор не может построить f(k) kÎN, так как при x=k функция j(x, y)= J²₁(x, y) ни для какого значения у не будет равной нулю.

 

Ассоциативное исчисление

Ассоциативное исчисление (система Туэ) U – формальная система F.S., задающая конечно определенные ассоциативные системы (полугруппы) K_u.

Всякое ассоциативное исчисление U=<A, Σ> определяется указанием некоторого алфавита A и конечного списка Σ соотношений в A – пар слов в этом алфавите α_i↔β_i. Пара α_i→β_i понимается как левая подстановка, а β_i→α_i – как правая постановка в заданное слово αÎA^*=eÈAÈA∙AÈ…ÈA^kÈ…(kÎN; e – пустое слово).

Допустимым относительно списка Σ действием над словами в алфавите A называется любая подстановка одной из частей какого-либо соотношения α_i↔β_i ((α_i↔β_i)ÎΣ) вместо вхождения другой части того же соотношения.

Ассоциативное исчисление U=<A, Σ> представляет собой разрешение производить, исходя из любого слова RÎA^*, любые допустимые относительно списка Σ действия.

 

Пример:

Подстановка ab↔bcb применима четырьмя способами к слову P₁=abcbcbab: замена каждого из двух вхождений bcb даст слова aabcbab и abcabab, а замена каждого из двух вхождений ab дает слова bcbcbcbab и abcbcbbcb. В то же время к слову P₂=bacb эта подстановка не применима, а подстановка вида α↔e означает, что из преобразуемого слова P_iÎA^* выбрасывается вхождение слова α, а также что между двумя какими-либо буквами преобразуемого слова или впереди него, или за ним вставляется слово α (e-пустое слово, eÎA^*, eÏA). Обо всех словах Q, которые при этом получаются (в том числе и о самом исходном слове P), говорят, что они эквивалентны P в ассоциативном исчислении U=<A,Σ> (в символической записи U:P_╨Q).

Отношение _╨ для любого ассоциативного исчисления U рефлексивно, симметрично и транзитивно. Кроме этого, из U:P_1╨Q и P_2╨R следует, что U: P₁P_2╨QR. Это позволяет естественным образом сопоставить всякому ассоциативному исчислению U некоторую конечно определенную ассоциативную систему K_u, взяв в качестве ее элементов классы слов, эквивалентных друг другу в U=<A, Σ>, а в качестве операции умножения в K_u – операцию конкатенации слов в алфавите A.

Так настроенная ассоциативная система K_u будет моноидом, т.е. будет иметь нейтральный элемент eÎA^*; элементы K_u представленные буквами алфавита A, будут составлять для K_u систему порождающих элементов, а список соотношений Σ будет представлять собой полную систему соотношений между упомянутыми порождающими элементами K_u в том смысле, что элементы K_u, представленные словами P и Q, тождественны в K_u тогда и только тогда, когда P и Q эквивалентны в U=<A, Σ>. В этом плане, распознавание тождества элементов в K_u сводится распознаванию эквивалентности слов в U=<A, Σ>.

Отсюда понятна важность исследования разрешимости алгоритмической проблемы распознавания эквивалентности слов в произвольном ассоциативном исчислении. Эта проблема состоит в том, что для произвольного U=<A, Σ> требуется построить алгоритм, который для любой пары слов в алфавите A U=<A, Σ> позволял бы за конечное число шагов выяснить, эквивалентны ли в U=<A, Σ> слова, составляющие эту пару. В алгебраической интерпретации эта проблема есть проблема тождества для полугруппы K_u.

 

Теорема (Маркова-Поста):

“Существует ассоциативное исчисление, в котором проблема распознавания эквивалентности слов алгоритмически неразрешима”

 

Действительно, рассматривая машину Тьюринга как математическую модель алгоритма, можно свести проблему распознавания эквивалентности слов в U=<A, Σ> к проблеме остановки машины Тьюринга (а эта проблема является алгоритмически неразрешимой).

 

Приведем и следующие две теоремы:

“Для любого перечислимого множества M существует система подстановок, множество заключительных слов которой совпадает с M”

“В ассоциативном исчислении два слова эквивалентны, если им соответствуют две конфигурации машины Тьюринга такие, что за конечное число тактов машина переходит из первой конфигурации ко второй”

 

Очевидно, что теорема: “Существует полугруппа заданная определяющими соотношениями, в которой проблема распознавания эквивалентности (равенства) слов алгоритмически неразрешима” является переформулировкой теоремы Маркова-Поста.

Примером ассоциативного исчисления с неразрешимой проблемой равенства является исчисление U=<{a,b,c,d,e},{ac↔ca, ad↔da, bc↔cb, bd↔db, abac↔abace, eca↔ae, edb↔be}>

 

Замечание:

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

 

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

 

Теоремы Геделя.

I. Теорема о неполноте

 

Эта теорема Геделя обычно рассматривается как следующие два утверждения:

1. «В любой непротиворечивой формальной теории, содержащей формальную арифметику, найдется формально неразрешимое суждение, т.е. такая замкнутая формула А, что ни А, ни ┐А не являются выводимыми в этой теории».

2. «Для любой непротиворечивой формальной теории, содержащей формальную арифметику, формула А, выражающая непротиворечивость теории, недоказуема в теории».

II. Теорема о полноте

Эта теорема является утверждением о полноте классического И.П:

«Всякая предикатная формула, истинная во всех моделях выводима (по формальным правилам классического исчисления предикатов)».

 

Примечание:

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

 

2. Теорема Геделя о полноте утверждает перечислимость множества всех истинных высказываний логики предикатов.

 

 

3. Согласно теореме Черча классическое исчисление предикатов неразрешимо.

В этом плане, не смотря на полноту И.П. разрешающей процедуры, связанной

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

4. Исчисление высказываний разрешимо и полно. Разрешающий алгоритм для всех формул F И.В. заключается в вычислении значений F на всех наборах значений её переменных. В виду полноты И.В. F является его теоремой, если и только если она истинна на всех своих наборах.

 

 

 

Словарь основных терминов.

 

Теория алгоритмов - раздел математической логики, в котором изучаются теоретические возможности эффективных процедур вычисления (алгоритмов) и их приложения.

 

Массовая (алгоритмическая) проблема - проблема построения алгоритма, обладающего теми или иными свойствами.

 

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

 

Конструктивный объект – объект формальной системы F.S = <L, D> = <A, S, A_x, R>, где L – формальный язык, D – дедуктивные средства конструктивного процесса построения конструктивных объектов, A_x – аксиомы(исходные данные), A_x принадлежит L, R – отношения на множестве объектов(продукции, правила вывода, правила построения объектов) исходных объектов.

 

Формальный язык – конструктивный объект, лексемы которого строятся из букв заданного алфавита с привлечением заданной формальной грамматики.

 

Алгоритмический язык L = <A, S₁, S₂> предназначен для записи алгоритмов и при этом . Алгоритмический язык называется универсальным, если он содержит алгоритмически полный набор предписаний. Задание универсального алгоритмического языка равносильно заданию алгоритмической системы, т.е. общего способа записи алгоритма.

 

Алгоритмические процессы – процессы, которые могут имитироваться на подходяще построенной абстрактной машине, описываемой в точных математических терминах

 

Тезис Тьюринга: «Для всякого алгоритма S_f в каком-либо алфавите может быть построен тьюриноговский алгоритм, дающий при одинаковых исходных данных, те же самые результаты, что и алгоритм S_f».

 

Тезис Черча-Тьюринга: «Любая теоретически разрешимая вычислительная задача может быть решена при помощи машины Тьюринга».

 

 

Машина Тьюринга (МТ) – алгоритмически полная система побуквенной обработки словарной информации. Эта гипотетическая машина является формой существования и записи алгоритма.

 

Рекурсивное (разрешимым) множество - множество слов, для которого МТ однозначно решает задачу принадлежности или не принадлежности данного слова языку, т.е. машина либо переходит в состояние q_z1, соответствующее заключению о принадлежности слова языку, либо в состояние q_z2 – слово не принадлежит языку.

 

Рекурсивно-перечислимое (частично-разрешимое) множество – такое множество, если МТ останавливается в заключительном состоянии для лексем (слов заданного алфавита) и «зависает» (зацикливается) или останавливается в состоянии q_i q_z (безрезультатная остановка) для непринадлежащих языку слов.

 

Тезис Черча: “Всякая функция, значение которой может вычисляться эффективно, является частично-рекурсивной” (т.е. вычислимыми функциями являются частично-рекурсивные функции – функции, получаемые за конечное число шагов из простейших с помощью суперпозиции, примитивной рекурсии и μ-оператора).

 

Базисные (простейшие элементарные) функции – числовые вычислимые функции , сопутствующие алгоритмы которых – одношаговые (очевидно, что это всюду определенные рекурсивные функции)

 

Нуль-функция Z (x₁, x_2,…,x_k)=0 – k-арная функция (оператор аннулирования Z), соответствующий алгоритм вычисления которой: “Любой совокупности значений аргументов x_i функции Z ставится в соответствие ее значение 0”.

 

Функция тождества (x₁, x_2,…,x_m,…,x_n)= x_m ( - оператор проектирования) – n-арная функция, алгоритм вычисления которой: “Значением функции принять значение m-го аргумента.” (m, n>0, m n).

 

Функция следования (λ – оператор сдвига) – унарная функция, для которой: “Значением принять натуральное число, следующее за числом, являющимся значением аргумента x ”.

 

Оператором суперпозиции(подстановки) Sⁿ_m называется операция подстановки в функцию от m переменных m функций от n переменных. , а сопутствующий алгоритм которого: «Значения m –арных функций принять за значения аргументов n–арной функции и вычислить её значение».

 

Оператором примитивной рекурсии R_n[f₁^n-1,f₂ⁿ⁺¹,x₁(n)]=f_mⁿ называется процесс определения функции f (n+1) переменных через n-местную функцию g и (n+2)- местную функцию h в следующем виде:

f(x₁, x_2, …, x_n, 0)= g(x₁, x₂,…, x_n)

f(x₁, x_2, …, x_n, y+1)=h(x₁, x₂,…, x_n, y, f(x₁, x_2, …, x_n, y)),

где g и h – две различные функции соответственно n и n+2 аргументов.

Эта пара равенств называется схемой примитивной рекурсии.

 

Оператором минимизации m (наименьшего числа оператора) называется преобразование (n+1)-местной функции (в общем случае частичной) j в n-местную f, такую, что для любых х₁, х₂, …х_n, у равенство f(х₁, х₂, …х_n)=у имеет место лишь в том случае, если определены и не равны нулю значения j(х₁, …, х_n, 0), …, j(х₁, …, х_n, у-1) и при этом j(х₁, х₂, …х_n, у)=0

 

 

Базисные функции для всех натуральных n, m, где n³m являются примитивно-рекурсивными;