1993 | OriginalPaper | Chapter
Computability and Combinators
Author : Erwin Engeler
Published in: Foundations of Mathematics
Publisher: Springer Berlin Heidelberg
Included in: Professional Book Archive
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
In the present section we want briefly to go into the connections between combinatory algebra and logic, and recursion theory. This will serve as a demonstration that concept formation in combinatory algebra has achieved its declared aim. We started out from the idea of capturing “algorithmic rules” by objects in an algebraic structure. But this is known to be also accomplished by the notion of a partially-recursive function; this is Church’s thesis. It therefore remains to show that each partially-recursive function corresponds to a combinator, which, applied to suitable numerical objects, does the same job.