Вычислимость
Вычислимость — подраздел информатики, который определяет алгоритмы, которые возможно вычислить посредством алгоритмов. Дополнительно же определяется класс вычислимости, чтобы понять, насколько сложнее становится задача с масштабированием.
Описание[править]
Началось всё жужжание с того, что Давид Гильберт сформулировал 23 проблемы, среди которых были и такие непростые задачи, как десятая проблема о разрешимости диофантовых уравнений и программа Гильберта по полной аксиоматизации математики. Программа предполагала, что любая математическая истина должна быть доказуема в формальной системе.
Однако пожилой Курт Гёдель доказал свои теоремы о неполноте и оказалось, что в любой достаточно мощной формальной системе существуют истинные, но недоказуемые утверждения, а также система не может доказать свою собственную непротиворечивость
Для рассмотрения формальных алгоритмов была восрана властная машина Тьюринга. Она чисто математическая и абстрактная, и состоит из бесконечной ленты, разделённой на ячейки, содержащие символы из конечного алфавита Γ, головки, которая читает/пишет символ и перемещается влево/вправо, конечного множества состояний Q, начального состояния q₀ и множества финальных состояний F и функции переходов δ.
С тех пор вычислимой стали называть функцию, которая может быть посчитана на машине Тьюринга, то бишь если всирать произвольные вводные, то машинка начнёт жужжать как здоровенный шмель и выдаст ответ, после чего остановится (это важно).
Так, и поныне не решена властная проблема, обозначаемая как P vs NP.
