Проблема алгоритмической разрешимости в математике

Содержание
1. История возникновения понятия «алгоритм» 3
2. Проблема алгоритмической разрешимости 4
3. Формулировки проблемы разрешения 5
4. Примеры и решение проблемы разрешимости 6
Литература 9

1. История возникновения понятия «алгоритм»
Алгоритм – это предписание исполнителю выполнить последовательность команд, приводящую от исходных данных к искомому результату.
Алгоритм – это конечная последовательность указаний, адресованных исполнителю, четко и однозначно задающая процесс решения задач какого-либо типа во всех деталях и позволяющая получить за конечное число шагов результат, однозначно определяемый исходными данными.
Некоторые из математических алгоритмов известны уже несколько тысячелетий. Считается, что самым древним нетривиальным алгоритмом является способ нахождения наибольшего общего делителя двух целых чисел. Он был открыт около 2300 лет тому назад и известен как алгоритм Евклида, поскольку содержится в первых предложениях седьмой книги «Начал» этого древнего математика. (Правда есть предположение, что алгоритм Евклида лишь интерпретация алгоритма, предложенного Эвдоксом за 75 лет до этого.)

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