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

Από τη Βικιπαίδεια, την ελεύθερη εγκυκλοπαίδεια
Πήδηση στην πλοήγηση Πήδηση στην αναζήτηση

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

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

Παραπομπές[Επεξεργασία | επεξεργασία κώδικα]

  1. Πάνος Ροντογιάννης. «Λάμδα Λογισμός» (PDF). Πανεπιστήμιο Αθηνών. Ανακτήθηκε στις 30 Νοεμβρίου 2014.  Unknown parameter |coauthors= ignored (|author= suggested) (βοήθεια)
  2. Κολλιόπουλος, Σταύρος. «Σημειώσεις μαθήματος "Θεωρία Υπολογισμού"» (PDF). Πανεπιστήμιο Αθηνών. Ανακτήθηκε στις 30 Νοεμβρίου 2014. 
  3. Hinze, Ralf (January 2005). «Theoretical Pearl - Church numerals, twice!». Journal of Functional Programming 15 (1): 1–13. doi:10.1017/S0956796804005313. http://www.cs.ox.ac.uk/ralf.hinze/publications/Church.pdf. 
Στο λήμμα αυτό έχει ενσωματωθεί κείμενο από το λήμμα Church encoding της Αγγλικής Βικιπαίδειας, η οποία διανέμεται υπό την GNU FDL και την CC-BY-SA 3.0. (ιστορικό/συντάκτες).