Самарская Государственная Архитектурно-Строительная Академия Факультет Информационных Систем и Технологий реферат

Вид материала

Реферат

Содержание Основные требования к алгоритмам. Теория алгоритмов и ее основатели. 2.1. Тьюринг Алан. 2.2. Клини Стефан Коул. 2.3. Чёрч Алоизо. 2.4. Пост Эмиль Леон. Список литературы

Подобный материал:

• Самарская Гуманитарная Академия удк ббк пермяков Ю. Е. Философские основания юриспруденции., 3735.17kb.
• Титульный лист программы обучения по дисциплине Syllabus, 456.17kb.
• Н. Э. Баумана Факультет "Информатика и системы управления" Кафедра "Системы обработки, 128.07kb.
• Анализ и функциональное диагностирование конвейерных систем обработки отчётной информации, 263.02kb.
• 1. Основы безопасности сетевых информационных технологий Основы безопасности сетевых, 100.23kb.
• Самарский Государственный Архитектурно-Строительный Университет Факультет информационных, 88.76kb.
• «применение информационных систем и технологий впроцессе подготовки отчетности по мсфо», 474.4kb.
• Тюменская государственная академия культуры, искусств, 159.77kb.
• Прочность и устойчивость тонкостенных систем с конструктивными особенностями 05. 23., 371.63kb.
• Матвеева Ирина Юрьевна, 326.27kb.

Самарская Государственная Архитектурно-Строительная Академия

Факультет Информационных Систем и Технологий


Реферативная работа по ТИИД

" Основатели теории алгоритмов:

С.КЛИНИ, А.ЧЁРЧ, Э.ПОСТА, А.ТЬЮРИНГ."


выполнил: студент группы ГИП-102 Загвоздкин М.В.

научный руководитель: Афанасьева В.И.


Самара, 2003г.


ОСНОВАТЕЛИ ТЕОРИИ АЛГОРИТМОВ:

С.КЛИНИ, А.ЧЁРЧ, Э.ПОСТА, А.ТЬЮРИНГ.


СОДЕРЖАНИЕ:


Стр.

1. Определение алгоритма. . . . . . . . . . . . . . . . . . . . . 3
   

2. Теория алгоритмов и ее основатели: . . . . . . . . . . . . . 8
   

2.1. Тьюринг Алан; . . . . . . . . . . . . . . . . . . . . . 8

2.2. Клини Стефан Коул; . . . . . . . . . . . . . . . . . . 11

2.3. Чёрч Алоизо; . . . . . . . . . . . . . . . . . . . . . . 11

2.4. Пост Эмиль Леон. . . . . . . . . . . . . . . . . . . . . 13

3. Список литературы. . . . . . . . . . . . . . . . . . . . . . . 15
   

1. Определение алгоритма.
   

Понятие «алгоритм» давно является привычным не только для математиков. Оно является концептуальной основой разнообразных процессов обработки информации. Возможность автоматизации таких процессов обеспечивается наличием соответствующих алгоритмов. С алгоритмами первое знакомство происходит в начальной школе при изучении арифметических действий с натуральными числами. В упрощенном понимании «алгоритм» – это то, что можно запрограммировать на ЭВМ.

Слово алгоритм содержит в своем составе преобразованное географическое название Хорезм. Термин «алгоритм» обязан своим происхождением великому ученому средневекового Востока - Муххамад ибн Муса ал-Хорезми ( Магомет, сын Моисея, из Хорезма ). Он жил приблизительно с 783 по 850 годы, и в 1983 году отмечалось 1200-летие со дня его рождения в городе Ургенче – областном центре современной Хорезмской области Узбекистана. В латинских переводах с арабского арифметического трактата ал-Хорезми его имя транскрибировалось как algorismi. Откуда и пошло слово «алгоритм» – сначала для обозначения алгоритмов цифровых вычислений десятичной позиционной арифметики, а затем для обозначения произвольных процессов, в которых искомые величины решаемых задач находятся последовательно из исходных данных по определенным правилам и инструкциям.

Вплоть до 30-х годов нашего столетия понятие алгоритма оставалось интуитивно понятным, имевшем скорее методологическое, а не математическое значение. Так, к началу ХХ века много ярких примеров дала алгебра и теория чисел. Среди них упомянем алгоритм Евклида нахождения наибольшего общего делителя двух натуральных чисел или двух целочисленных многочленов, алгоритм Гаусса решения системы линейных уравнений над полем, алгоритм нахождения рациональных корней многочленов одного переменного с рациональными коэффициентами, алгоритм Штурма определения числа действительных корней многочлена с действительными коэффициентами на некотором отрезке действительных чисел, алгоритм разложения многочлена одного переменного над конечным полем на неприводимые множители. Указанные алгоритмические проблемы решены путем указания конкретных разрешающих процедур. Для получения результатов такого типа достаточно интуитивного понятия алгоритма. Однако, в начале ХХ века были сформулированы алгоритмические проблемы, положительное решение которых представлялось маловероятным. Решение таких проблем потребовало привлечения новых логических средств. Ведь одно дело доказать существование разрешающего алгоритма – это можно сделать, используя интуитивное понятие алгоритма. Другое дело – доказать несуществование алгоритма – для этого нужно знать точно – что такое алгоритм.

Задача точного определения понятия алгоритма была решена в 30-х годах в работах Гильберта, Чёрча, Клини, Поста, Тьюринга в двух формах: на основе понятия рекурсивной функции и на основе описания алгоритмического процесса. Рекурсивная функция это функция, для которой существует алгоритм вычисления ее значений по произвольному значению аргумента. Класс рекурсивных функций был определен строго как конкретный класс функций в некоторой формальной системе. Был сформулирован тезис (называемый «тезис Чёрча»), утверждающий, что данный класс функций совпадает с множеством функций, для которых имеется алгоритм вычисления значений по значению аргументов. Другой подход заключался в том, что алгоритмический процесс определяется как процесс, осуществимый на конкретно устроенной машине (называемой «машиной Тьюринга»). Был сформулирован тезис (называемый «тезис Тьюринга»), утверждающий, что любой алгоритм может быть реализован на подходящей машине Тьюринга. Оба данных подхода, а также другие подходы (Марков, Поста) привели к одному и тому же классу алгоритмически вычислимых функций и подтвердили целесообразность использования тезиса Чёрча или тезиса Тьюринга для решения алгоритмических проблем. Поскольку понятие рекурсивной функции строгое, то с помощью обычной математической техники можно доказать, что решающая некоторую задачу функция не является рекурсивной, что эквивалентно отсутствию для данной задачи разрешающего алгоритма. Аналогично, несуществование разрешающей машины Тьюринга для некоторой задачи равносильно отсутствию для нее разрешающего алгоритма. Указанные результаты составляют основу так называемой дескриптивной теории алгоритмов, основным содержанием которой является классификация задач по признаку алгоритмической разрешимости, то есть получение высказываний типа «Задача П алгоритмически разрешима» или «Задача П алгоритмически неразрешима». В данном направлении получен ряд фундаментальных результатов. Среди них отрицательное решение Новиковым П.С. в 1952 году классической проблемы тождества для конечно определенных групп, сформулированной Деном в 1912 году. Знаменитая десятая проблема Гильберта, сформулированная им в 1900 году (среди других 23 проблем) формулируется так: «10. Задача о разрешимости диофантова уравнения. Пусть задано диофантово уравнение с произвольными неизвестными и целыми рациональными числовыми коэффициентами. Указать способ, при помощи которого возможно после конечного числа операций установить, разрешимо ли это уравнение в целых рациональных числах». Алгоритмическая неразрешимость 10-й проблемы Гильберта была доказана в 1970 году Мятиясевичем Ю.В.

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

В технику термин «алгоритм» пришел вместе с кибернетикой. Понятие алгоритма помогло, например, точно определить, что значит эффективно задать последовательность управляющих сигналов. Применение ЭВМ послужило стимулом развитию теории алгоритмов и изучению алгоритмических моделей, к самостоятельному изучению алгоритмов с целью их сравнения по рабочим характеристикам (числу действий, расходу памяти), а также их оптимизации. Возникло важное направление в теории алгоритмов - сложность алгоритмов и вычислений. Начала складываться так называемая метрическая теория алгоритмов, основным содержанием которой является классификация задач по классам сложности. Сами алгоритмы стали объектом точного исследования, как и те объекты, для работы с которыми они предназначены. В этой области естественно выделяются задачи получения верхних и задачи получения нижних оценок сложности алгоритмов, и методы решения этих задач совершенно различны. Для получения верхних оценок достаточно интуитивного понятия алгоритма. Для этого строится неформальный алгоритм решения конкретной задачи и затем он формализуется для реализации на подходящей алгоритмической модели. Если показывается, что сложность (время или память) вычисления для этого алгоритма не превосходит значения подходящей функции при всех значениях аргумента, то эта функция объявляется верхней оценкой сложности решения рассматриваемой задачи. В области получения верхних оценок получено много ярких результатов для конкретных задач. Среди них разработаны быстрые алгоритмы умножения целых чисел, многочленов, матриц, решения линейных систем уравнений, которые требуют значительно меньше ресурсов, чем традиционные алгоритмы.

Установить нижнюю оценку – значит доказать, что никакой алгоритм вычисления не имеет сложности меньшей, чем заданная граница. Для получения результатов такого типа необходима точная фиксация рассматриваемой алгоритмической модели, и такие результаты получены только в очень жестких вычислительных моделях. В связи с этим получила развитие проблематика получения “относительных” нижних оценок, так называемая теория NP-полноты, связанная с труднорешаемостью переборных задач.

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

1. Каждый алгоритм имеет дело с данными – входными, промежуточными, выходными. Для того, чтобы уточнить понятие данных, фиксируется конечный алфавит исходных символов (цифры, буквы и т.п.) и указываются правила построения алгоритмических объектов. Типичным используемым средством является индуктивное построение. Например, определение идентификатора в АЛГОЛЕ: идентификатор – это либо буква, либо идентификатор, к которому приписана справа либо буква, либо цифра. Слова конечной длины в конечных алфавитах - наиболее обычный тип алгоритмических данных, а число символов в слове - естественная мера объема данных. Другой случай алгоритмических объектов - формулы. Примером могут служить формулы алгебры предикатов и алгебры высказываний. В этом случае не каждое слово в алфавите будет формулой.

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

3. Алгоритм состоит из отдельных элементарных шагов, причем множество различных шагов, из которых составлен алгоритм, конечно. Типичный пример множества элементарных шагов – система команд ЭВМ.

4. Последовательность шагов алгоритма детерминированна, то есть после каждого шага указывается, какой шаг следует выполнять дальше, либо указывается, когда следует работу алгоритма считать законченной.

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

6. Алгоритм предполагает наличие механизма реализации, который по описанию алгоритма порождает процесс вычисления на основе исходных данных. Предполагается, что описание алгоритма и механизм его реализации конечны.

Можно заметить аналогию с вычислительными машинами. Требование 1 соответствует цифровой природе ЭВМ, требование 2 - памяти ЭВМ, требование 3 – программе машины, требование 4 – ее логической природе, требования 5, 6 – вычислительному устройству и его возможностям.

Имеются также некоторые черты неформального понятия алгоритма, относительно которых не достигнуто окончательного соглашения. Эти черты сформулируем в виде вопросов и ответов.

7. Следует ли фиксировать конечную границу для размера входных данных?

8. Следует ли фиксировать конечную границу для числа элементарных шагов?

9. Следует ли фиксировать конечную границу для размера памяти?

10. Следует ли ограничить число шагов вычисления?

На все эти вопросы далее принимается ответ «НЕТ», хотя возможны и другие варианты ответов, поскольку у физически существующих ЭВМ соответствующие размеры ограничены. Однако теория, изучающая алгоритмические вычисления, осуществимые в принципе, не должна считаться с такого рода ограничениями, поскольку они преодолимы по крайней мере в принципе (например, вообще говоря, любой фиксированный размер памяти всегда можно увеличить на одну ячейку).

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

2. Теория алгоритмов и ее основатели.
   

Теория алгоритмов не учит "составлять" алгоритмы. Она занимается более важным вопросом. Основная задача классической теории алгоритмов - это ответ на вопрос: " Можно ли (вообще) для задач данного типа построить алгоритм?". Говоря более наукообразно: "Являются ли задачи данного типа алгоритмически разрешимыми"? Это связано с тем, что, во-первых, не для всех задач возможно создать алгоритмы их решения. А, во-вторых, чтобы сделать математически строгий вывод о невозможности построить алгоритм, надо иметь строгое (формальное) определение самого алгоритма. Но понятие АЛГОРИТМА относится к фундаментальным неопределяемым понятиям. Понятие алгоритма заменили строго формализованными математическими моделями. Среди самых известных рекурсивные функции, машины Тьюринга и нормальные алгорифмы Маркова. Эти математические модели выступают в роли "конкретизаций понятия алгоритма". То есть длительная практика подтверждает так называемый тезис Черча, который можно пересказать так: Для любой алгоритмически разрешимой задачи можно построить рекурсивную функцию (машину Тьюринга, нормальный алгорифм Маркова). И наоборот, для задач, для которых нельзя построить перечисленные конкретизации, не существует алгоритма решения.

2.1. Тьюринг Алан.

Тьюринг Алан Матисон (Turing, Alan Mathison) (1912–1954), английский математик, логик. Тьюринг родился в Лондоне 23 июня 1912. Учился в Шерборнской школе, затем в Кембриджском университете, который окончил в 1935. В том же году был избран членом совета Кингз-колледжа. В 1936–1938 работал над докторской диссертацией в Принстонском университете в США. В 1937 он опубликовал известную работу «О вычислимых числах, с приложением к проблеме разрешимости» (On the Computable Numbers, with an Application to the Entscheidungsproblem), в которой, используя «машины Тьюринга», показал невозможность существования формальной, чисто механической процедуры, которая позволяла бы решать, выводимо ли данное высказывание из некоторого набора математических аксиом. Вместе с К.Гёделем Тьюринг похоронил надежды Д.Гильберта и его последователей, полагавших, что всю математику можно представить в виде набора аксиом и получаемых на их основе теорем. Поскольку машина Тьюринга является абстрактной вычислительной машиной, было доказано, что существует класс логических задач, не разрешимых с помощью любого компьютера.

Во время Второй мировой войны Тьюринг работал в организации, занимавшейся расшифровкой кодов противника. Принимал участие в создании электромеханического устройства для дешифровки текстов, получаемых с помощью немецкой шифровальной машины «Энигма», и в течение некоторого времени возглавлял отдел, осуществлявший радиоперехват. После войны Тьюринг предложил весьма амбициозный проект АСЕ (Automatic Computing Engine – Автоматическая Вычислительная Машина), над которой работал в Национальной физической лаборатории в 1945–1948. Когда работа над проектом замедлилась по бюрократическим причинам, он перешел на преподавательскую работу в Манчестерский университет, где к его услугам был уже действовавший небольшой компьютер «Марк-1». С конца 1940-х годов Тьюринг занимался математическими проблемами биологии. Свои идеи Тьюринг сформулировал в нескольких выступлениях и интервью, а также в статье Вычислительные машины и разум (Computing Machinery and Intellegence), опубликованной в журнале «Майнд» («Mind») (1950). Эта статья стала эпохальной для той отрасли компьютерной науки, за которой впоследствии закрепилось название «искусственный интеллект». В 1951 Тьюринг был избран членом Лондонского королевского общества.

Умер Тьюринг в своем доме в Уилмслоу, близ Манчестера, 7 июня 1954

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

Машина Тьюринга – машина, имитирующая о осуществляющая алгоритмические процессы. Концепция такого рода машины возникла в середине 30-х годов 20 века в результате анализа действий человека, выполняющего в соответствии с заранее разработанным планом те или иные вычисления, то есть последовательные преобразования знаковых комплексов. Анализ этот в свою очередь, был осуществлен Тьюрингом с целью решения назревшей к тому времени проблемы поиска точного математического эквивалента для общего интуитивного представления об алгоритме.

Машина Тьюринга - это математическая модель идеализированного вычислительного устройства. Ее удобно представить в виде автоматически функционирующего устройства, способного находиться в конечном числе внутренних состояний и снабженного бесконечной внешней памятью - лентой. Лента разделена на конечное число ячеек, в каждой ячейке ленты в определенный момент времени записан один из символов а0, а1, а2, ..., аN.

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

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

Кроме ленты, имеется головка чтения/записи, которая, во-первых, умеет двигаться вперед, назад и стоять на месте; во-вторых, умеет читать содержимое, стирать и записывать символы из данного алфавита; в третьих, управляется программой.

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

Машина Тьюринга - это модель компьютера, и решает она следующую проблему: если для решения задачи можно построить машину Тьюринга, то она алгоритмически разрешима.

И машина Тьюринга, и машина Поста эквивалентны по своим возможностям. Разработаны практически в одно и то же время (в 1936 году) независимо друг от друга.

Можно ли любой алгоритм представить в форме машины Тьюринга? Ответ на этот вопрос дается в виде так называемого тезиса Тьюринга: всякий алгоритм представим в форме машины Тьюринга. Это тезис потому, что его невозможно доказать, так как в нем фигурируют, с одной стороны, интуитивное понятие «всякий алгоритм», а с другой стороны - точное понятие «машина Тьюринга».

Класс нормальных алгоритмов Маркова и класс алгоритмов, представленных в форме машин Тьюринга, совпадают.


2.2. Клини Стефан Коул.


Клини Стивен Коул (Kleene Stephen Cole) (pодился 5.1.1909, Хартфорд, штат Коннектикут) – известный американский логик и математик, член Национальной Академии Наук США (1969). Окончил Принстонский университет (1930). В 1934 году получил степень доктора философии в Принстонском университете. С 1935 работает в Висконсинском университете (с 1948 профессор). Основные труды по теории алгоритмов и рекурсивных функций, а также проблемам интуиционистской логики и математики. В частности, им доказана эквивалентность, введенного А.Чёрчем понятия λ-определимости функции с общерекурсивностью. Введенное Клини понятие (рекурсивной реализуемости формул лежит в основе интуиционистской интерпретации арифметических суждений. Клини – автор ряда широко известных монографий по математической логике, основаниям математики и теории рекурсивных функций. В книге «Введение в математику» (1952) дал очерк состояния оснований математики и возникших в середине 20 века в этой связи основных направлений в математической логике. В ней подробно рассмотрены интуиционистские системы. Ввёл понятие рекурсивной реализуемости формул. Известна классификация Клини-Мостовского для теоретико-числовых предикатов (1943), введенная независимо С.Клини и А.Мостовским.


2.3. Чёрч Алоизо.


Чёрч Алоизо (Church Alonzo) (родился 14.6.1903, Вашингтон) – крупный американский логик и математик, профессор математики Принстонского и Калифорнийского универститетов. С 1936 года редактор журнала «The Journal of Symbolic Logic». Занимался исследованиями проблемы логической семантики. Внес большой вклад в развитие математической логики и теории автоматов. Он знаменит тем, что в 1935 году построил первый пример неразрешимой массовой проблемы, которая состоит в требовании найти алгоритм для решения некоторой серии «единичных» проблем. Массовая проблема неразрешима, если ее решения, то есть требуемого алгоритма, е существует.

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

Алоизо Чёрч автор книги «Введение в математическую логику» (1956), в которой разъяснил свое понимание метода математической логики, определил ее первичные понятия и изложил исчисление высказываний или пропорциональное исчисление, функциональные исчисления первого порядка, чистое функциональное исчисление первого порядка и функциональные исчисления второго порядка. А.Чёрч дает определения таких категорий, как имя, константы и переменные функции, символы, связки, операторы, кванторы, проблема разрешения, непротиворечивость и полнота системы аксиом.

Математическую логику А.Чёрч называет формальной логикой, предмет которой изучается методом построения формализованных языков. «Обычно (формальная) логика, - пишет он, - занимается анализом предложений и доказательств; при этом основное внимание обращается на форму в отвлечении от содержания…»¹ Поскольку естественные языки на протяжении длительных исторических периодов развивались под влиянием практических потребностей легкости общения, постольку они не отличаются точностью и надежностью, что приводит к ошибкам в рассуждениях. Чтобы избежать возможных ошибок, А.Черч предлагает употреблять для логических целей специально созданный язык – формализованный язык, в который из обычных языков будут перенесены собственные имена. При этом он подчеркивает, что в хорошо построенном языке каждое имя должно иметь точно один смысл, если ставится задача обеспечить однозначность в формализованных языках. Суждение А.Чёрч определяет так: «Всякий концепт истинного значения называется суждением независимо от того, является ли он смыслом какого-либо предложения».²

В математической логике большую роль играет тезис Чёрча, принцип, согласно которому класс функций, вычислимых с помощью алгоритмов в широком интуитивном смысле, совпадает с классом частично рекурсивных функций. Тезис Чёрча – это естественнонаучный факт, подтверждаемый опытом, накопленным в математике за всю ее историю. Все известные в математике примеры алгоритмов удовлетворяют ему. Различным уточнениям интуитивного понятия алгоритма соответствуют свои формулировки тезиса Чёрча. Тезис Тьюринга заключается в том, что всякая вычислимая в интуитивном смысле функция вычислима с помощью машины Тьюринга, а принцип нормализации Маркова – в том, что всякая вычислимая в интуитивном смысле функция вычислима с помощью некоторого нормального алгоритма. Из эквивалентности известных уточнений понятия алгоритма следует эквивалентность соответствующих вариантов тезиса Чёрча. Этот факт является еще одним подтверждением тезиса Чёрча. Тезис Чёрча не может быть строго доказан, так как в его формулировке участвует неточное понятие «алгоритм в интуитивном смысле». Были попытки опровергнуть тезис Чёрча, однако они к успеху не привели. Принятие тезиса Чёрча полезно в теории алгоритмов и ее приложениях. Во-первых, при доказательстве существования тех или иных конкретных алгоритмов – машин Тьюринга, рекурсивных функций, нормальных алгоритмов – можно, опираясь на тезис Чёрча, ограничиваться интуитивно ясными построениями и не выписывать соответствующие формальные схемы. Кроме того, тезис Чёрча является основанием для вывода о неразрешимости данной алгоритмической проблемы после того, как строго доказано, что эта проблема не может быть решена в рамках того или иного уточнения понятия алгоритма.


2.4. Пост Эмиль Леон.


Первые многозначные логики построили независимо друг от друга польский логик Я. Лукасевич в 1920 г. и американский логик Э. Пост в 1921 г. С тех пор построены и исследованы десятки и сотни таких «логик».

Пост (Post) Эмиль Леон (11.2.1897 – 21.04.1954) – американский математик и логик. Читал лекции по математике и логике в Колумбийском, Нью-йоркском и других университетах США. Им получен ряд фундаментальных результатов в математической логике: одно из наиболее употребительных определений понятий непротиворечивости и полноты формальных систем (исчислений); доказательства функциональной полноты и дедуктивной полноты (в широком и узком смысле) исчисления высказываний; изучение систем многозначной логики с более чем 3 значениями истинности; одно из первых (независимо от Тьюринга) определений понятия алгоритма в терминах «абстрактной вычислительной машины» и формулировка основного тезиса теории алгоритмов о возможности описать любой конкретный алгоритм посредством этого определения; результаты о выразимости общерекурсивных функций и предикатов через примитивно рекурсивные, в частности так называемая теорема о нормальной форме; первые (одновременно с А.А.Марковым) доказательства алгоритмической неразрешимости ряда проблем математической логики и алгебры.

Э. Пост подходил к построению многозначных логик чисто формально. Пусть 1 означает истину, а 0 — ложь. Естественно допустить тогда, что числа между единицей и нулем обозначают какие-то уменьшающиеся к нулю степени истины.

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

Машина Поста - математическое построение, предназначенное для уточнения понятия алгоритма.

Машиной называется потому, что при построении используются некоторые понятия реальных машин – память, команда, и пр.

Машина Поста состоит из неограниченной в обе стороны ленты, разделенной на ячейки, которые последовательно пронумерованы целыми числами, как положительными, так и отрицательными. В каждой ячейке ленты стоит либо признак того, что в ячейке записана метка, либо ячейка пустая. Состояние ленты - это данные о том, какие ячейки заняты, а какие пусты.

Кроме ленты, имеется головка чтения/записи, которая: - умеет двигаться вперед, назад и стоять на месте;

- умеет читать содержимое, стирать и записывать метку;

- управляется программой, в которую могут входить в любой комбинации и любом количестве шесть команд:

1) Вправо;

2) Влево;

3) Поставить метку;

4) Стереть метку;

5) Передачи управления на один номер команды в программе, если в текущей ячейке есть метка; если метки нет, то передача управления на другой номер команды;

6) Прекращения работы.

Состояние машины - это состояние ленты и положение головки чтения/записи.

Машина Поста, несмотря на внешнюю простоту, может производить различные вычисления, для чего надо задать начальное состояние машины и программу, которая эти вычисления сделает.

Машина Поста - это модель компьютера.

Машина решает следующую проблему: если для решения задачи можно построить машину Поста, то она алгоритмически разрешима.

Машина Поста и машина Тьюринга эквивалентны по своим возможностям. Разработаны практически в одно и то же время (в 1936 г.) независимо друг от друга.

Можно ли любой алгоритм представить в форме машины Поста? Ответ на этот вопрос дается в виде так называемого тезиса Поста: всякий алгоритм представим в форме машины Поста. Это тезис потому, что его невозможно доказать, так как в нем фигурируют с одной стороны, интуитивное понятие «всякий алгоритм», а с другой стороны - точное понятие «машина Поста».

Список литературы

1. Ершов Ю.Л., Палютин Е.А. Математическая логика. М.: Наука, 1987.
   
2. Клини С. Введение в метаматематику. - М.: Изд-во иностр. лит., 1957.
   
3. Клини С. Математическая логика. М., 1973.
   
4. Клини С.К. Машины Тьюринга и рекурсивные функции. М., 1972.
   
5. Кондаков Н.И. Логический словарь-справочник. – М.: Наука, 1975.
   
6. Малышев А. Алгоритмы и рекурсивные функции. - М.: Наука, 1986.
   
7. Математическая энциклопедия. – М.: Изд-во «Советская энциклопедия», 1982.
   
8. Успенский В.А. Машина Поста. М.: Наука, 1988. - 96 с.
   
9. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. - М.: Наука, 1987. - 288с
   
10. Чёрч А. Введение в математическую логику. Т. 1. – М., 1960.