Κωδικοποίηση Τσερτς

Στα μαθηματικά η κωδικοποίηση Τσερτς (Αγγλικά: Church encoding) είναι ένα μέσο αναπαράστασης δεδομένων και τελεστών με λάμδα-λογισμό (συμβολίζεται ως λ-λογισμός ή στα αγγλικά: λ-calculus). Τα δεδομένα και οι τελεστές δημιουργούν μια μαθηματική δομή η οποία ενσωματώνεται στον λ-λογισμό. Τα αριθμοειδή Τσερτς (ή και αριθμιακά Τσερτς, στα Αγγλικά: Church numerals) είναι αναπαραστάσεις των φυσικών αριθμών χρησιμοποιώντας λάμδα συμβολισμούς. Οι αναπαραστάσεις αυτές έχουν πάρει από το όνομα του Αλόνζο Τσερτς ο οποίος πρώτη φορά κωδικοποίησε δεδομένα με αυτή τη μορφή (χρησιμοποιώντας λ-λογισμό).

Οι όροι συνήθως θεωρούνται πρωτογενείς (Αγγλικά: primitive) σε διαφορετική αναπαράσταση (όπως ακέραιοι, λογικοί τύποι, ζεύγη ή λίστες) και αντιστοιχίζονται σε συναρτήσεις ανώτερου βαθμού (Αγγλικά: high order functions) κάτω από την κωδικοποίηση Τσερτς. Σύμφωνα με την θέση Τσερτς-Τούρνινγκ  αποδεικνύεται ότι κάθε υπολογίσιμος τελεστής (και οι παράμετροί του) μπορούν να αναπαρασταθούν με την κωδικοποίηση του Τσερτς. Στον λ-λογισμό χωρίς τύπους ο μόνος πρωτογενής τύπος είναι η συνάρτηση.

Παραπομπές

Θεωρία υπολογισμού
Λ-λογισμός