Математическая логика и теория алгоритмов. Галуев Г.А. - 42 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

Составители: 

Рубрика: 

Математическая Логика и Теория Алгоритмов стр. 42 из 64
© 2003 Галуев Геннадий Анатольевич
0
1
)()( xVWxC⎤
0
2 )()( xVRxC⎤
0
3
)(aC S
0
4 )(aQ
0
5 )()( xRVxQ ¬⎤
Тогда
0
6 )(aR резольвента
0
2 и
0
3
0
7 )(aR⎤ резольвента
0
4 и
0
5
8
0 резольвента
0
6
и
0
7
Таким образом,
G действительно является следствием
1
F и
2
F .
Лекция 8.
Теория алгоритмов.
Слово алгоритм связывают с именем арабского математика IX века Мухаммеда
ибн Муса Аль-Хорезми, впервые выдвинувшего идею о том, что решение любой по-
ставленной математической и философской задачи может быть оформлено в виде по-
следовательности выполняемых правил, то есть алгоритмизировано. Алгоритм А
действует на некотором множестве объектов {a} и представляет собой некоторую оп
-
ределенную последовательность действий (простейших), выполнение которой либо
заканчивается и получается объект А(а), либо процедура эта никогда не заканчива-
ется, либо обрывается без получения значения А на а. Такое интуитивное понятие
алгоритма долгое время устраивало математиков и было достаточным для установле-
ния того, является ли данное предписание(последовательность действий) алгорит-
мом, особенно если идет речь о построении конкретных алгоритмов для решения кон-
кретных задач. Однако, как только мы, придя к предположению о возможной нераз-
решимости какой-либо алгоритмической проблемы, начнем пытаться доказывать, что
эта неразрешимость действительно имеет место, мы в общем случае сразу же столк-
немся с необходимостью уточнения понятия алгоритма
его стандартизации. Осозна-
ние этого факта и широкие исследования области оснований математики (аксиомати-
ческие теории множеств в исчислении высказываний предикатов) привели к появле-
нию в 30-е годы сразу нескольких уточненных понятий алгоритма:
А. Чёрч - λ-конверсии Чёрча, рекурсивные функции Эрбрана-Геделя-Пливей
комбинаторные процессы Поста, машины Тьюринга, позднее нормальные алгоритмы
Маркова А. А..
Произведенное уточнение понятия алгоритма дало немедленный эффект. В 1936 году
Чёрчем была доказана неразрешимость знаменитой проблемы – разрешимости для
классического исчисления предикатов, которую в то время Гильберт считал главной
проблемой математической логики.
В 1947 году А. А. Марковым на основе понятия нормального алгоритма была ус-
тановлена неразрешимость проблемы ТУЭ – проблемы тождества
для полугрупп, то
есть первый пример неразрешимой алгоритмически проблемы собственно математи-
ческого характера.
Особенно возросла роль понятия алгоритма с появлением ЭВМ и созданием ал-
горитмических языков программирования. Собственно теория алгоритмов стала осно-
вой современной вычислительной математики и программирования.
Наиболее существенным для оправдания появления различных уточнений по-
нятия алгоритма оказалось совпадение
классов вычислимых функций для всех этих
понятий. Оказалось, что все эти понятия сводимы друг к другу, то есть эквивалентны.
В тоже время наличие различных понятий алгоритма имеет и свои преимущества, так
как для различных классов задач бывает удобнее использовать и различные понятия
алгоритма (также как различные языки программирования ориентированы на разные
классы задач).

Страницы