Маккарти формализм - McCarthy Formalism

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

Введение

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

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

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

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

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

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

«Практические компьютерные языки не поддаются формальной математической обработке - они не предназначены для упрощения доказательства теорем о процедурах, которые они описывают. В статье Маккарти [1963] мы находим формализм, который усиливает практический аспект концепция рекурсивной функции, сохраняя и улучшая ее математическую ясность. ¶ Маккарти вводит «условные выражения» формы

f = (если п₁ тогда е₁ еще е₂)

где е_я выражения и п₁ это утверждение (или уравнение), которое может быть верным или ложным. ¶ Это выражение означает

Видишь ли, если п₁ правда; если да, то ценность ж дан кем-то е₁.

ЕСЛИ p1 ложно, значение ж дан кем-то е₂.

Это условное выражение. . . также имеет силу оператора минимизации. . ..

Формализм Маккарти подобен общей рекурсивной (Клини) системе, поскольку основан на некоторых основных функциях, композиции и равенстве, но только условное выражение заменяет примитивно-рекурсивную схему и оператор минимизации »(Minsky 1967: 192). -193)

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

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

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

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

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

"Функция

φ

является примитивно рекурсивный в

ψ 1, ..., ψ k

(кратко Ψ), если существует конечная последовательность

φ 1, ..., φ k

функций (вхождений) ... таких, что каждая функция последовательности является одной из функций Ψ (предполагаемые функции), или начальная функция, или непосредственная зависимость от предыдущих функций, а последняя функция

φ k

является

φ

. »(Kleene 1952: 224).

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

Минский (вверху) описывает оператор с двумя регистрами. Демонстрация того, что вложенный ЕСЛИ-ТО-ЕЩЕ - "заявление о случае "(или" оператор переключения ") - это примитивно рекурсивный можно найти в Kleene 1952: 229^[3] at "#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).

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

Заметки

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

использованная литература

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

[1] Минский (1967) не включает тождественный оператор в свое описание примитивные рекурсивные функции. Почему это так, неизвестно.

[2] Различные авторы используют разные названия этой операции. Клини называет это: "схема определение подстановкой. Выражение для неоднозначного значения φ получается подстановкой выражений для неоднозначных значений χ₁,. . ., χ_м для переменных ψ. . .. функция φ, определенная применением этой схемы, мы иногда пишем как S_м^п(ψ, ₁,. . ., χ_м. »(Kleene 1952: 220). Кнут называет это« важнейшим замена операция (иногда называемая назначение или замена) ", и он символизирует это стрелкой" ← ", например," m ← n "означает значение переменной м заменяется текущим значением переменной п"(ср. Knuth 1973: 3).

[3] 5 примитивных "схем" рекурсии Клини включают следующее:
нулевая константа: 0 или может быть 0 ()
преемник: $S (0) = "1", S (1) = "2",$ и т.п.
проекция: $U я п (Икс 1, ..., Икс п) = Икс я$ , то $Икс я$ - "параметры", фиксированные на протяжении всего расчета, и $U я п$ спроецировать один из них, обозначение $π я п (Икс 1, ..., Икс п) = Икс я$ также используется.
замена $φ (Икс 1, ..., Икс п) = ψ (χ 1 (Икс 1, ..., Икс п), ..., χ м (Икс 1, ..., Икс п))$
примитивная рекурсия; см. Kleene 1952: 219.

[4] нулевая константа: 0 или может быть 0 ()

[5] преемник: $S (0) = "1", S (1) = "2",$ и т.п.

[6] проекция: $U я п (Икс 1, ..., Икс п) = Икс я$ , то $Икс я$ - "параметры", фиксированные на протяжении всего расчета, и $U я п$ спроецировать один из них, обозначение $π я п (Икс 1, ..., Икс п) = Икс я$ также используется.

[7] замена $φ (Икс 1, ..., Икс п) = ψ (χ 1 (Икс 1, ..., Икс п), ..., χ м (Икс 1, ..., Икс п))$

[8] примитивная рекурсия; см. Kleene 1952: 219.

[9] нулевая константа: 0 или может быть 0 ()

[10] преемник: $S (0) = "1", S (1) = "2",$ и т.п.

[11] проекция: $U я п (Икс 1, ..., Икс п) = Икс я$ , то $Икс я$ - "параметры", фиксированные на протяжении всего расчета, и $U я п$ спроецировать один из них, обозначение $π я п (Икс 1, ..., Икс п) = Икс я$ также используется.

[12] замена $φ (Икс 1, ..., Икс п) = ψ (χ 1 (Икс 1, ..., Икс п), ..., χ м (Икс 1, ..., Икс п))$

[13] примитивная рекурсия; см. Kleene 1952: 219.

[1]

[2]

[3]