Содержание
Содержание
1. История возникновения понятия «алгоритм» 3
2. Проблема алгоритмической разрешимости 4
3. Формулировки проблемы разрешения 5
4. Примеры и решение проблемы разрешимости 6
Литература 9
Выдержка из текста
1. История возникновения понятия «алгоритм»
Алгоритм – это предписание исполнителю выполнить последовательность команд, приводящую от исходных данных к искомому результату.
Алгоритм – это конечная последовательность указаний, адресованных исполнителю, четко и однозначно задающая процесс решения задач какого-либо типа во всех деталях и позволяющая получить за конечное число шагов результат, однозначно определяемый исходными данными.
Некоторые из математических алгоритмов известны уже несколько тысячелетий. Считается, что самым древним нетривиальным алгоритмом является способ нахождения наибольшего общего делителя двух целых чисел. Он был открыт около 2300 лет тому назад и известен как алгоритм Евклида, поскольку содержится в первых предложениях седьмой книги «Начал» этого древнего математика. (Правда есть предположение, что алгоритм Евклида лишь интерпретация алгоритма, предложенного Эвдоксом за 75 лет до этого.)
Список использованной литературы
Литература
1. Ершов Ю. Л. Проблемы разрешимости и конструктивные модели. — М.: Наука, 1980.
2. Катленд Н. Вычислимость. Введение в теорию рекурсивных функций. — М.: Наука, 1983.
3. Мальцев А. И. . Алгоритмы и рекурсивные функции. — М.: Наука, 1986.
4. Справочная книга по математической логике. Ч. III. Теория рекурсии. — М.: Наука. 1982.
5. Чёрч А. Введение в математическую логику. — М.: Наука, 1960.
6. Н. Н. Непейвода. А. А. Ивин. А. С. Карпенко. Проблема разрешимости. Гуманитарная энциклопедия [Электронный ресурс] // Центр гуманитарных технологий. — 21.08.2014 (последняя редакция: 10.06.2015). URL: http://gtmarket.ru/concepts/6927