Математическая логика и основы теории алгоритмов. Радаев В.Н. - 8 стр.

UptoLike

ВУЗ: 

СГАУ | Самара

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

Рубрика: 

Вводные замечания и методические указания 7
аппарат, позволяющий вскрыть конституционные принципы функциониро
вания вычислительных и управляющих устройств, которые в значительной
степени определяют облик всей современной цивилизации, и моделировать
их работу.
Представленная программа рассчитана на трехсеместровый период обу
чения и состоит из шести разделов: вводные понятия математической ло
гики; исчисление высказываний; исчисление предикатов; теория рекурсив
ных функций; теория алгоритмов; арифметизация процесса логического
вывода, рекурсивная неразрешимость и дедуктивная неполнота формаль
ной арифметики. Предполагается, что материал, включенный в четыре
первых раздела программы, будет изучаться в течение одного семестра
по следующей схеме: 17 лекционных и 17 практических занятий. Два за
ключительных раздела покрывают соответственно два семестра занятий
по схеме 9 лекционных и 17 практических занятий в каждом из них.
Программа имеет ярко выраженную направленность на изучение об
ширного комплекса результатов, касающихся формально-дедуктивного ме
тода в математике и тесно связанного с этим методом понятия алгорит
ма и вычислимой функции.
12
Значительное место в программе поэтому
зарезервировано для анализа формальных систем (таких как исчисление
предикатов, формальная арифметика и вообще формальные логические
исчисления первой ступени) и выяснения пределов наших возможных зна
ний о таких системах. Понятия алгоритма и вычислимой функции явля
ются одними из центральных понятий всей современной математики. Од
ним из наиболее замечательных достижений математической логики яви
лись разработка понятия общерекурсивной функции и формулировка те
зиса Черча, утверждающего, что понятие рекурсивной функции является
уточнением интуитивного понятия функции, вычислимой с помощью ал
горитма.
13
Используя выражение Поста, можно сказать, что тезис Черча
12
Вычислимая функция функция, для которой существует вычисляющий ее значения алгоритм.
С другой стороны, каждый алгоритм задает функцию, определенную на области его применимости
и ставящую в соответствие каждому элементу этой области результат применения к нему алгоритма.
Систематическое изложение теории вычислимых функций дано в монографии [20]. Первое точное
определение эффективно вычислимой функции принадлежит Эрбрану (J. Herbrand) и Геделю (1934 г.)
и базируется на исчисление равенств ЭрбранаГеделя, развитом с целью нахождения наиболее общего
вида рекурсивных определений теоретико-числовых функций.
13
Класс рекурсивных функций впервые был описан Геделем (1931 г.) как класс всех числовых функ
ций, выразимых в некоторой формальной системе. Пятью годами позже Черч опубликовал свою гипо
тезу о том, что класс рекурсивных функций совпадает с классом вычислимых функций. Тезис Черча
достаточен для того, чтобы придать необходимую ясность термину ”алгоритм” и точно сформули
ровать понятие разрешимости. Опираясь на свою гипотезу Черч доказал неразрешимость основной
алгоритмической проблемы исчисления предикатов проблемы распознавания формул, выводимых
средствами этого исчисления. Математика всегда была тесно связана с теми или иными алгоритмами
и всегда являлась источником алгоритмов вычислений и обработки символьной информации, которые
сами по себе выступают как неотъемлемые компоненты современной научно-исследовательской рабо
ты. Но только после уточнения понятия алгоритма удалось обнаружить существование невычислимых
функций и алгоритмически неразрешимых математических проблем.
Математическая логика и основы теории алгоритмов

Страницы