Вычислимая функция
-
Определение вычислимости
- Вычислимая функция — это функция, которую можно вычислить с помощью алгоритма.
- Вычислимость функции может быть доказана в системе доказательств, такой как арифметика Пеано.
-
Тезис Черча-Тьюринга
- Согласно тезису Черча-Тьюринга, любая функция, вычисляемая с помощью процедуры, удовлетворяющей трем свойствам, является вычислимой.
- Тезис не может быть доказан формально, но его эквивалентность различным моделям вычислений подтверждена.
-
Доказуемая полнота
- Функция, вычислимость которой доказана, называется доказуемо полной.
- Множество доказуемо полных функций рекурсивно перечислимо.
-
Рекурсивные функции
- Рекурсивные функции определяются через рекурсивные определения, которые избегают бесконечных рекурсий.
- Каждая функция, определенная рекурсивным образом, вычислима.
-
Невычислимые функции
- Множество вычислимых функций конечно, но существуют функции, которые не могут быть вычислены.
- Примеры включают функции, которые выводят цифры невычислимых чисел, и множество конечных функций для натуральных чисел.
-
Проблема остановки
- Проблема остановки — это вопрос о том, существует ли эффективный метод определения истинности математических утверждений.
- Тьюринг и Черч показали, что эта проблема не может быть решена эффективно.
-
Расширения вычислимости
- Относительная вычислимость позволяет рассматривать функции относительно произвольных множеств натуральных чисел.
- Теория высшей рекурсии изучает множества, которые могут быть вычислены с помощью итераций перехода Тьюринга.
- Гипервычисления исследуют модели вычислений, выходящие за рамки обычных вычислений по Тьюрингу.