Computability and Combinators

Erwin Engeler
Additional contact information
Erwin Engeler: ETH-Zentrum, Mathematikdepartment

Chapter § 5 in Foundations of Mathematics, 1993, pp 94-100 from Springer

Abstract: Abstract 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.

Keywords: Normal Form; Recursive Function; Combinatory Logic; Recursion Theory; Number Object (search for similar items in EconPapers)
Date: 1993
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:sprchp:978-3-642-78052-3_14

Ordering information: This item can be ordered from
http://www.springer.com/9783642780523

DOI: 10.1007/978-3-642-78052-3_14

Access Statistics for this chapter

More chapters in Springer Books from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().