Понятие алгоритма и неформальной вычислимости

Нан аборе I(F)=I(F’)=1

Получим противоречие, т. к. формула F по условию является противоречием, т. е. множество формул Г является не выполнимым.

(23) Пусть C1 и C2 – произвольные предложения ИВ, за счет произвольности предположим C1’ и C2’:

C1=C1’vP C2=C2’v ┐P

P и ┐P – контральные литералы.

Правило вывода привила резолюции выглядит так:

где C1 и C2 – резольвируемы (родительские предложения), а C1’ и C2’ – резольвенты (дочерние предложения)

Частными случаями этого правила являются:

1) 

2)  Правило транзитивности:

3)  Правило слияния:

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

I(C1)=1 I(C2)=1

1)  C1=C1’vP

I(P)=0 & C1’≠(0) → I(C1’)=1 I(C1’vC2’)=1

2)  C2=C2’vP

I(P)=1 & C2’≠(0) → I(C2’)=1

I(C2’vC1’)=1

(24)

C1, C2 – резольвируемые предложения ИП, которые представлены:

C1=С1’vP1

C2=C2’v ┐P2

P1 и ┐P2 – контральные литералы.

Унифицируемы общим унификатором

(P1 и P2) =P

(25) Суть алгоритма:

Нужно доказать вывод

Алгоритм:

1)  Каждой из формул множества Г, и формула ┐S (от противного), сводятся во множество предложений С

2)  В полученном совокупном множестве C отыскиваются резольвируемые предложения C1 и C2, к которым применяются правило, к которым применяются правило резолюции, а его результат (резольвента) расширяет множество предложений С.

3)  Продолжать выполнение пунктов 1-2 до тех пор, пока не ьулеи получена пустая резольвента. (C1’vC2’)δ=0, т. е. C1 и C2 образуют противоречие P1&┐P2 и согласно теореме * множество C не имеет модели.

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

В этом алгоритме возможны 3 случая:

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

2)  В результате очередного шага, получена нулевая резольвента (пустое множество), т. е. — верен.

3)  Процесс пополнения резольвентами множества C не дает пустых резольвент, сколько бы мы этих шагов не производили т. е. алгоритм зацикливается, поэтому он полуразрешим.

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

Фундаментальные вопросы:

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

2)как распознавать разрешимые и не разрешимые проблемы?

3)что такое вычислимость? эффект вычислимости?

4)что мы должны вкладывать в понятие алгоритм? И тд.

Основные хар-ки и особенности алгоритма:

1)св-во определённости(алг разбивает задачу на более простые шаги)

2)для алг. всегда определены входные данные

3)определен вид представления выходных данных(может быть даже изображение или сигнал)

4)детерминированность-при завершении любого шага всегда определены дальнейшие действия.

конкретные извесные задачи для которых на уровне теорем док-но.,что для них не сущ. Алгоритмов решения.

ЗАМ. в реальных задачах все участвующие объекты можно кадировать целыми числами. ф-лыопределены на мн-ве натуральных чисел с нулем. Сами фун-ции так же принимают значение з этого мн-ва

n-местное

ОПР. если область определения допускает значек включения???????

Т. е. может совпадать с ,то такие фун-ции наз-ют ВСЮДУ ОПРЕДЕЛЁННЫМИ. иначе (если строгое включение)ЧАСТИЧНОопред.

ОПР. фун-ция ЭФФЕКТИВНО_ВЫЧИСЛЯЕМАЯ, если алгоритм вычисляющий её и для алг. Должны выполнятся условия в области опред-ния

2)если алгоритм должен зациклится.

ЗАМЕЧ. понятие эфеективн-ти вычислимости шире чем понимание алгоритма сводящегося в вычислением на ЭВМ или каких либо устройствах.

(27)Подход Геделя-Клини к формализации понятия алгоритма: Частично-рекурсивные функции (ЧРФ): операторы суперпозиции, примитивной рекурсии, минимизации для построения ЧРФ.Идея Г. Т.получить вче вычислимые ф-ции из существенно ограниченного базиса с помощью простейших алгоритм. средств

А)нулевая фун-цияфун-ция следованияфун-ция проэкции о от1доN

Б)1)Оператор суперпозиции

и

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

Строится(n+1 фун-ция из двух фу-ций n-местной и (n+2) месной =-это равенство определяется оператор(2)

(1) Вторая ф-ла реализует св-во рекурсии. Первая нужна для вычисления стартового обеспечения условия. ЗАМ. Ф-ция может быть рекурсивной по всем предыдущим переменным.