- Главная
- Математика
- Машина Тьюринга
Содержание
- 3. Всякая функция вычисляемая по Тьюрингу является частично рекурсивной. Это будет сделано на основе приема, распространенного в
- 4. Курт Фри́дрих Гёдель (нем. Kurt Friedrich Gödel; 28 апреля 1906, Брюнн, Австро-Венгрия — 14 января 1197,
- 5. Нумерация Гёделя — это функция g, сопоставляющая каждому объекту некоторого формального языка её номер. С её
- 6. Частично рекурсивная функция определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции и примитивной рекурсии добавляется
- 7. Легко понять, что любая примитивно рекурсивная функция является частично рекурсивной, так как по определению операторы для
- 8. Термины «частично рекурсивная функция» и «общерекурсивная функция» прижились в силу исторических причин и по сути являются
- 9. Алгоритмическая проблема — это проблема, в которой требуется найти единый метод (алгоритм) для решения бесконечной серии
- 10. Понятие нумерации алгоритмов — важное средство для их исследования, в частности для доказательств несуществования единого алгоритма
- 11. Понятие нумерации алгоритмов — важное средство для их исследования, в частности для доказательств несуществования единого алгоритма
- 13. Скачать презентацию
Всякая функция вычисляемая по Тьюрингу является частично рекурсивной. Это будет сделано
Всякая функция вычисляемая по Тьюрингу является частично рекурсивной. Это будет сделано
Курт Фри́дрих Гёдель (нем. Kurt Friedrich Gödel; 28 апреля 1906, Брюнн, Австро-Венгрия — 14 января 1197, Принстон, Нью-Джерси) — австрийский логик, математик и философ математики,
Курт Фри́дрих Гёдель (нем. Kurt Friedrich Gödel; 28 апреля 1906, Брюнн, Австро-Венгрия — 14 января 1197, Принстон, Нью-Джерси) — австрийский логик, математик и философ математики,
Гёдель, Курт
Нумерация Гёделя — это функция g, сопоставляющая каждому объекту некоторого формального языка её номер. С
Нумерация Гёделя — это функция g, сопоставляющая каждому объекту некоторого формального языка её номер. С
Нумерация Гёделя была применена Гёделем в качестве инструмента для доказательства неполнотыформальной арифметики.
Нумерация Гёделя
Частично рекурсивная функция определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции
Частично рекурсивная функция определяется аналогично примитивно рекурсивной, только к двум операторам суперпозиции
Оператор минимизации аргумента. Пусть — функция от n натуральных переменных. Тогда результатом применения оператора минимума аргумента к функции называется функция от переменной, задаваемая следующим определением:
, при условии То есть функция возвращает минимальное значение последнего аргумента функции , при котором её значение равно 0.Частично рекурсивные функции для некоторых значений аргумента могут быть не определены, так как оператор минимизации аргумента не всегда корректно определён, поскольку функция может быть не равной нулю ни при каких значениях аргументов. С точки зрения императивного программирования, результатом частично рекурсивной функции может быть не только число, но и исключение или уход в бесконечный цикл, соответствующие неопределённому значению.
Частично рекурсивная функция
Легко понять, что любая примитивно рекурсивная функция является частично рекурсивной, так
Легко понять, что любая примитивно рекурсивная функция является частично рекурсивной, так
Также понятно, что примитивно рекурсивная функция определена везде и поэтому является общерекурсивной функцией (у примитивно рекурсивной функции нет повода «зависать», так как при её построении используются операторы, определяющие везде определённые функции).
Довольно сложно доказать существование и привести пример общерекурсивной функции, не являющейся примитивно рекурсивной. Одним из популярных примеров является функция Аккермана. Другой пример общерекурсивной функции, не являющейся примитивно рекурсивной, строится диагональным методом Кантора из универсальной функции для множества одноместных примитивно рекурсивных функций.
Как было показано Гёделем, частично рекурсивные функции совпадают с множеством вычислимых функций
Свойства
Термины «частично рекурсивная функция» и «общерекурсивная функция» прижились в силу исторических
Термины «частично рекурсивная функция» и «общерекурсивная функция» прижились в силу исторических
История возникновения названия
Алгоритмическая проблема — это проблема, в которой требуется найти единый метод
Алгоритмическая проблема — это проблема, в которой требуется найти единый метод
Математики в начале XX в. столкнулись с тем, что для некоторых массовых проблем не удается подобрать общий алгоритм для их решения. В связи с этим возникла необходимость дать точное определение самому понятию алгоритма. Мы познакомились с несколькими способами такого уточнения, и в настоящем параграфе приведем примеры алгоритмически неразрешимых массовых проблем. Сначала в качестве понятия, уточняющего понятие алгоритма, будем использовать понятие машины Тьюринга. Затем рассмотрим проблему алгоритмической разрешимости в рамках общей теории алгоритмов.
Неразрешимые алгоритмические проблемы
Понятие нумерации алгоритмов — важное средство для их исследования, в частности
Понятие нумерации алгоритмов — важное средство для их исследования, в частности
Поскольку любой алгоритм можно задать конечным описанием (словом) (например, в конечном алфавите знаков, используемых при наборе математических книг), а множество всех конечных слов в фиксированном конечном алфавите счетно, то множество всех алгоритмов счетно. Это означает наличие взаимно-однозначного соответствия между множеством NN
натуральных чисел и множеством всех алгоритмов, рассматриваемым как подмножество множества Al∗Al∗
всех слов в алфавите AlAl
, выбранном для описания алгоритмов (φ:N→Al∗)(φ:N→Al∗)
. Такая функция называется нумерацией алгоритмов. Если φ(n)=Aφ(n)=A
, то число nn
называется номером алгоритма AA
. Из взаимной однозначности отображения φφ
следует существование обратной функции φ−1φ−1
, восстанавливающей по описанию алгоритма AnAn
его номер в этой нумерации φ−1(An)=nφ−1(An)=n
. Очевидно, что различных нумераций много.
Нумерация всех алгоритмов является одновременно и нумерацией всех вычислимых функций в следующем смысле: номер функции ff
— это номер некоторого алгоритма, вычисляющего ff
. Ясно, что в любой нумерации всякая функция будет иметь бесконечное множество различных номеров.
Существование нумераций позволяет работать с алгоритмами как с числами. Это особенно удобно при исследовании алгоритмов над алгоритмами. Отсутствие именно таких алгоритмов часто приводит к алгоритмически неразрешимым проблемам.
Нумерация алгоритмов
Понятие нумерации алгоритмов — важное средство для их исследования, в частности
Понятие нумерации алгоритмов — важное средство для их исследования, в частности
Поскольку любой алгоритм можно задать конечным описанием (словом) (например, в конечном алфавите знаков, используемых при наборе математических книг), а множество всех конечных слов в фиксированном конечном алфавите счетно, то множество всех алгоритмов счетно. Это означает наличие взаимно-однозначного соответствия между множеством NN
натуральных чисел и множеством всех алгоритмов, рассматриваемым как подмножество множества Al∗Al∗
всех слов в алфавите AlAl
, выбранном для описания алгоритмов (φ:N→Al∗)(φ:N→Al∗)
. Такая функция называется нумерацией алгоритмов. Если φ(n)=Aφ(n)=A
, то число nn
называется номером алгоритма AA
. Из взаимной однозначности отображения φφ
следует существование обратной функции φ−1φ−1
, восстанавливающей по описанию алгоритма AnAn
его номер в этой нумерации φ−1(An)=nφ−1(An)=n
. Очевидно, что различных нумераций много.
Нумерация всех алгоритмов является одновременно и нумерацией всех вычислимых функций в следующем смысле: номер функции ff
— это номер некоторого алгоритма, вычисляющего ff
. Ясно, что в любой нумерации всякая функция будет иметь бесконечное множество различных номеров.
Существование нумераций позволяет работать с алгоритмами как с числами. Это особенно удобно при исследовании алгоритмов над алгоритмами. Отсутствие именно таких алгоритмов часто приводит к алгоритмически неразрешимым проблемам.
Другие неразрешимые проблемы