[Prev][Next][Index][Thread]
references on partial comb algebras
I am looking for references to work on partial combinatory algebras,
specifically the construction of partial equivalence relation (per)
models over partial combinatory algebras.
A particular question is the trade-off between the definition that
does not require Kxy defined for all xy, and does not require
Sxyz defined when (xz)(yz) is defined, and an alternative
definition with stronger definedness conditions. With the more
restrictive definition, every HRO structure over the pca is
a (typed) combinatory algebra, but this fails with the weaker
definition. Since combinatory algebras are often useful, I wonder
whether there are any useful examples of pcas where Kxy is sometimes
undefined, and Sxyz is undefined in some case where (xz)(yz)
is defined.
Would anyone mind if I just called a structure <D,*,K,S> with
* a partial binary operation, Kxy=x, and Sxyz ~= xz(yz)
a "partial combinatory algebra"? (Here Kxy is an abbreviation
for K*x*y, etc.) The main examples of pca's, natural numbers with
recursive function application, and ordinary combinatory algebras,
satisfy this definition.
John Mitchell