Durma sorunu - Halting problem

Bu makale genel bir liste içerir Referanslar, ancak büyük ölçüde doğrulanmamış kalır çünkü yeterli karşılık gelmiyor satır içi alıntılar. Lütfen yardım edin geliştirmek bu makale tanıtım daha kesin alıntılar. (Eylül 2018) (Bu şablon mesajını nasıl ve ne zaman kaldıracağınızı öğrenin)

İçinde hesaplanabilirlik teorisi, durdurma sorunu keyfi bir tanımdan belirleme problemidir bilgisayar programı ve programın çalışmasının bitip bitmeyeceği veya sonsuza kadar çalışmaya devam edeceği bilgisi. Alan Turing 1936'da bir general olduğunu kanıtladı algoritma olası tüm program-giriş çiftleri için durdurma problemini çözmek için var olamaz.

Herhangi bir program için f programların durup durmayacağını belirleyebilir, "patolojik" bir program g, bazı girdilerle çağrılır, kendi kaynağını ve girdisini f ve özellikle neyin tersini yapın f tahmin g yapacağım. Hayır f bu davayı ele alan var olabilir. İspatın önemli bir kısmı, bilgisayar ve programın matematiksel tanımıdır. Turing makinesi; durdurma problemi karar verilemez Turing makineleri üzerinden. İlk vakalardan biridir karar problemleri çözülemez olduğu kanıtlandı. Bu kanıt, hiçbir programlama buluşunun mükemmel bir şekilde gerçekleştiremeyeceği bir uygulama sınıfını tanımlayan pratik hesaplama çabaları için önemlidir.

Jack Copeland (2004) terimin girişine atıfta bulunur durdurma sorunu işine Martin Davis 1950 lerde.^[1]

Arka fon

Durma sorunu, sabit bir bilgisayar programlarının özellikleriyle ilgili bir karar sorunudur. Turing tamamlandı hesaplama modeli, yani verilen bazılarında yazılabilen tüm programlar Programlama dili bu bir Turing makinesine eşdeğer olacak kadar geneldir. Sorun, bir program ve programa bir girdi verildiğinde, programın bu girdi ile çalıştırıldığında sonunda durup durmayacağını belirlemektir. Bu soyut çerçevede, programın yürütülmesi için gereken bellek miktarı veya zaman konusunda hiçbir kaynak sınırlaması yoktur; keyfi olarak uzun sürebilir ve durdurulmadan önce keyfi miktarda depolama alanı kullanabilir. Soru basitçe verilen programın belirli bir girdi üzerinde durup durmayacağıdır.

Örneğin, sözde kod program

(true) devam ederken

durmaz; bunun yerine sonsuza kadar devam eder sonsuz döngü. Öte yandan program

"Merhaba dünya!"

durur.

Bu programların durup durmayacağına karar vermek basit olsa da, daha karmaşık programlar sorunludur. Soruna bir yaklaşım, programı birkaç adımda çalıştırmak ve durup durmadığını kontrol etmek olabilir. Ancak program durmazsa, programın sonunda durup durmayacağı veya sonsuza kadar çalışıp çalışmayacağı bilinmemektedir. Turing, belirli bir program ve girdi için programın o girdi ile çalıştırıldığında durup durmayacağına her zaman doğru şekilde karar veren bir algoritmanın olmadığını kanıtladı. Turing'in kanıtının özü, böyle bir algoritmanın kendisiyle çelişecek şekilde yapılabileceği ve bu nedenle doğru olamayacağıdır.

Programlama sonuçları

Biraz sonsuz döngüler oldukça faydalı olabilir. Örneğin, olay döngüleri tipik olarak sonsuz döngüler olarak kodlanır.^[2]Bununla birlikte, çoğu alt yordamın tamamlanması (durdurulması) amaçlanmıştır.^[3]Özellikle zor gerçek zamanlı bilgi işlem programcılar, yalnızca bitmesi (durması) garanti edilmeyen, aynı zamanda belirli bir son tarihten önce bitmesi garanti edilen alt yordamlar yazmaya çalışır.^[4]

Bazen bu programcılar bazı genel amaçlı (Turing-complete) programlama dilleri kullanırlar, ancak kısıtlı bir tarzda yazmaya çalışırlar. MISRA C veya KIVILCIM —Bu, ortaya çıkan alt rutinlerin verilen son tarihten önce bittiğini kanıtlamayı kolaylaştırır.^{[kaynak belirtilmeli ]}

Diğer zamanlarda bu programcılar, en az güç kuralı —Tamamen Turing-tamamlanmamış bir bilgisayar dilini kasıtlı olarak kullanıyorlar. Genellikle, bunlar tüm alt yordamların bitmesini garanti eden dillerdir, örneğin Coq.^{[kaynak belirtilmeli ]}

Ortak tuzaklar

Durdurma problemindeki zorluk, karar prosedürünün tüm programlar ve girdiler için çalışması gerekliliğinde yatmaktadır. Belirli bir program, belirli bir girişte durur veya durmaz. Her zaman "durmalar" yanıtını veren ve her zaman "durmayan" yanıtını veren bir algoritma düşünün. Herhangi bir özel program ve girdi için, bu iki algoritmadan biri, hiç kimse hangisini bilmese bile doğru yanıt verir. Yine de her iki algoritma da genel olarak durma problemini çözmez.

Programlar var (tercümanlar ) verilen kaynak kodun yürütülmesini simüle eden. Bu tür programlar, bu durumda bir programın durduğunu gösterebilir: yorumlayıcının kendisi sonunda simülasyonunu durdurur, bu da orijinal programın durduğunu gösterir. Ancak, bir yorumlayıcı girdi programı durmazsa durmayacaktır, bu nedenle bu yaklaşım durma sorununu belirtildiği gibi çözemez; durmayan programlar için "durmaz" yanıtını başarıyla vermez.

Durma problemi teorik olarak karar verilebilir: doğrusal sınırlı otomata (LBA'lar) veya sonlu belleğe sahip deterministik makineler. Sonlu belleğe sahip bir makinenin sınırlı sayıda yapılandırması vardır ve bu nedenle, üzerindeki herhangi bir deterministik program, eninde sonunda önceki bir yapılandırmayı durdurmalı veya tekrar etmelidir:

...Herhangi bir sonlu durum makinesi, tamamen kendi başına bırakılırsa, sonunda mükemmel bir periyodik tekrarlayan modele düşecektir.. Bu yinelenen modelin süresi, makinenin dahili durumlarının sayısını aşamaz ... (orijinalinde italik, Minsky 1967, s. 24)

Bununla birlikte, Minsky, her biri iki duruma sahip bir milyon küçük parçaya sahip bir bilgisayarın en az 2^1,000,000 olası durumlar:

Bunu 1'i takip eden yaklaşık üç yüz bin sıfır ... Böyle bir makine kozmik ışınların frekanslarında çalışacak olsa bile, galaktik evrimin aeonları, böyle bir döngüdeki bir yolculuğun zamanına kıyasla hiçbir şey olmazdı ( Minsky 1967 sayfa 25):

Minsky, bir makinenin sonlu olmasına ve sonlu otomataların "bir takım teorik sınırlamalara sahip" olmasına rağmen şunu belirtir:

... ilgili büyüklükler kişiyi, esas olarak durum diyagramının yalnızca sonluluğuna dayanan teoremlerin ve argümanların büyük bir anlam taşımayabileceğinden şüphelenmeye sevk etmelidir. (Minsky s. 25)

Ayrıca, sonlu belleğe sahip kesin olmayan bir makinenin, her olası karardan sonra durumları sıralayarak, kesin olmayan kararların olası dizilerinin hiçbirinde, bazılarında veya tümünde durup durmayacağına otomatik olarak karar verilebilir.

Tarih

Bu bölüm içinde liste biçim, ancak daha iyi okuyabilir nesir. Yardımcı olabilirsiniz bu bölümü dönüştürmek, Eğer uygunsa. Yardım düzenleme kullanılabilir. (Şubat 2020)

Durma sorunu tarihsel olarak önemlidir çünkü kanıtlanması gereken ilk sorunlardan biriydi. karar verilemez. (Turing'in kanıtı 1936 Mayıs'ında basıma gitti. Alonzo Kilisesi bir sorunun karar verilemezliğinin kanıtı lambda hesabı Nisan 1936'da yayımlanmıştı [Kilise, 1936]. Daha sonra, kararlaştırılamayan diğer birçok sorun tanımlandı.

Zaman çizelgesi

• 1900: David Hilbert "23 sorusunu" soruyor (artık Hilbert'in sorunları ) ikinci Uluslararası Matematikçiler Kongresi Paris'te. "Bunlardan ikincisi, 'in tutarlılığını kanıtlamaktı.Peano aksiyomları Matematiğin titizliğinin gösterdiği gibi buna bağlıydı ". (Hodges s. 83, Davis'in Davis'in yorumu, 1965, s. 108)
• 1920–1921: Emil Post durma problemini araştırır etiket sistemleri, onu çözümsüzlük adayı olarak görüyor. (Kesinlikle çözülemeyen sorunlar ve nispeten kararsız önermeler - bir öngörü açıklaması, Davis, 1965, s. 340–433.) Çözülmezliği çok daha sonrasına kadar tespit edilmedi. Marvin Minsky (1967).
• 1928: Hilbert, Bologna Uluslararası Kongresi'nde 'İkinci Problemi'ni yeniden canlandırdı. (Reid s. 188–189) Hodges üç soru sorduğunu iddia ediyor: yani # 1: Matematik miydi tamamlayınız? # 2: Matematik miydi tutarlı? # 3: Matematik miydi karar verilebilir? (Hodges s. 91). Üçüncü soru olarak bilinir Entscheidungsproblem (Karar Problemi). (Hodges s.91, Penrose s.34)
• 1930: Kurt Gödel Hilbert'in 1928 sorusundan ilk ikisine bir cevap olarak bir ispat duyurur [cf Reid s. 198]. "Önce o [Hilbert] sadece kızgındı ve hayal kırıklığına uğramıştı, ama sonra sorunu yapıcı bir şekilde ele almaya başladı ... Gödel'in kendisi, çalışmasının Hilbert'in biçimsel bakış açısıyla çelişmediğini hissetti ve makalesinde düşüncesini ifade etti. görünümü "(Reid s. 199)
• 1931: Gödel, "Principia Mathematica ve İlgili Sistemlerin Resmi Olarak Karar Verilemeyen Önerileri Üzerine I" adlı kitabını yayınladı (Davis, 1965, s. 5ff'de yeniden basıldı)
• 19 Nisan 1935: Alonzo Kilisesi "Temel Sayı Teorisinin Çözülemeyen Bir Problemi" ni yayınlar, burada bir fonksiyonun olmasının ne anlama geldiğini tanımlar etkili bir şekilde hesaplanabilir. Böyle bir işlevin bir algoritması olacaktır ve "... algoritmanın sonlandırıldığı gerçeği etkin bir şekilde bilinir ..." (Davis, 1965, s. 100)
• 1936: Kilise, Entscheidungsproblem çözülemez. (Entscheidungsproblem Üzerine Bir Not, Davis'te yeniden basıldı, 1965, s. 110.)
• 7 Ekim 1936: Emil Post "Finite Combinatory Processes. Formulation I" adlı makalesi alındı. Gönderi, "işleme" bir talimat "(C) Durdur" ekler. Böyle bir süreci "tip 1 ... eğer belirlediği süreç her bir sorun için sonlanırsa" olarak adlandırdı. (Davis, 1965, sayfa 289ff)
• 1937: Alan Turing kağıdı Entscheidungsproblem Uygulamasıyla Hesaplanabilir Sayılar Üzerine Ocak 1937'de baskıya ulaşır (Davis, 1965, s. 115'te yeniden basılmıştır). Turing'in ispatı hesaplamadan özyinelemeli işlevler ve makineyle hesaplama kavramını tanıtır. Stephen Kleene (1952) bunu "çözülemez olduğu kanıtlanan karar problemlerinin ilk örneklerinden" biri olarak ifade eder.
• 1939: J. Barkley Rosser Gödel, Church ve Turing tarafından tanımlanan "etkili yöntem" in temel denkliğini gözlemler (Rosser in Davis, 1965, s. 273, "Gödel Teoremi ve Kilise Teoremi Kanıtlarının Gayri Resmi İfadesi")
• 1943: Bir gazetede, Stephen Kleene "Tam bir algoritmik teori oluştururken, yaptığımız şey bir prosedürü tanımlamaktır ... bu prosedür zorunlu olarak sona erer ve öyle bir şekilde sonuçtan kesin bir cevabı okuyabiliriz," Evet "veya" Hayır ". sorusu, 'Yüklem değeri doğru mu?'.
• 1952: Kleene (1952) Bölüm XIII ("Hesaplanabilir Fonksiyonlar"), Turing makineleri için durma sorununun çözülemezliğine ilişkin bir tartışmayı içerir ve bunu "sonunda duran", yani duran makineler açısından yeniden formüle eder: "... herhangi bir belirli durumdan başlatıldığında herhangi bir makinenin olup olmadığına karar vermek için algoritma, sonunda durur. "(Kleene (1952) s. 382)
• 1952: "Martin Davis 1952'de Illinois Üniversitesi Kontrol Sistemleri Laboratuvarı'nda verdiği bir dizi konferansta 'durma sorunu' terimini ilk kez kullandığını düşünüyor (Davis'ten Copeland'a mektup, 12 Aralık 2001). "(Dipnot 61, Copeland (2004) s. 40ff)

Resmileştirme

Turing, orijinal ispatında algoritma tanıtarak Turing makineleri. Ancak sonuç hiçbir şekilde onlara özgü değildir; diğer herhangi bir model için de geçerlidir hesaplama bu, hesaplama gücünde Turing makinelerine eşdeğerdir, örneğin Markov algoritmaları, Lambda hesabı, Posta sistemleri, makineleri kaydet veya etiket sistemleri.

Önemli olan, biçimlendirmenin, algoritmaların bazılarına basit bir şekilde eşleştirilmesine izin vermesidir. veri tipi bu algoritma üzerinde çalışabilir. Örneğin, biçimcilik algoritmaların dizeler üzerinden işlevleri tanımlamasına izin verir (Turing makineleri gibi), o zaman bu algoritmaların dizelerle eşlenmesi gerekir ve biçimsellik algoritmaların işlevleri doğal sayılar üzerinden tanımlamasına izin verirse (örneğin hesaplanabilir işlevler ) o zaman algoritmaların doğal sayılarla eşlenmesi gerekir. Dizelere eşleme genellikle en basit olanıdır, ancak bir alfabe ile n karakterler aynı zamanda sayılar olarak yorumlanarak sayılarla eşleştirilebilir. n-ary sayı sistemi.

Küme olarak temsil

Karar problemlerinin geleneksel temsili, söz konusu özelliğe sahip olan nesneler kümesidir. durdurma seti

K = {(ben, x) | program ben girişte çalıştırıldığında durur x}

durma sorununu temsil eder.

Bu set yinelemeli olarak numaralandırılabilir bu, tüm çiftleri listeleyen hesaplanabilir bir işlev olduğu anlamına gelir (ben, x) Bu içerir. Ancak, bu kümenin tamamlayıcısı yinelemeli olarak numaralandırılamaz.^[5]

Durdurma sorununun birçok eşdeğer formülasyonu vardır; herhangi bir set Turing derecesi eşittir durma problemi böyle bir formülasyondur. Bu tür setlerin örnekleri şunları içerir:

• {ben | program ben 0} girişiyle çalıştırıldığında sonunda durur
• {ben | bir girdi var x öyle ki program ben girdi ile çalıştırıldığında sonunda durur x}.

İspat kavramı

Durdurma sorununun çözülemeyeceğinin kanıtı bir çelişki ile ispat. İspat kavramını açıklamak için, bir Toplam hesaplanabilir işlev durur (f) bu, alt yordamın f durur (giriş olmadan çalıştırıldığında) ve aksi takdirde yanlış döndürür. Şimdi aşağıdaki alt programı düşünün:

def g():    Eğer durur(g):        loop_forever()

durur (g) doğru ya da yanlış döndürmelidir, çünkü durur olduğu varsayıldı Toplam. Eğer durur (g) true, sonra g Arayacağım loop_forever ve asla durma, ki bu bir çelişkidir. Eğer durur (g) yanlış döndürür, sonra g duracak çünkü aramayacak loop_forever; bu aynı zamanda bir çelişkidir. Genel olarak, durur (g) ile tutarlı bir doğruluk değeri döndüremez g durur. Bu nedenle, ilk varsayım durur toplam hesaplanabilir bir işlev yanlış olmalıdır.

İspatta kullanılan yönteme köşegenleştirme - g neyin tersini yapar durur diyor g yapmak gerekir. Bu taslak ile gerçek kanıt arasındaki fark, gerçek ispatta hesaplanabilir fonksiyonun durur bir alt rutini doğrudan bir argüman olarak almaz; bunun yerine bir programın kaynak kodunu alır. Gerçek kanıt, bu sorunu çözmek için ek çalışma gerektirir. Dahası, gerçek ispat, tanımında gösterilen özyinelemenin doğrudan kullanımından kaçınır. g.

İspat taslağı

Yukarıdaki kavram ispatın genel yöntemini göstermektedir; bu bölüm ek ayrıntılar sunacaktır. Genel amaç, olmadığını göstermektir. Toplam hesaplanabilir işlev keyfi bir program olup olmadığına karar veren ben keyfi girişte durur x; yani aşağıdaki işlev h hesaplanamaz (Penrose 1990, s. 57–63):

${displaystyle h (i, x) = {egin {case} 1 & {ext {if}} {ext {program}} i {ext {input on input}} x, 0 & {ext {ext {aksi}} end {case }}}$

Buraya program i ifade eder ben th programı bir sayım bir sabitin tüm programları Turing tamamlandı hesaplama modeli.

İspat, iki bağımsız değişkeni olan hiçbir toplam hesaplanabilir işlevin gerekli işlev olamayacağını doğrudan belirleyerek ilerler. h. Kavramın taslağında olduğu gibi, herhangi bir toplam hesaplanabilir ikili fonksiyon verildiğinde f, aşağıdaki kısmi işlev g bazı programlarla da hesaplanabilir e:

${displaystyle g (i) = {egin {case} 0 & {ext {if}} f (i, i) = 0, {ext {undefined}} & {ext {else.}} end {case}}}$

Doğrulama g hesaplanabilir, aşağıdaki yapılara (veya bunların eşdeğerlerine) dayanır:

• hesaplanabilir alt programlar (hesaplayan program f programdaki bir alt programdır e),
• değerlerin tekrarlanması (program e girdileri hesaplar ben,ben için f girişten ben için g),
• koşullu dallanma (program e hesapladığı değere bağlı olarak iki sonuç arasında seçim yapar f(ben,ben)),
• tanımlı bir sonuç üretmemek (örneğin sonsuza kadar döngü yaparak),
• 0 değeri döndürüyor.

Aşağıdaki sözde kod hesaplamanın basit bir yolunu gösterir g:

prosedür compute_g(ben):    Eğer f(ben, ben) == 0 sonra        dönüş 0    Başka        döngü sonsuza dek

Çünkü g kısmi hesaplanabilir, bir program olmalı e hesaplayan g, hesaplama modelinin Turing-complete olduğu varsayımıyla. Bu program, durdurma işlevinin üzerinde çalıştığı tüm programlardan biridir. h tanımlanmış. İspatın bir sonraki adımı şunu gösterir: h(e,e) ile aynı değere sahip olmayacak f(e,e).

Tanımından izler g tam olarak aşağıdaki iki durumdan biri geçerli olmalıdır:

• f(e,e) = 0 ve benzeri g(e) = 0. Bu durumda h(e,e) = 1, çünkü program e girişte durur e.
• f(e,e) ≠ 0 ve benzeri g(e) tanımsızdır. Bu durumda h(e,e) = 0, çünkü program e girişte durmaz e.

Her iki durumda da, f ile aynı işlev olamaz h. Çünkü f bir keyfi iki bağımsız değişken ile toplam hesaplanabilir işlev, tüm bu işlevler farklı olmalıdır h.

Bu ispat benzerdir Cantor'un çapraz argümanı. Yukarıdaki tabloda belirtildiği gibi, her doğal sayı için bir sütun ve bir satır içeren iki boyutlu bir dizi görselleştirilebilir. Değeri f(ben,j) sütuna yerleştirilir ben, kürek çekmek j. Çünkü f toplam hesaplanabilir bir işlev olduğu varsayılırsa, dizinin herhangi bir öğesi kullanılarak hesaplanabilir f. Fonksiyonun yapısı g bu dizinin ana köşegeni kullanılarak görselleştirilebilir. Dizinin konumunda 0 varsa (ben,ben), sonra g(ben) 0'dır. Aksi takdirde, g(ben) tanımsızdır. Çelişki, bir sütun olmasından kaynaklanmaktadır. e karşılık gelen dizinin g kendisi. Şimdi varsayalım f durdurma işlevi miydi h, Eğer g(e) tanımlanmış (g(e) = 0 bu durumda), g(e) öylece durur f(e, e) = 1. Ama g(e) = 0 yalnızca f(e, e) = 0, çelişkili f(e, e) = 1. Benzer şekilde, eğer g(e) tanımlanmadı, ardından işlevi durdurma f(e, e) = 0, g(e) = 0 altında g 'inşaat. Bu varsayımla çelişir g(e) tanımlanmıyor. Her iki durumda da çelişki ortaya çıkar. Bu nedenle herhangi bir rasgele hesaplanabilir işlev f durdurma işlevi olamaz h.

Hesaplanabilirlik teorisi

Bir sorunun kararlaştırılamaz olduğunu kanıtlamanın tipik yöntemi, indirgeme^{[açıklama gerekli ]}. Bunu yapmak için, yeni probleme bir çözüm bulunursa, karar verilemeyen problemin örneklerini yeni problemin örneklerine dönüştürerek karar verilemeyen bir probleme karar vermek için kullanılabileceğini göstermek yeterlidir. Bunu zaten bildiğimiz için Hayır yöntem eski soruna karar verebilir, yeni soruna da hiçbir yöntem karar veremez. Genellikle yeni sorun, durma sorununu çözmeye indirgenir. (Aynı teknik, bir problemin NP tamamlandı, sadece bu durumda, çözüm olmadığını göstermek yerine, hiçbir çözüm olmadığını gösterir. polinom zamanı varsayarsak çözüm P ≠ NP.)

Örneğin, durdurma sorununun karar verilemezliğinin böyle bir sonucu, genel bir sorunun olamayacağıdır. algoritma hakkında verilen bir ifadenin doğal sayılar doğru veya yanlış. Bunun nedeni şudur: önerme belirli bir girdi verildiğinde belirli bir programın duracağını belirten doğal sayılar hakkında eşdeğer bir ifadeye dönüştürülebilir. Doğal sayılarla ilgili her ifadenin doğruluk değerini bulabilen bir algoritmamız olsaydı, kesinlikle bunun doğruluk değerini bulabilirdi; ancak bu, orijinal programın durup durmayacağını belirleyecektir, ki bu imkansızdır, çünkü durdurma problemi kararlaştırılamaz.

Rice teoremi Durma probleminin çözülemez olduğu teoremini genelleştirir. Bunu belirtir hiç önemsiz olmayan özellik, tüm programlar için girdi programı tarafından uygulanan kısmi işlevin bu özelliğe sahip olup olmadığına karar veren genel bir karar prosedürü yoktur. (Kısmi işlev, her zaman bir sonuç üretmeyebilen bir işlevdir ve bu nedenle, sonuçları üretebilen veya durdurmayı başaramayan programları modellemek için kullanılır.) Örneğin, "0 girdisi için durdurma" özelliği karar verilemez. Burada, "önemsiz olmayan", özelliği karşılayan kısmi işlevler kümesinin ne boş küme ne de tüm kısmi işlevler kümesi olduğu anlamına gelir. Örneğin, "0 girişinde durur veya durmaz" tüm kısmi işlevler için açıkça doğrudur, bu nedenle önemsiz bir özelliktir ve basitçe "doğru" raporlayan bir algoritma tarafından kararlaştırılabilir. Ayrıca, bu teorem sadece program tarafından uygulanan kısmi fonksiyonun özellikleri için geçerlidir; Rice'ın Teoremi, programın kendi özelliklerine uygulanmaz. Örneğin, "100 adımda 0 girişinde durma" değil program tarafından uygulanan kısmi işlevin bir özelliği - kısmi işlevi uygulayan programın bir özelliğidir ve büyük ölçüde karar verilebilir.

Gregory Chaitin tanımladı durdurma olasılığı sembolüyle gösterilir Ω gayri resmi olarak temsil ettiği söylenen bir tür gerçek sayı olasılık rastgele üretilmiş bir programın durması. Bu numaralar aynı Turing derecesi durma sorunu olarak. Bu bir normal ve aşkın sayı hangisi olabilir tanımlı ama tamamen olamaz hesaplanmış. Bu, birinin olmadığını kanıtlayabileceği anlamına gelir algoritma Bu, Ω rakamlarını üretir, ancak ilk birkaç rakamı basit durumlarda hesaplanabilir.

Turing'in kanıtı, algoritmaların durup durmayacağını belirlemek için genel bir yöntem veya algoritma olamayacağını gösterirken, bu sorunun tek tek örnekleri saldırıya çok açık olabilir. Belirli bir algoritma verildiğinde, genellikle herhangi bir girdi için durması gerektiği ve aslında Bilgisayar bilimcileri genellikle bunu bir doğruluk kanıtı. Ancak her bir kanıt, özellikle eldeki algoritma için geliştirilmelidir; yok mekanik, genel yol Turing makinesindeki algoritmaların durup durmadığını belirlemek için. Ancak, bazıları var Sezgisel Bu, tipik programlarda sıklıkla başarılı olan bir ispat oluşturmaya çalışmak için otomatik bir şekilde kullanılabilir. Bu araştırma alanı otomatik olarak bilinir sonlandırma analizi.

Durma problemine verilen olumsuz cevap, bir Turing makinesi ile çözülemeyen problemler olduğunu gösterdiğinden, Kilise-Turing tezi uygulayan herhangi bir makinenin neler yapabileceğini sınırlar etkili yöntemler. Bununla birlikte, insanın hayal gücüne uygun tüm makineler Kilise-Turing tezine tabi değildir (ör. oracle makineleri ). Gerçek deterministik olup olamayacağı açık bir sorudur. fiziksel süreçler Uzun vadede, bir Turing makinesinin simülasyonundan kaçınma ve özellikle de böyle bir varsayımsal sürecin bir hesaplama makinesi (a hiper bilgisayar ) Bu, diğer şeylerin yanı sıra bir Turing makinesinin durma problemini çözebilir. Aynı zamanda, bu tür bilinmeyen fiziksel süreçlerin işleyişine dahil olup olmadığı da açık bir sorudur. İnsan beyni ve insanların durdurma sorununu çözüp çözemeyeceği (Copeland 2004, s. 15).

Gödel'in eksiklik teoremleri

Tarafından ortaya atılan kavramlar Gödel'in eksiklik teoremleri durdurma problemi ile ortaya çıkanlara çok benzer ve ispatlar oldukça benzerdir. Aslında, Birinci Eksiklik Teoreminin daha zayıf bir formu, durma probleminin karar verilememesinin kolay bir sonucudur. Bu daha zayıf form, eksiklik teoreminin standart ifadesinden farklıdır; aksiyomatizasyon doğal sayıların hem tam hem de ses imkansız. "Sağlam" kısmı zayıflatmadır: bu, söz konusu aksiyomatik sistemin yalnızca doğru doğal sayılarla ilgili ifadeler. Sağlamlık ima ettiğinden tutarlılık, bu daha zayıf biçim bir sonuç güçlü biçimin. Gödel'in Birinci Eksiklik Teoreminin standart biçiminin ifadesinin, bir ifadenin doğruluk değeriyle tamamen ilgisiz olduğunu, ancak yalnızca onu bir ifadeyle bulmanın mümkün olup olmadığı konusuyla ilgili olduğunu gözlemlemek önemlidir. matematiksel kanıt.

Teoremin daha zayıf formu, durma probleminin karar verilememesinden şu şekilde ispatlanabilir. Bir sesimiz (ve dolayısıyla tutarlı) ve eksiksiz olduğumuzu varsayın aksiyomatizasyon hepsi doğru birinci dereceden mantık hakkında açıklamalar doğal sayılar. Daha sonra tüm bu ifadeleri sıralayan bir algoritma oluşturabiliriz. Bu, bir algoritma olduğu anlamına gelir N(n) doğal bir sayı verildiğinde n, doğal sayılar hakkında gerçek bir birinci dereceden mantık ifadesini hesaplar ve tüm doğru ifadeler için en az bir n öyle ki N(n) bu ifadeyi verir. Şimdi, temsili algoritmanın a girişte durur ben. Bu ifadenin birinci dereceden bir mantık ifadesi ile ifade edilebileceğini biliyoruz. H(a, ben). Aksiyomatizasyon tamamlandığından, ya bir n öyle ki N(n) = H(a, ben) veya bir n ' öyle ki N(n ') = ¬ H(a, ben). Yani eğer biz yinelemek her şeyden önce n bulana kadar H(a, ben) ya da onun olumsuzlanması, her zaman duracağız ve dahası, bize verdiği cevap (sağlamlıkla) doğru olacaktır. Bu, bize durma sorununa karar vermemiz için bir algoritma verdiği anlamına gelir. Böyle bir algoritma olamayacağını bildiğimiz için, doğal sayılarla ilgili tüm gerçek birinci dereceden mantık ifadelerinin tutarlı ve tam bir aksiyomatizasyonunun olduğu varsayımının yanlış olması gerektiği sonucuna varır.

Genelleme

Durma probleminin birçok çeşidi hesaplanabilirlik ders kitaplarında bulunabilir (örneğin, Sipser 2006, Davis 1958, Minsky 1967, Hopcroft ve Ullman 1979, Börger 1989). Tipik olarak karar verilemezlikleri şu şekilde olur: indirgeme standart durma probleminden. Ancak, bazılarının daha yüksek çözülemezlik derecesi. Sonraki iki örnek tipiktir.

Tüm girişlerde durdurma

evrensel durma sorunu, ayrıca bilinir (in özyineleme teorisi ) gibi bütünlük, belirli bir bilgisayar programının durup durmayacağını belirleme problemidir her girdi için (isim bütünlük hesaplanan fonksiyonun eşdeğer olup olmadığı sorusundan gelir Toplam Bu sorun sadece durdurma sorunu olarak kararlaştırılamaz değil, aynı zamanda büyük ölçüde kararlaştırılamaz. Açısından aritmetik hiyerarşi, bu ${displaystyle Pi _ {2} ^ {0}}$-tamamlandı (Börger 1989, s. 121).

Bu, özellikle bir kararla bile karar verilemeyeceği anlamına gelir. kehanet durma sorunu için.

Kısmi çözümleri tanımak

Bazı girdiler için durma sorununa doğru bir yanıt döndüren birçok program vardır, diğer girdiler içinse hiç yanıt vermezler. Ancak sorun "verilen program p, bu bir kısmi durdurma çözücü mü? "(açıklanan anlamda) en azından durdurma problemi kadar zor. Bunu görmek için, bunu yapmak için bir algoritma PHSR (" kısmi durdurma çözücü tanıyıcı ") olduğunu varsayın. aşağıdaki gibi durma problemini çözmek için kullanılabilir: Giriş programının olup olmadığını test etmek için x durur y, bir program inşa et p girişte (x,y) raporlar doğru ve diğer tüm girişlerde farklılaşır. p PHSR ile.

Yukarıdaki argüman bir indirgeme durdurma probleminin PHS tanınmasına ve aynı şekilde daha zor problemlere tüm girişlerde durma PHS tanınmasının sadece karar verilemez değil, aynı zamanda daha yüksek olduğunu ima ederek azaltılabilir. aritmetik hiyerarşi özellikle ${displaystyle Pi _ {2} ^ {0}}$-tamamlayınız.

Kayıplı hesaplama

Bir kayıplı Turing makinesi bandın bir kısmının deterministik olmayan bir şekilde kaybolabileceği bir Turing makinesidir. Durma problemi kayıplı Turing makinesi için karar verilebilir ancakilkel özyinelemeli.^[6]:92

Oracle makineleri

Bir makine kehanet çünkü durma sorunu, belirli Turing makinelerinin belirli girdilerde durup durmayacağını belirleyebilir, ancak genel olarak kendilerine eşdeğer makinelerin durup durmayacağını belirleyemezler.

Ayrıca bakınız

• Meşgul kunduz
• Gödel'in eksiklik teoremi
• Brouwer-Hilbert tartışması
• Kolmogorov karmaşıklığı
• P'ye karşı NP sorunu
• Sonlandırma analizi
• En kötü durum yürütme süresi

Notlar

Referanslar

• Alan Turing, Hesaplanabilir sayılar üzerine, Entscheidungsproblem uygulaması ile, Tutanaklar Londra Matematik Derneği, Seri 2, Cilt 42 (1937), s. 230–265, doi:10.1112 / plms / s2-42.1.230. - Alan Turing, Entscheidungsproblem için bir Uygulama ile Hesaplanabilir Sayılarda. Bir Düzeltme, Proceedings of the London Mathematical Society, Series 2, Volume 43 (1938), pp 544–546, doi:10.1112 / plms / s2-43.6.544 . Her iki parçanın ücretsiz çevrimiçi versiyonu Bu, Turing'in tanımladığı çığır açan kağıttır. Turing makineleri, durdurma sorununu formüle eder ve bunun olduğunu gösterir (aynı zamanda Entscheidungsproblem ) çözülemez.
• Sipser, Michael (2006). "Bölüm 4.2: Durma Sorunu". Hesaplama Teorisine Giriş (İkinci baskı). PWS Yayıncılık. pp.173–182. ISBN  0-534-94728-X.
• c2: HaltingProblem
• Kilise, Alonzo (1936). "Temel Sayı Teorisinin Çözülemeyen Bir Problemi". Amerikan Matematik Dergisi. 58 (2): 345–363. doi:10.2307/2371045. JSTOR  2371045.
• B. Jack Copeland ed. (2004), Temel Turing: Hesaplama, Mantık, Felsefe, Yapay Zeka ve Yapay Yaşamda Yeni Yazılar ve Enigmanın Sırları, Clarendon Press (Oxford University Press), Oxford UK, ISBN  0-19-825079-7.
• Davis, Martin (1965). Kararsız Önermeler, Çözümlenemeyen Sorunlar ve Hesaplanabilir Fonksiyonlar Üzerine Kararsız, Temel Makaleler. New York: Raven Press.. Turing'in makalesi bu ciltte 3 numaradır. Makaleler arasında Godel, Church, Rosser, Kleene ve Post tarafından yazılanlar bulunmaktadır.
• Davis, Martin (1958). Hesaplanabilirlik ve Çözümlenemezlik. New York: McGraw-Hill..
• Alfred North Whitehead ve Bertrand Russell, Principia Mathematica * 56, Cambridge at the University Press, 1962. Re: paradokslar problemi, yazarlar bir setin problemini "belirleyici fonksiyonların" hiçbirinde bir nesne olmadığını tartışır, özellikle "Giriş, Bölüm 1 s. 24 "... biçimsel mantıkta ortaya çıkan zorluklar" ve Bölüm 2.I. "Kısır Döngü İlkesi" s. 37ff ve Bölüm 2.VIII. "Çelişkiler" s. 60ff.
• Martin Davis, "Hesaplama nedir", Bugün Matematik, Lynn Arthur Steen, Vintage Books (Random House), 1980. Harika bir küçük kağıt, belki de uzman olmayanlar için Turing Makineleri hakkında yazılmış en iyi makale. Davis, Turing Machine'i Post'un hesaplama modeline göre çok daha basit bir modele indirgiyor. Tartışır Chaitin kanıt. Küçük biyografileri içerir Emil Post, Julia Robinson.
• Marvin Minsky, Hesaplama: Sonlu ve Sonsuz Makineler, Prentice-Hall, Inc., NJ, 1967. Bkz. Bölüm 8, Kısım 8.2 "Durma Probleminin Çözülememesi."
• Roger Penrose, İmparatorun Yeni Zihni: Bilgisayarlar, Akıllar ve Fizik Kanunları ile ilgili, Oxford University Press, Oxford İngiltere, 1990 (düzeltmelerle). Cf. Bölüm 2, "Algoritmalar ve Turing Makineleri". Aşırı karmaşık bir sunum (daha iyi bir model için Davis'in makalesine bakın), ancak Turing makinelerinin ve durma probleminin kapsamlı bir sunumu ve Church's Lambda Calculus.
• John Hopcroft ve Jeffrey Ullman, Otomata Teorisine Giriş, Diller ve Hesaplama, Addison-Wesley, Okuma Kütlesi, 1979. Bkz. Bölüm 7 "Turing Makineleri". "Dillerin", NP-Bütünlüğün, vb. Makine-yorumu etrafında odaklanan bir kitap.
• Andrew Hodges, Alan Turing: Enigma, Simon ve Schuster, New York. Cf. Kanıtına götüren bir tarih ve bir tartışma için "Gerçeğin Ruhu" bölümü.
• Constance Reid, Hilbert, Copernicus: Springer-Verlag, New York, 1996 (ilk yayın tarihi 1970). Alman matematiğinin ve fiziğinin 1880'lerden 1930'lara kadar büyüleyici tarihi. Sayfalarında matematikçilerin, fizikçilerin ve mühendislerin aşina olduğu yüzlerce isim yer almaktadır. Belki de açık referanslar ve birkaç dipnotla gölgelenmiştir: Reid, kaynaklarının Hilbert'i şahsen tanıyanlar ve Hilbert'in mektupları ve kağıtları ile çok sayıda röportaj olduğunu belirtir.
• Edward Beltrami, Rastgele nedir? Matematikte ve hayatta şans ve düzen, Kopernik: Springer-Verlag, New York, 1999. Matematiksel eğilimli uzman olmayanlar için güzel, nazik bir okuma, sonunda daha zor şeyler koyar. İçerisinde Turing makina modeli var. Tartışır Chaitin katkılar.
• Moore, Cristopher; Mertens, Stephan (2011), Hesaplamanın Doğası, Oxford University Press, ISBN  9780191620805
• Ernest Nagel ve James R. Newman, Gödel'in Kanıtı, New York University Press, 1958. Çok zor bir konu hakkında harika yazı. Matematiksel eğilimli uzman olmayanlar için. Tartışır Gentzen 96-97. sayfalarda ve dipnotlarda ispatı. Ekler, Peano Aksiyomları kısaca, okuyuculara biçimsel mantığı nazikçe tanıtın.
• Taylor Booth, Sıralı Makineler ve Otomata Teorisi, Wiley, New York, 1967. Cf. Bölüm 9, Turing Makineleri. Elektrik mühendisleri ve teknik uzmanlar için tasarlanmış zor kitap. Turing Makinelerine referansla özyineleme, kısmi özyineleme, durma problemini tartışır. Bir Turing makinesi içinde model. Bölüm 9'un sonundaki referanslar, eski kitapların çoğunu (örneğin, yazarlar Martin Davis, F. C. Hennie, H. Hermes, S. C. Kleene, M. Minsky, T. Rado dahil olmak üzere 1952'den 1967'ye kadar) ve çeşitli teknik makaleleri yakalar. Meşgul-Kunduz Programları altındaki nota bakın.
• Meşgul Kunduz Programlar Scientific American, Ağustos 1984, ayrıca Mart 1985 s. 23. Booth'taki bir referans, onları Rado, T. (1962), Hesaplanamayan fonksiyonlar hakkında, Bell Systems Tech'e atfeder. J. 41. Booth ayrıca Rado'nun Meşgul Kunduz Problemini Bölüm 9, s. 3, 4, 5, 6 problemlerinde tanımlar. 396.
• David Bolter, Turing'in Adamı: Bilgisayar Çağında Batı Kültürü, The University of North Carolina Press, Chapel Hill, 1984. Genel okuyucu için. Tarihli olabilir. İçinde başka bir (çok basit) Turing Machine modeli var.
• Egon Börger. "Hesaplanabilirlik, Karmaşıklık, Mantık". Kuzey Hollanda, 1989.
• Stephen Kleene, Metamatatiğe Giriş, North-Holland, 1952. Bölüm XIII ("Hesaplanabilir Fonksiyonlar"), Turing makineleri için durdurma probleminin çözülemezliğine ilişkin bir tartışmayı içerir. Turing'in daire içermeyen, solmayan makineler terminolojisinden farklı olarak, Kleene bunun yerine "duran", yani duran makinelere atıfta bulunur.
• Sven Köhler, Christian Schindelhauer, Martin Ziegler, Gerçek dünyadaki durdurma sorunlarına yaklaşma hakkında, s. 454-466 (2005) ISBN  3540281932 Bilgisayar Bilimleri cilt 3623'teki Springer Ders Notları: Durdurma Probleminin Karar Verilemezliği, tüm durumların doğru şekilde cevaplanamayacağı anlamına gelir; ama belki "bazıları", "çok" veya "çoğu" olabilir? Bir yandan sabit cevap "evet" sonsuz sıklıkta doğru ve ayrıca sonsuz sıklıkta yanlış olacaktır. Soruyu mantıklı kılmak için şunu düşünün: yoğunluk çözülebilecek örneklerden. Bu, önemli ölçüde, Programlama Sistemi değerlendiriliyor.
• Ölümcül Otonom Silahların Sonuçlarıyla birlikte Makine Etiğinin Mantıksal Sınırlamaları - tartışılan makale: Durdurma Sorunu Ahlaki Robotların Olmadığı anlamına mı geliyor?
• Nicholas J. Daras ve Themistocles M. Rassias, Modern Ayrık Matematik ve Analiz: Kriptografi, Bilgi Sistemleri ve Modellemede Uygulamalar ile Springer, 2018. ISBN  978-3319743240. Bölüm 3 Kısım 1, durdurma sorununun kaliteli bir tanımını, çelişkili bir kanıtı ve Durdurma Sorunu'nun yardımcı bir grafik sunumunu içerir.

Dış bağlantılar

• Loop snooper'ı inceleme - durdurma sorununun karar verilemezliğinin şiirsel bir kanıtı
• animasyon filmi - durdurma sorununun karar verilemezliğinin kanıtını açıklayan bir animasyon
• 2. Milenyumun 2. En Önemli Teoreminin 2 Dakikalık Kanıtı - sadece 13 satırlık bir kanıt