Computability Via The Lambda Calculus with Patterns

Bodin Skulkiat, Pimpen Vejjajiva, Mark Hall

Abstract


We introduce a concept of \textbf{computability relative to a structure}, which specifies which functions on the universe of a first-order structure are computable, using the lambda calculus with patterns. In doing so, we add a new congruence, $\equiv_\mathfrak{A}$, called \textbf{congruence in a structure} to identify two syntactically different terms which represent the same element of the universe. We then show that, with the introduction of the new congruence, all the basic properties of the original lambda calculus with patterns still hold, including the Church-Rosser theorem.

Full Text: PDF

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.

Journal of Mathematics Research   ISSN 1916-9795 (Print)   ISSN 1916-9809 (Online)

Copyright © Canadian Center of Science and Education

To make sure that you can receive messages from us, please add the 'ccsenet.org' domain to your e-mail 'safe list'. If you do not receive e-mail in your 'inbox', check your 'bulk mail' or 'junk mail' folders.