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

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

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

Рубрика: 

• чтобы процесс переработки данных состоял из отдельных
дискретных шагов и был детерминированным;
• чтобы были четко указаны условия остановки процесса, и что
следует считать результатом процесса.
Таким образом, любой алгоритм характеризуется массовостью,
детерминированностью и результативностью. Для решения любой
массовой задачи требуется построить соответствующий алгоритм,
поэтому важность понятия алгоритм трудно переоценить.
Математика накопила большое число алгоритмов для решения
разнообразных задач. В то же время попытки решения ряда задач
натолкнулись на трудности, которые не удалось преодолеть.
Возникла необходимость доказать существование алгоритма
(алгоритмическую разрешимость) или принципиальную
невозможность построения алгоритма (алгоритмическую
неразрешимость) для ряда важных задач.
Между тем, сформулированное выше понятие алгоритма нельзя
считать точным определением, моделью алгоритма. Поэтому были
предложены точные математические модели, уточняющие понятие
алгоритма: машина Тьюринга, система рекурсивных функций Клини,
нормальный алгоритм А.А.Маркова, схема Колмогорова-Успенского,
лямбда-конверсии Черча, финитные комбинаторные процессы Поста.
А.Черч впервые обосновал положение о том, что все уточнения
понятия алгоритма эквивалентны ("тезис Черча"), т.е. правильно
отражают интуитивное представление об алгоритмах, сложившееся в
математике.
С помощью этих моделей алгоритма доказана алгоритмическая
неразрешимость ряда важных задач математики и вычислительной
техники и, в частности, неразрешимость проблемы останова
универсальной вычислительной машины, реализующей любой
алгоритм. Например, из алгоритмической неразрешимости проблемы
останова следует важный практический вывод: невозможно создать
универсальную отладочную программу для обнаружения
возможности зацикливания отлаживаемой программы.
Алгоритмически неразрешимой оказалась проблема
выводимости в исчислении предикатов: для любых формул P и Q
узнать, существует ли дедуктивная цепочка, ведущая от P к Q.
142

Страницы