Hesaplanabilir İşlevler için Mantık - Logic for Computable Functions

Hesaplanabilir İşlevler için Mantık (LCF) etkileşimlidir otomatik teorem kanıtlayıcı geliştirildi Stanford ve Edinburg tarafından Robin Milner ve 1970'lerin başındaki işbirlikçilerinin teorik temeline dayanarak mantık nın-nin hesaplanabilir işlevler önceden öneren Dana Scott. LCF sistemi üzerinde çalışmak, genel amaçlı Programlama dili ML kullanıcıların teoremi ispatlayan taktikler yazmasına izin vermek için cebirsel veri türleri, parametrik polimorfizm, soyut veri türleri, ve istisnalar.

Temel fikir

Sistemdeki teoremler özel bir "teorem" terimleridir soyut veri türü. Makine öğreniminin soyut veri türlerinin genel mekanizması, teoremlerin yalnızca çıkarım kuralları teorem soyut tipin işlemleriyle verilir. Kullanıcılar teoremleri hesaplamak için rastgele karmaşık ML programları yazabilir; teoremlerin geçerliliği bu tür programların karmaşıklığına bağlı değildir, ancak soyut veri türü uygulamasının sağlamlığından ve ML derleyicisinin doğruluğundan kaynaklanır.

Avantajlar

LCF yaklaşımı, bellekte prova nesnelerini depolamaya gerek kalmadan, açık ispat sertifikaları üreten sistemlere benzer güvenilirlik sağlar. Teorem veri türü, sistemin çalışma zamanı konfigürasyonuna bağlı olarak isteğe bağlı olarak prova nesneleri depolamak için kolayca uygulanabilir, böylece temel prova oluşturma yaklaşımını genelleştirir. Teoremleri geliştirmek için genel amaçlı bir programlama dili kullanma tasarım kararı, yazılan programların karmaşıklığına bağlı olarak, adım adım kanıtlar, karar prosedürleri veya teorem kanıtlayıcılar yazmak için aynı dili kullanmanın mümkün olduğu anlamına gelir.

Dezavantajları

Güvenilir bilgi işlem tabanı

Temel alınan ML derleyicisinin uygulanması, güvenilir bilgi işlem tabanı. CakeML üzerinde çalışın[1] resmi olarak doğrulanmış bir makine öğrenimi derleyicisiyle sonuçlandı ve bu endişelerin bir kısmını hafifletti.

İspat prosedürlerinin etkinliği ve karmaşıklığı

Kanıtlama teoremi, genellikle doğruluğu kapsamlı bir şekilde analiz edilen karar prosedürlerinden ve teorem kanıtlama algoritmalarından yararlanır. Bir LCF yaklaşımında bu prosedürleri uygulamanın basit bir yolu, bu tür prosedürlerin, sonucu doğrudan hesaplamak yerine, her zaman sistemin aksiyomlarından, lemlerinden ve çıkarım kurallarından sonuçlar elde etmesini gerektirir. Potansiyel olarak daha verimli bir yaklaşım, formüllerde çalışan bir işlevin her zaman doğru sonuç verdiğini kanıtlamak için yansımayı kullanmaktır.[2]

Etkiler

Sonraki uygulamalar arasında Cambridge LCF bulunmaktadır. Daha sonra sistemler, mantığı kısmi işlevler yerine toplamı kullanacak şekilde basitleştirerek HOL, HOL Işık, ve Isabelle Proof asistanı çeşitli mantıkları destekleyen. 2019 itibariyle, Isabelle kanıt asistanı hala bir LCF mantığı olan Isabelle / LCF'nin bir uygulamasını içerir.

Notlar

  1. ^ "CakeML". Alındı 2 Kasım 2019.
  2. ^ Boyer, Robert S; Moore, J Strother. Metafonksiyonlar: Bunların Doğru Olduğunu Kanıtlamak ve Yeni İspat Prosedürleri Olarak Verimli Kullanmak (PDF) (Bildiri). Teknik Rapor CSL-108, SRI Projeleri 8527/4079. s. 1–111. Alındı 2 Kasım 2019.

Referanslar