stringtranslate.com

Маккарти Формализм

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

Введение

Понятие Маккарти оусловное выражение

Маккарти (1960) описал свой формализм следующим образом: [1]

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

Объяснение Мински «формализма»

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

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

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

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

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

В своей работе «Введение в метаматематику» 1952 года Стивен Клини дает определение примитивной рекурсивной функции:

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

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

Минский (выше) описывает оператор с двумя вариантами. Демонстрацию того, что вложенный IF-THEN-ELSE — « оператор case » (или «оператор switch») — является примитивно рекурсивным, можно найти в Kleene 1952:229 [4] в «#F ('mutually-exclusive predicates')». Оператор CASE ведет себя как логический мультиплексор и является просто расширением более простого логического оператора с двумя вариантами, иногда называемого AND-OR-SELECT (подробнее см. в Propositional formula ). Оператор CASE для трех вариантов можно было бы словесно описать так: «Если X — это CASE 1, то DO "p", иначе если X — это CASE 2, то do "q", иначе если X — это CASE "3", то do "r", иначе do "default".

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

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

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

Смотрите также

Примечания

  1. ^ Маккарти 1960.
  2. ^ Минский (1967) не включает оператор тождества в свое описание примитивных рекурсивных функций . Почему это так, неизвестно.
  3. ^ Различные авторы используют различные названия для этой операции. Клини называет ее: «схема определения путем подстановки . Выражение для неоднозначного значения φ получается путем подстановки выражений для неоднозначных значений χ 1 , . . ., χ m для переменных ψ . . .. функцию φ, определенную применением этой схемы, мы иногда записываем как st S m n (ψ, 1 , . . ., χ m ». (Клини 1952:220). Кнут называет ее «важнейшей операцией замены (иногда называемой присваиванием или подстановкой )», и он символизирует ее стрелкой «←», например, «m ← n» означает, что значение переменной m должно быть заменено текущим значением переменной n » (ср. Кнут 1973:3).
  4. ^ Пять примитивных рекурсивных «схем» Клини включают следующее:
    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. замена φ( Икс 1 , ..., Икс п ) = ψ(Х 1 ( Икс 1 , ..., Икс п ), ..., х м ( Икс 1 , ..., Икс п ))
    5. примитивная рекурсия; см. Kleene 1952:219.

Ссылки