Математическая логика и теория алгоритмов. Задание

ЗАДАНИЯ В КОНЦЕ ТЕКСТА ВЫДЕЛЕНЫ ЦВЕТОМ.

МАТЕРИАЛЫ ПО КУРСУ "Математическая логика и теория алгоритмов"

Тема «ОСНОВЫ ТЕОРИИ АЛГОРИТМОВ. МАШИНА ТЬЮРИНГА»

1. Понятие алгоритма

2. Определение и примеры машин Тюринга

3. Реализация алгоритмов машинами Тюринга

4. Задачи

1. Понятие алгоритма

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

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

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

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