Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

В информатике и теории рекурсии McCarthy формализм (1963) из компьютера ученый Джон Маккарти уточняет понятие рекурсивных функций путем использования IF-THEN-ELSE строительства общего , информатике, вместе с четырьмя операторами примитивно рекурсивных функций : ноль , преемник, равенство чисел и состава. Условный оператор заменяет как примитивную рекурсию, так и оператор mu .

Введение [ править ]

Понятие условного выражения Маккарти [ править ]

Маккарти (1960) так описал свой формализм:

«В этой статье мы сначала описываем формализм для рекурсивного определения функций. Мы считаем, что этот формализм имеет преимущества как в качестве языка программирования, так и в качестве средства разработки теории вычислений ...
Нам понадобится ряд математических идей и обозначений, касающихся функций в целом. Большинство идей хорошо известны, но понятие условного выражения считается новым, а использование условных выражений позволяет рекурсивно определять функции новым и удобным способом ».

Объяснение Минским «формализма» [ править ]

В своей книге « Вычисления: конечные и бесконечные машины» 1967 года Марвин Мински в своем § 10.6 Условные выражения: формализм Маккарти описывает «формализм» следующим образом:

«Практические компьютерные языки не поддаются формальной математической обработке - они не предназначены для упрощения доказательства теорем о процедурах, которые они описывают. В статье Маккарти [1963] мы находим формализм, который усиливает практический аспект концепция рекурсивной функции, сохраняя и улучшая ее математическую ясность. ¶ Маккарти вводит «условные выражения» формы
f = ( если p 1, то e 1, иначе e 2 )
где e i - выражения, а p 1 - утверждение (или уравнение), которое может быть истинным или ложным. ¶ Это выражение означает
Посмотрите, истинно ли p 1 ; в таком случае значение f равно e 1 .
ЕСЛИ p1 ложно, значение f равно e 2 .
Это условное выражение. . . также имеет силу оператора минимизации. . ..
Формализм Маккарти подобен общей рекурсивной системе (Клини), поскольку основан на некоторых основных функциях, композиции и равенстве, но только условное выражение заменяет примитивно-рекурсивную схему и оператор минимизации »(Minsky 1967: 192). -193)

Минский использует в своих демонстрациях следующие операторы: [1]

  • Нуль
  • Преемник
  • Равенство чисел
  • Состав (замена, замена, уступка) [2]
  • Условное выражение

Из них он показывает, как вывести функцию- предшественницу (т. Е. УКАЗАНИЕ); с помощью этого инструмента он выводит оператор минимизации, необходимый для «общей» рекурсии , а также примитивно-рекурсивные определения.

Расширение IF-THEN-ELSE до оператора CASE [ править ]

В своем введении в мета-математику 1952 года Стивен Клини дает определение того, что значит быть примитивной рекурсивной функцией:

«Функция φ является примитивно рекурсивной в ф 1 , ..., ψ K (кратко Ф ), если существует конечная последовательность φ 1 , ..., φ к из (вхождения) функций ... таким образом, что каждая функция последовательности является либо одной из функций Ψ (предполагаемых функций), либо начальной функцией, либо непосредственной зависимостью от предыдущих функций, а последняя функция φ k - это φ ». (Клини 1952: 224)

Другими словами, учитывая «базовую» функцию (это может быть константа, например 0), примитивная рекурсия использует либо базовое, либо предыдущее значение функции для получения значения функции; примитивная рекурсия иногда называется математической индукцией

Минский (вверху) описывает оператор с двумя регистрами. Демонстрация того, что вложенный оператор IF-THEN-ELSE - « оператор case » (или «оператор переключения») - примитивно рекурсивен, можно найти в Kleene 1952: 229 [3] по адресу «#F ('взаимоисключающие предикаты' ) ". Оператор CASE ведет себя как логический мультиплексор и является просто расширением более простого логического оператора с двумя регистрами, иногда называемого И-ИЛИ-ВЫБОР (подробнее см. В Формула высказываний ). Оператор CASE для трех случаев может быть словесно описан следующим образом: «Если X - CASE 1, тогда DO« p », иначе, если X - CASE 2, затем выполнить« q », иначе, если X - CASE« 3 », затем выполнить« r »else do» дефолт".

Boolos-Burgess-Jeffrey 2002 замечают, что в конкретном случае оператор CASE или последовательность вложенных операторов IF-THEN-ELSE должны быть взаимоисключающими , что означает, что выполняется (истинно) только один «случай», и все вместе они являются исчерпывающими. , что означает, что все возможные ситуации или «случай» «покрыты». Эти требования являются следствием определенности логики высказываний ; правильная реализация требует использования таблиц истинности и карт Карно для определения и упрощения случаев; подробнее см. Формула высказываний . Авторы указывают на силу «определения по делам»:

"... в более сложных примерах определение по прецедентам значительно упрощает установление (примитивной) рекурсивности важных функций. Это происходит главным образом потому, что существует множество процессов для определения новых отношений из старых, которые, как можно показать, создают новые (примитивные) рекурсивные отношения в применении к (примитивным) рекурсивным отношениям ". (Булос-Берджесс-Джеффри 2002: 74)

Они доказывают, в частности, что процессы подстановки , отношения графа (аналогично отношению идентичности, которое извлекает (значение) определенной переменной из списка переменных), отрицания (логическое НЕ), конъюнкции (логическое И), дизъюнкция (логическое ИЛИ), ограниченная универсальная квантификация или ограниченная квантификация существования могут использоваться вместе с определением по случаям для создания новых примитивных рекурсивных функций (см. Boolos-Burgess-Jeffrey 2002: 74-77).

См. Также [ править ]

Заметки [ править ]

  1. ^ Minsky (1967) не включает тождественный оператор в свое описание примитивных рекурсивных функций . Почему это так, неизвестно.
  2. ^ Различные авторы используют разные названия для этой операции. Клини называет это: «схемой определения путем подстановки . Выражение для неоднозначного значения φ получается путем подстановки выражений для неоднозначных значений χ 1 , ..., χ m для переменных ψ.... функцию φ, определенную применением этой схемы, мы иногда пишем ast S m n (ψ, 1 , ..., χ m . »(Kleene 1952: 220). Кнут называет ее« чрезвычайно важнойоперацией замены (иногда называемой присваиванием). или замена) », и он символизирует это стрелкой« ← », например,« m ← n »означает, что значение переменной m должно быть заменено текущим значением переменной n » (см. Knuth 1973: 3).
  3. ^ 5 примитивных "схем" рекурсии Клини включают следующее:
    1. нулевая константа: 0 или может быть 0 ()
    2. преемник: S (0) = "1", S (1) = "2" и т. д.
    3. проекция: U i n ( x 1 , ..., x n ) = x i , x i - это «параметры», фиксированные на протяжении всего расчета, а U i n проецирует один из них наружу, обозначение π i n ( x 1 , ..., x n ) = x i также используется.
    4. подстановка φ ( x 1 , ..., x n ) = ψ (χ 1 ( x 1 , ..., x n ), ..., χ m ( x 1 , ..., x n ))
    5. примитивная рекурсия; см. Kleene 1952: 219.

Ссылки [ править ]

  • Джордж С. Булос , Джон П. Берджесс и Ричард С. Джеффри , 2002, Вычислимость и логика: четвертое издание , Cambridge University Press, Cambridge UK, ISBN  0-521-00758-5 в мягкой обложке.
  • Джон Маккарти (1960), Рекурсивные функции символьных выражений и их вычисление машиной, Часть I , Сообщения ACM, 3, 184-195 (апрель 1960).
  • Джон Маккарти (1963), Основы математической теории вычислений , компьютерного программирования и формальных систем, стр. 33-70.
  • Марвин Мински (1967), Вычисления: конечные и бесконечные машины , Prentice-Hall Inc, Englewood Cliffs, NJ.