* Алгоритмічно нерозв'язні задачі
Проблема розв’язності (зависання)
В теорії обчислювальності існує проблема зависання (обчислювальності): дано опис алгоритму та початкові вхідні дані, необхідно визначити, чи може алгоритм з цими вхідними даними завершитися коли-небудь. Альтернативою зупинки є ситуація, коли робота алгоритму не припиняється (він зависає). Машина Т‘юринга не може бути використана для вирішення проблеми зависання будь-якого алгоритму. Тому подібна задача відноситься до алгоритмічно нерозв‘язних задач
Алгоритмічно нерозв’язні задачі
Алгоритмічна нерозв‘язність – важлива властивість деяких класів коректно поставлених задач, які допускають використання алгоритмів, яка полягає в тому, що задачі кожного із цих класів в принципі не мають якого-небудь загального універсального алгоритму вирішення, що об‘єднує весь клас.
Незважаючи на повну однотипність умов та вимог для подібних задач не існує єдиного алгоритму вирішення.
Однак це не означає, що подібні задачі не можуть бути вирішені в принципі, просто для їх вирішення необхідно використовувати різні підходи, нерідко творчі і нетрадиційні.
Приклад алгоритмічно нерозв‘язної задачі: виявлення «мертвого коду».
Проблема відсутності загального методу вирішення задачі
Ця проблема визначає певний клас алгоритмічно нерозв‘язних задач, приклади:
1. Розподіл дев‘яток у запису числа π:
Визначимо функцію f(n) = i, де n – кількість цифр ―9‖ підряд у десятковому запису числа π, а i – номер найбільш лівої дев‘ятки із n тих, що йдуть підряд, наприклад: π =3,141592…; f(1) = 5 Задача полягає у визначенні f(n) для довільного n. Оскільки число π є ірраціональним і трансцендентним, то ми не знаємо жодної інформації про розподіл дев'яток (так само як і будь-яких інших цифр) в десятковому записі числа. Обчислення f (n) пов'язане з обчисленням наступних цифр у розкладі π, до тих пір, поки ми не виявимо n дев'яток поспіль, однак у нас немає загального методу обчислення f (n), тому для деяких n обчислення можуть тривати нескінченно - ми навіть не знаємо в принципі (за природою числа π) чи існує рішення для всіх n.
2. Обчислення досконалих чисел
Досконалі числа – це числа, які дорівнюють сумі своїх дільників, наприклад: 28 = 1+2+4+7+14. Визначимо функцію S (n) = n-е за рахунком досконале число і поставимо задачу обчислення S (n) по довільно заданому n. Немає загального методу обрахунку досконалих чисел, невідомо навіть, чи множина досконалих чисел обраховна, чи ні, тому алгоритм має перебирати усі числа підряд, перевіряючи їх досконалість. Відсутність загального методу вирішення не дозволяє відповісти на питання про проблему зупинки: якщо ми перевірили M чисел під час пошуку n-го досконалого числа, чи може це означати, що його взагалі не існує?
3. Десята проблема Гільберта
Нехай задано многочлен n-го ступеня з цілими коефіцієнтами – P, чи існує алгоритм, який визначає, чи існує розв‘язок рівняння P = 0 в цілих числах? Математиками доведено, що такого алгоритму не існує, тобто загальний метод визначення цілих коренів рівняння P=0 по цілочисельним коефіцієнтам многочлену відсутній.
