Düşük temel teoremi - Low basis theorem - Wikipedia

Düşük temel teoremi birkaç taneden biridir temel teoremler hesaplanabilirlik teorisinde, her biri bunu gösteriyor, ikili ağacın sonsuz bir alt ağacı verildiğinde , belirli hesaplanabilirlik özelliklerine sahip ağaçta sonsuz bir yol bulmak mümkündür. Düşük temel teoremi, özellikle, bir yolun olması gerektiğini gösterir. düşük; yani Turing atlama Yolun Turing eşdeğeri durdurma sorunu .

Açıklama ve kanıt

Düşük temel teoremi, her boş olmayan sınıf içinde (görmek aritmetik hiyerarşi ) bir dizi içerir düşük derece (Soare 1987: 109). Bu, tanım olarak, ikili ağacın her sonsuz hesaplanabilir alt ağacının ifadesine eşdeğerdir. düşük dereceli sonsuz bir yola sahiptir.

İspat, zorlama yöntemini kullanır sınıflar (Cooper 2004: 330). Hájek ve Kučera (1989), düşük temelin şu adıyla bilinen resmi aritmetik sisteminde kanıtlanabilir olduğunu gösterdi. .

Uygulama

Düşük temel teoreminin bir uygulaması, tamamlamaların düşük Turing derecesine sahip olması için etkili teorilerin tamamlamalarını oluşturmaktır. Örneğin, düşük temel teoremi, PA dereceleri kesinlikle aşağıda .

Referanslar

  • Cenzer, Douglas (1999). " hesaplanabilirlik teorisindeki sınıflar ". Griffor'da Edward R. (ed.). Hesaplanabilirlik teorisi el kitabı. Damızlık. Mantık Bulundu. Matematik. 140. Kuzey-Hollanda. pp.37–85. ISBN  0-444-89882-4. BAY  1720779. Zbl  0939.03047.
  • Cooper, S. Barry (2004). Hesaplanabilirlik Teorisi. Chapman ve Hall / CRC. ISBN  1-58488-237-9..
  • Hájek, Petr; Kučera, Antonín (1989). "I∑1'de Özyineleme Teorisi Üzerine". Journal of Symbolic Logic. 54 (2): 576–589. doi:10.2307/2274871. JSTOR  2274871.
  • Jockusch, Carl G., Jr.; Soare, Robert I. (1972). "Π (0, 1) Teorilerin Sınıfları ve Dereceleri". Amerikan Matematik Derneği İşlemleri. 173: 33–56. doi:10.1090 / s0002-9947-1972-0316227-0. ISSN  0002-9947. JSTOR  1996261. Zbl  0262.02041. Ek açıklama düzyazı dahil orijinal yayın.
  • Nies, André (2009). Hesaplanabilirlik ve rastgelelik. Oxford Mantık Kılavuzları. 51. Oxford: Oxford University Press. ISBN  978-0-19-923076-1. Zbl  1169.03034. Teorem 1.8.37.
  • Soare, Robert I. (1987). Özyinelemeli olarak numaralandırılabilir kümeler ve dereceler. Hesaplanabilir işlevler ve hesaplanabilir şekilde oluşturulmuş kümeler üzerine bir çalışma. Matematiksel Mantıkta Perspektifler. Berlin: Springer-Verlag. ISBN  3-540-15299-7. Zbl  0667.03030.