Gödel makine - Gödel machine

Bir Gödel makine varsayımsal bir kendini geliştirmedir bilgisayar programı problemleri en iyi şekilde çözen.^{[açıklama gerekli ]} Yeni kodun daha iyi bir strateji sağladığını ispatlayabildiğinde kendi kodunu yeniden yazdığı yinelemeli bir kendini geliştirme protokolü kullanır.^[1]^[2] Makine tarafından icat edildi Jürgen Schmidhuber (ilk olarak 2003'te önerildi^[3]), ancak adını alır Kurt Gödel matematiksel teorilere ilham veren.^[4]

Gödel makinesi, aşağıdaki konularla uğraşırken sıklıkla tartışılır. meta öğrenme, "öğrenmeyi öğrenmek" olarak da bilinir. Uygulamalar, insan tasarım kararlarının otomatikleştirilmesini ve birden çok ilgili görev arasında bilgi aktarımını içerir ve daha sağlam ve genel öğrenme mimarilerinin tasarımına yol açabilir.^[5] Teorik olarak mümkün olsa da, tam bir uygulama yaratılmamıştır.^[6]

Gödel makinesi genellikle Marcus Hutter 's AIXItl için başka bir resmi şartname yapay genel zeka. Schmidhuber, Gödel makinesinin, ilk alt programı olarak AIXItl'i uygulayarak başlayabileceğine ve arama kodu için başka bir algoritmanın daha iyi olacağına dair kanıt bulduktan sonra kendi kendini değiştirebileceğine işaret ediyor.^[7]

Sınırlamalar

Bir bilgisayar tarafından çözülen geleneksel sorunlar yalnızca bir giriş gerektirir ve bir miktar çıktı sağlar. Bu tür bilgisayarların başlangıç algoritmaları donanımla bağlantılıydı.^[8] Bu, dinamik doğal ortamı hesaba katmıyor ve bu nedenle Gödel makinesinin üstesinden gelmesi gereken bir hedefti.

Ancak Gödel makinesinin kendi sınırları vardır. Gödel'e göre İlk Eksiklik Teoremi, aritmetiği kapsayan herhangi bir biçimsel sistem ya kusurludur ya da sistemde kanıtlanamayan ifadelere izin verir. Bu nedenle, sınırsız hesaplama kaynaklarına sahip bir Gödel makinesi bile, etkililiğini kanıtlayamayacağı kendi kendine iyileştirmeleri görmezden gelmelidir.^[3]

İlgi değişkenleri

Gödel makinesinin çalışma süresinde özellikle yararlı olan üç değişken vardır.^[3]

Bir aralar ${ displaystyle t}$ , değişken ${ displaystyle { text {zaman}}}$ ikili eşdeğerine sahip olacak ${ displaystyle t}$ . Bu, makinenin çalışma süresi boyunca istikrarlı bir şekilde artar.

Hiç giriş Gödel makinesi için doğal ortamdan kastedilen değişken olarak depolanır ${ displaystyle x}$ . Muhtemelen durum böyle ${ displaystyle x}$ farklı değişken değerleri için farklı değerler tutacak ${ displaystyle { text {zaman}}}$ .

Gödel makinesinin çıktıları değişken olarak saklanır. ${ displaystyle y}$ , nerede ${ displaystyle y (t)}$ bir anda çıktı bit dizesi olabilir ${ displaystyle t}$ .

Herhangi bir zamanda ${ displaystyle t}$ , nerede ${ displaystyle (1 leq t leq T)}$ amaç, gelecekteki başarıyı veya faydayı maksimize etmektir. Tipik fayda fonksiyonu kalıbı takip eder ${ displaystyle u (s, mathrm {Zarf}): S times E rightarrow mathbb {R}}$ :

{ displaystyle u (s, mathrm {Env}) = E _ { mu} { Bigg [} toplamı _ { tau = { text {zaman}}} ^ {T} r ( tau) orta s, mathrm {Zarf} { Bigg]}}

nerede ${ displaystyle r (t)}$ gerçek değerli bir ödül girdisidir (içinde kodlanmıştır ${ displaystyle s (t)}$ ) zamanda ${ displaystyle t}$ , ${ displaystyle E _ { mu} [ cdot mid cdot]}$ bazı olası bilinmeyen dağıtımlarla ilgili koşullu beklenti operatörünü belirtir ${ displaystyle mu}$ aset'dan ${ displaystyle M}$ olası dağılımların ( ${ displaystyle M}$ çevrenin olası olasılıklı reaksiyonları hakkında bilineni yansıtır) ve yukarıda belirtilen ${ displaystyle { text {zaman}} = operatöradı {saat}}$ devletin bir işlevidir ${ displaystyle s}$ mevcut döngüyü benzersiz şekilde tanımlayan.^[3] Uygun eylemlerle beklenen ömrü uzatma olasılığını hesaba kattığımızı unutmayın.^[3]

İspat teknikleri tarafından kullanılan talimatlar

Aşağıdaki altı kanıtı değiştirme talimatının doğası, kanıta yanlış bir teoremi eklemeyi imkansız kılar, böylece kanıt doğrulamasını önemsiz hale getirir.^[3]

get-axiom (n)

Ekler n-nci aksiyom mevcut teorem dizisine bir teorem olarak. Aşağıda ilk aksiyom şeması verilmiştir:

Donanım Aksiyomları makinenin bileşenlerinin bir döngüden diğerine nasıl değişebileceğini resmi olarak belirtin.
Ödül Aksiyomları tanımla hesaplama maliyeti donanım talimatı ve çıktı eylemlerinin fiziksel maliyeti. İlgili Aksiyomlar ayrıca Gödel makinesinin ömrünü şu şekilde tanımlar: skaler tüm ödülleri / maliyetleri temsil eden miktarlar.
Çevre Aksiyomları yeni girişlerin şeklini kısıtlayın x önceki girdi dizilerine göre çevreden üretilir y.
Belirsizlik Aksiyomları / Dizi Manipülasyon Aksiyomları aritmetik, analiz için standart aksiyomlardır, olasılık teorisi ve Gödel makinesinde gelecekteki değişken değerlerle ilgili ispatların oluşturulmasına izin veren dizi manipülasyonu.
İlk Durum Aksiyomları Başlangıç durumunun bir kısmının veya tamamının nasıl yeniden yapılandırılacağı hakkında bilgi içerir.
Fayda Aksiyomları genel hedefi fayda işlevi biçiminde tanımlayın sen.

uygulama kuralı (k, m, n)

Dizini alır k bir çıkarım kuralının (örneğin Modus geçiş ücretleri, Modus ponens ) ve bunu daha önce kanıtlanmış iki teoreme uygulama girişimleri m ve n. Ortaya çıkan teorem daha sonra ispata eklenir.

silme teoremi (m)

Dizinde depolanan teoremi siler m mevcut kanıtta. Bu, gereksiz ve gereksiz teoremlerin neden olduğu depolama kısıtlamalarının azaltılmasına yardımcı olur. Silinen teoremlere artık yukarıdakiler tarafından referans verilemez uygulama kuralı işlevi.

set-switchprog (m, n)

Değiştirir Switchprog S^p_{m: n}boş olmaması koşuluyla alt dize nın-nin S^p.

Kontrol()

Prova arama hedefine ulaşılıp ulaşılmadığını doğrular. Bir hedef teorem, mevcut aksiyomatlı fayda fonksiyonunun verildiğini belirtir sen (Öğe 1f), bir anahtarın faydası p mevcut switchprog'a, yürütmeye devam etme faydasından daha yüksek olacaktır. p (bu, alternatif anahtar programları aramaya devam eder).^[3] Bu, Gödel Makinesi için kodu çözülmüş kontrol () işlevinin aşağıdaki açıklamasında gösterilmektedir:

{ displaystyle D_ {KA} = { frac {d _ { text {gözenek}}} {3}} u = { frac {d _ { text {gözenek}}} {3}} { sqrt { frac {8 kappa NT} { pi M_ {A}}}}}

durum2 teoremi (m, n)

İki argüman alır, m ve nve içeriğini dönüştürmeye çalışır S_{m: n} bir teoremin içine.

Örnek uygulamalar

Zaman sınırlı NP-zor optimizasyon

Gödel makinesine ilk girdi, çok sayıda bağlı bir grafiğin temsilidir. düğümler çeşitli uzunluklarda kenarlarla bağlanmıştır. Verilen süre içinde T bulmalı döngüsel tüm düğümleri bağlayan yol. Tek gerçek değerli ödül, zamanında gerçekleşecek T. Şimdiye kadar bulunan en iyi yolun uzunluğuna bölünerek 1'e eşittir (hiçbiri bulunamadıysa 0). Başka giriş yok. Beklenen ödülü en üst düzeye çıkarmanın yan ürünü, ilk önyargı göz önüne alındığında, sınırlı süre içinde bulunabilen en kısa yolu bulmaktır.^[3]

Hızlı teorem kanıtlama

> 2 tamsayısının bile iki asal sayının toplamı olduğunu olabildiğince çabuk kanıtlayın veya çürütün (Goldbach varsayımı ). Ödül 1 /t, nerede t bu tür ilk kanıtı üretmek ve doğrulamak için gereken süredir.^[9]

Sınırlı kaynaklarla beklenen ödülü en üst düzeye çıkarmak

Bir bilişsel en az 1 ihtiyacı olan robot litre Saatte benzin, kısmen bilinmeyen bir ortamla etkileşime girerek, bazen tankına yakıt ikmali yapmak için gizli, sınırlı benzin depoları bulmaya çalışıyor. Ömrü ile orantılı olarak ödüllendirilir ve en fazla 100 yıl sonra veya tankı boşalır boşalmaz veya uçurumdan düşer vb. Ölür. olasılığa dayalı çevresel reaksiyonlar başlangıçta bilinmemekle birlikte, hesaplanması zor çevresel reaksiyonların olası olmadığı aksiyomatize edilmiş Speed Prior'dan örneklendiği varsayılmaktadır. Bu, optimuma yakın tahminler yapmak için hesaplanabilir bir stratejiye izin verir. Beklenen ödülü en üst düzeye çıkarmanın bir yan ürünü, beklenen ömrü en üst düzeye çıkarmaktır.^[3]

Ayrıca bakınız

Gödel'in eksiklik teoremleri

Referanslar

^ Mahmud, M. M. Hassan (2008). Evrensel Transfer Öğrenimi. sayfa 16–18. ISBN 9780549909880.
^ Anderson, Michael L .; Tim Oates (Bahar 2007). "Metareasoning ve metal öğrenmede son araştırmaların bir incelemesi". AI Dergisi. 28 (1): 7.
^ ^a ^b ^c ^d ^e ^f ^g ^h ^ben Schmidhuber, Jürgen (Aralık 2006). Gödel Makineleri: Kendi Kendine Yönelik ¨ Kendi Kendini İyileştirmeleri Sağlayacak Şekilde Optimum Sağlayan Evrensel Sorun Çözücüler (PDF). Alındı 10 Kasım 2014.
^ "Gödel makinesi".
^ Schaul, Tom; Schmidhuber, Juergen (2010). "Metal öğrenme". Scholarpedia. 5 (6): 4650. Bibcode:2010SchpJ ... 5.4650S. doi:10.4249 / alimpedia.4650. Alındı 10 Kasım 2014.
^ Steunebrink, Bas R .; Schmidhuber, Jürgen (2011). Gödel Makine Uygulamaları Ailesi. Bilgisayar Bilimlerinde Ders Notları. 6830. s. 275–280. CiteSeerX 10.1.1.300.3076. doi:10.1007/978-3-642-22887-2_29. ISBN 978-3-642-22886-5.
^ Schmidhuber, Jürgen (5 Mart 2009). "Gödel'de Nihai Biliş" (PDF). Bilişsel Hesaplama. 1 (2): 177–193. CiteSeerX 10.1.1.218.3323. doi:10.1007 / s12559-009-9014-y. Alındı 13 Kasım 2014.
^ Schmidhuber, Jürgen (5 Mart 2009). "Gödel'de Nihai Biliş" (PDF). Bilişsel Hesaplama. 1 (2): 177–193. CiteSeerX 10.1.1.218.3323. doi:10.1007 / s12559-009-9014-y. Alındı 13 Kasım 2014.
^ Schmidhuber, Jürgen (5 Mart 2009). "Gödel'de Nihai Biliş". Bilişsel Hesaplama. 1 (2): 177–193. CiteSeerX 10.1.1.218.3323. doi:10.1007 / s12559-009-9014-y.

Dış bağlantılar

[1] Mahmud, M. M. Hassan (2008). Evrensel Transfer Öğrenimi. sayfa 16–18. ISBN 9780549909880.

[2] Anderson, Michael L .; Tim Oates (Bahar 2007). "Metareasoning ve metal öğrenmede son araştırmaların bir incelemesi". AI Dergisi. 28 (1): 7.

[Gödel_Machines.-3] ^ ^a ^b ^c ^d ^e ^f ^g ^h ^ben Schmidhuber, Jürgen (Aralık 2006). Gödel Makineleri: Kendi Kendine Yönelik ¨ Kendi Kendini İyileştirmeleri Sağlayacak Şekilde Optimum Sağlayan Evrensel Sorun Çözücüler (PDF). Alındı 10 Kasım 2014.

[4] "Gödel makinesi".

[5] Schaul, Tom; Schmidhuber, Juergen (2010). "Metal öğrenme". Scholarpedia. 5 (6): 4650. Bibcode:2010SchpJ ... 5.4650S. doi:10.4249 / alimpedia.4650. Alındı 10 Kasım 2014.

[6] Steunebrink, Bas R .; Schmidhuber, Jürgen (2011). Gödel Makine Uygulamaları Ailesi. Bilgisayar Bilimlerinde Ders Notları. 6830. s. 275–280. CiteSeerX 10.1.1.300.3076. doi:10.1007/978-3-642-22887-2_29. ISBN 978-3-642-22886-5.

[7] Schmidhuber, Jürgen (5 Mart 2009). "Gödel'de Nihai Biliş" (PDF). Bilişsel Hesaplama. 1 (2): 177–193. CiteSeerX 10.1.1.218.3323. doi:10.1007 / s12559-009-9014-y. Alındı 13 Kasım 2014.

[8] Schmidhuber, Jürgen (5 Mart 2009). "Gödel'de Nihai Biliş" (PDF). Bilişsel Hesaplama. 1 (2): 177–193. CiteSeerX 10.1.1.218.3323. doi:10.1007 / s12559-009-9014-y. Alındı 13 Kasım 2014.

[9] Schmidhuber, Jürgen (5 Mart 2009). "Gödel'de Nihai Biliş". Bilişsel Hesaplama. 1 (2): 177–193. CiteSeerX 10.1.1.218.3323. doi:10.1007 / s12559-009-9014-y.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]