Частичная комбинаторная алгебра ⇐ Васина Википедия

[wiki_en]

В теоретической информатике и математической логике «частичная комбинаторная алгебра» (PCA) - это алгебраическая структура, которую можно рассматривать как абстракцию модели вычислений. Определение PCAS использует идею из комбинаторной логики. PCA используются для определения топоз реализации.

== Определение ==

«Частичная примененная структура»
«Термины»
* Постоянная a \ in < /math> - это выражение,
* Переменная (из некоторого фиксированного, счетного бесконечного набора переменных) является выражением,
* Если e_1 и e_2 является выражениями, то e_1 e_2 является выражением.

Термин «закрыт», если он не содержит переменных. Закрытый термин может быть «оценен» естественным образом: постоянная a \ in оценивает себя, и если термины e_1 и e_2 < /Математика> соответственно оценивать a_1 и a_2 , затем e_1 e_2 оценивает до a_1 A_2 , если это определено. Обратите внимание, что оценка является частичной операцией, поскольку не все приложения определены. Операция замены также определяется естественным образом: если t - термин, x является переменной, а u - еще один термин, t [u/x] обозначает термин t со всеми событиями x , замененный на u .

Частичная примененная структура '' '' '', как говорят, «комбинаторно завершено»
* Для всех a_0, \ dots, a_ {n-1} \ in , приложение a_0 \ dots a_ {n-1} определено, и
* Для всех a_0, \ dots, a_n \ in , оценка t [a_0/x_0, \ dots, a_n/x_n] определяется тогда и только тогда, когда < Математика> a_0 \ dots a_n определяется, и если они определены, они равны как элементы a .

«Частичная комбинаторная алгебра» ''
Неофициально, комбинаторное условие полноты требует аналога операции абстракции из исчисления Lambda, чтобы существовать внутри PCA.

== Примечания ==


< /ссылки>



Подробнее: https://en.wikipedia.org/wiki/Partial_c ... ry_algebra