McCarthy Formalism
-
Формализм Маккарти
- Джон Маккарти предложил формализм для описания рекурсивных функций в 1963 году.
- Формализм использует конструкцию IF-THEN-ELSE и четыре оператора: zero, successor, equality of numbers и composition.
- Условный оператор заменяет примитивную рекурсию и mu-оператор.
-
Объяснение Мински
- Марвин Мински описал формализм в своей книге «Computation: Finite and Infinite Machines» в 1967 году.
- Мински использовал операторы zero, successor, equality of numbers и composition для демонстрации.
- Он показал, как вывести функцию предшественника и минимизировать оператор для «общей» рекурсии.
-
Расширение IF-THEN-ELSE до CASE оператора
- Стивен Клайн определил примитивную рекурсивную функцию в 1952 году.
- Клайн показал, что вложенный IF-THEN-ELSE является примитивно рекурсивным.
- CASE оператор ведет себя как логический мультиплексор и является расширением двух-CASE логического оператора.
-
Требования к CASE оператору
- CASE оператор должен быть взаимно исключающим и коллективно исчерпывающим.
- Эти требования следуют из детерминизма пропозициональной логики.
- Для корректной реализации требуются таблицы истинности и карты Карно.
-
Определение по случаям
- Boolos-Burgess-Jeffrey доказали, что процессы подстановки, отношения, отрицания, конъюнкции, дизъюнкции, квантификации и определения по случаям могут создавать новые примитивно рекурсивные функции.