## Abstract

From every partial combinatory algebra script A sign we construct another partial combinatory algebra a-lim(script A sign). In a-lim(script A sign), every representable partial numerical function φ(n) is exactly of the form lim_{t}ζ(t,n) for some representable partial numerical function ζ(t,n) of script A sign. The partial combinatory algebra a-lim(script A sign) is a quotient of script A sign by a partial equivalence relation, and is equipped with a limit structure in the sense that each element of a-lim(script A sign) is the limit of a countable sequence of script A sign-elements. In this paper, we discuss the limit structures for script A sign in terms of Barendregt's range property (if the range of a combinator is finite, then it is a singleton). Moreover, we repeat the construction a-lim(-) transfinite times to interpret infinitary λ-calculi. Finally, we attempt to interpret type-free λμ-calculus by introducing another partial applicative structure which has an asynchronous application operator that allows a parallel limit operation.

Original language | English |
---|---|

Pages (from-to) | 199-220 |

Number of pages | 22 |

Journal | Theoretical Computer Science |

Volume | 311 |

Issue number | 1-3 |

DOIs | |

Publication status | Published - 2004 Jan 23 |

## Keywords

- Limiting recursive
- Partial equivalence relation
- Realizability interpretation
- λμ-calculus

## ASJC Scopus subject areas

- Theoretical Computer Science
- Computer Science(all)