Turing'in kanıtı - Turing's proof

Turing'in ispatı Alan Turing'in ilk kez Ocak 1937'de " On Computable Numbers, Application with a Application to the Entscheidungsproblem " başlığıyla yayınlanan bir ispatıdır . Bu, bazı salt matematiksel evet-hayır sorularının asla hesaplama yoluyla yanıtlanamayacağı varsayımının ( Church'in teoreminden sonra) ikinci kanıtıydı ; daha teknik olarak, sorunun her örneğine yanılmaz bir şekilde doğru "evet" veya "hayır" yanıtı veren tek bir algoritma olmaması anlamında bazı karar sorunlarının " karar verilemez " olduğudur . Turing'in kendi sözleriyle: "...kanıtlayacağım şey, Gödel'in iyi bilinen sonuçlarından oldukça farklıdır... Şimdi, belirli bir U formülünün K [ Principia'da kanıtlanabilir olup olmadığını söyleyen genel bir yöntem olmadığını göstereceğim. Mathematica ]..." ( Karar Verilemez , s. 145).

Turing bu kanıtı diğer iki kişiyle birlikte izledi. İkinci ve üçüncü her ikisi de birinciye güveniyor. Hepsi, basit bir dizi kurala uyan daktilo benzeri "bilgisayar makineleri" geliştirmesine ve ardından "evrensel bir bilgi işlem makinesi" geliştirmesine güveniyor.

Kanıtların özeti

Turing, Entscheidungsprobleminin hiçbir çözümü olamayacağına dair kanıtında, nihai kanıtına götürecek iki kanıttan yola çıktı. İlk teoremi durma problemiyle en alakalı , ikincisi Rice teoremi ile daha alakalı .

İlk kanıt : keyfi bir "bilgisayar makinesinin" (1, 2, 3, ... tamsayısıyla temsil edildiği gibi) "dairesiz" olup olmadığına karar verebilecek hiçbir "bilgisayar makinesi"nin bulunmadığının (yani, yazdırmaya devam ettiğinin) Number in binary ad infinitum): "...bunu sınırlı sayıda adımda yapmak için genel bir sürecimiz yok" (s. 132, age ). Turing'in kanıtı, "köşegen süreci" kullanıyor gibi görünse de, aslında onun makinesinin (H olarak adlandırılır) tüm diyagonal sayıyı ( Cantor'un köşegen argümanı ) kendi numarasını bile hesaplayamadığını gösterir : "Argümandaki yanlışlık, B [köşegen sayının] hesaplanabilir olduğu varsayımı" ( Karar Verilemez , s. 132). Kanıt çok fazla matematik gerektirmez.

İkinci kanıt : Bu, okuyucular için belki de Rice'ın teoremi olarak daha aşinadır : "Daha fazla gösterebiliriz ki, keyfi bir M makinesinin SD'si ["programı"] ile sağlandığında M'nin hiç olup olmayacağını belirleyecek olan hiçbir makine E olamaz. verilen bir sembolü basar (0 say) " (italikleri, Kararsız , s. 134).

Üçüncü kanıt : "Her M bilgisayar makinesine karşılık gelen bir Un(M) formülü oluşturuyoruz ve Un(M)'nin kanıtlanabilir olup olmadığını belirlemek için genel bir yöntem varsa, o zaman M'nin hiç kanıtlanıp kanıtlanmadığını belirlemek için genel bir yöntem olduğunu gösteriyoruz. 0" yazdırır ( Karar Verilemez , s. 145).

Üçüncü kanıt, birinci lemmayı kanıtlamak için biçimsel mantığın kullanılmasını, ardından ikincisinin kısa bir sözcük kanıtını gerektirir:

Öngörü 1: S1 [sembol "0"], M'nin bazı tam konfigürasyonlarında bantta görünüyorsa, Un(M) kanıtlanabilir. ( Karar Verilemez , s. 147)
Önerme 2: [Tersi] Un(M) kanıtlanabilirse, M'nin tam bir konfigürasyonunda kasette S1 [sembol "0"] görünür. ( Karar Verilemez , s. 148)

Son olarak, Turing, yalnızca 64 sözcük ve sembolle, indirgeme yoluyla "Hilbert Entscheidungsproblem'in hiçbir çözümü olamayacağını" ( Undecidable , s. 145) kanıtlıyor .

İlk kanıtın özeti

Turing bir dizi kısaltma yarattı. Tanımlar için makalenin sonundaki sözlüğe bakın.

Bazı önemli açıklamalar:

Turing'in H makinesi, çapraz sayıda 0 ve 1 yazdırmaya çalışıyor.
Bu diyagonal sayı, H aslında değerlendirme altındaki her "başarılı" makineyi "simüle ettiğinde" ve R-th "başarılı" makinenin R-th "şeklini" (1 veya 0) yazdırdığında oluşturulur.

Turing, makalesinin çoğunu, bizi onların gerçekliğine ikna etmek için makinelerini "inşa etmek" için harcadı. Bu, onun reductio ad absurdum ispat biçimini kullanması için gerekliydi . Bu kanıtın "yapıcı" doğasını vurgulamalıyız. Turing, neyin gerçekten üretilebilir gerçek bir makine olabileceğini anlatıyor. Tek şüpheli unsur, bu kanıtın sonunda imkansız olduğunu gösterecek olan D makinesinin varlığıdır.

Turing, ispata bir “karar/belirleme” makinesi D'nin varlığının iddiasıyla başlar. Herhangi bir SD (A, C, D, L, R, N, noktalı virgül “;”) beslendiğinde, bunun olup olmadığını belirleyecektir. SD (sembol dizisi), "dairesel" - ve bu nedenle "yetersiz u" - veya "dairesiz" - ve dolayısıyla "tatmin edici s" olan bir "bilgisayar makinesini" temsil eder.

Turing daha önce yorumunda, tüm "bilgisayar makinelerinin - bir sayıyı sonsuza kadar 1 ve 0 olarak hesaplayan makineler - evrensel makinenin" bandına bir SD olarak yazılabileceğini göstermişti. evrensel bir makinenin gerçekten var olduğunu gösteren kanıt harcanır, yani
 Gerçekten evrensel bir makine U var
Her N sayısı için gerçekten benzersiz bir SD vardır,
Her Turing makinesinin bir SD'si vardır
U'nun bandındaki her SD, U tarafından “çalıştırılabilir” ve orijinal makine ile aynı “çıktıyı” (şekil 1, 0) üretecektir.

Turing, D makinesinin işini nasıl yaptığı hakkında yorum yapmıyor. Tartışma uğruna, D'nin önce semboller dizisinin "iyi biçimli" olup olmadığına (yani yalnızca bir sembol karmaşası değil, bir algoritma biçiminde) bakacağını ve değilse onu atacağını varsayıyoruz. Sonra “daire avına” gidecekti. Bunu yapmak için belki de "sezgisel" (püf noktaları: öğretilen veya öğrenilen) kullanır. Kanıt amacıyla, bu ayrıntılar önemli değildir.

Turing daha sonra (oldukça gevşek bir şekilde) H adını verdiği bir makinenin izleyeceği algoritmayı (yöntemi) tanımlar. H Makinesi, içinde D karar makinesini içerir (dolayısıyla D, H'nin bir “alt rutinidir”). Makine H'nin algoritması, H'nin talimat tablosunda veya belki de H'nin bant üzerindeki Standart Açıklamasında ifade edilir ve evrensel makine U ile birleştirilir; Turing bunu belirtmez.

Turing, evrensel makine U'yu tarif ederken, bir makinenin SD'sinin (bir "programa" benzer harfler dizisi) bir tam sayıya (8 tabanı) dönüştürülebileceğini ve bunun tersini göstermiştir. Herhangi bir N sayısı (8 tabanındaki), aşağıdaki değiştirmelerle bir SD'ye dönüştürülebilir: 1 ile A, 2 ile C, 3 ile D, 4 ile L, 5 ile R, 6 ile N, 7 ile noktalı virgül ";".

Görünüşe göre, H makinesinin benzersiz numarası (DN), "K" sayısıdır. K'nin çok uzun bir sayı, belki de on binlerce basamak uzunluğunda olduğu sonucunu çıkarabiliriz. Ama bundan sonrası için bu önemli değil.

Makine H, herhangi bir N sayısını, alt makine D'nin test etmesi için eşdeğer bir SD sembol dizisine dönüştürmekten sorumludur . (Programlama dilinde: H, D'ye rastgele bir "SD" iletir ve D, "yeterli" veya "yetersiz" döndürür.) Makine H, başarılı sayıların bir çetelesini ("Kayıt"?) tutmaktan da sorumludur (varsayalım ki, “başarılı” SD'lerin sayısı, yani R, test edilen SD'lerin sayısından çok daha azdır, yani N) Son olarak, H, bandının bir bölümüne diyagonal bir sayı “beta astarlı” B' yazdırır. bu B' (bilgisayar anlamında) her bir "tatmin edici" makinenin/numaranın "hareketlerini" "simüle ederek"; sonunda test edilen bu makine/sayı, Rth "şekline" (1 veya 0) ulaşacaktır ve H H daha sonra simülasyonun bıraktığı “karışıklığı temizlemekten”, N'yi artırmaktan ve testlerine ad infinitum ile devam etmekten sorumludur .

Not: H'nin aradığı tüm bu makineler, Turing'in "bilgisayar makineleri" dediği makinelerdir. Bunlar, Turing'in "rakamlar" dediği sonsuz bir akışta ikili-ondalık sayıları hesaplar: sadece 1 ve 0 sembolleri.

İlk kanıtı göstermek için bir örnek

Bir örnek: Diyelim ki H makinesi 13472 sayıyı test etti ve 5 tatmin edici sayı üretti, yani H, 1'den 13472'ye kadar olan sayıları SD'lere (sembol dizileri) dönüştürdü ve test için D'ye geçirdi. Sonuç olarak H, 5 tatmin edici sayıyı toplamış ve birincisini 1. "şekline", ikincisini 2. hanesine, üçüncüsünü 3. hanesine, dördüncüyü 4. hanesine ve beşincisini de 5. hanesine çalıştırmıştır. Sayı şimdi N = 13472, R = 5 ve B' = ".10011" (örneğin) olarak duruyor. H, kasetindeki pisliği temizler ve devam eder:

H artırır , N = 13473 ve dönüşüm "13473" sembolü dize ADRLD. D alt makinesi ADLRD'yi yetersiz bulursa, H, çetele kaydını R'den 5'te bırakır. H, N sayısını 13474'e yükseltir ve ilerlenir. Öte yandan, eğer D, ADRLD'yi tatmin edici bulursa, o zaman H, R'yi 6'ya yükseltir. H, N'yi (tekrar) ADLRD'ye dönüştürür [bu sadece bir örnektir, ADLRD muhtemelen işe yaramaz] ve evrensel makineyi U kullanarak "çalıştırır". bu test altındaki makine (U "çalışan" ADRLD) 6. “şeklini”, yani 1 veya 0'ı yazdırır. H, bu 6. sayıyı (örn. “0”), bandının “çıkış” bölgesine yazdırır (örn. B' = ".100110").

H, dağınıklığı temizler ve ardından N sayısını 13474'e çıkarır.

H kendi K sayısına ulaştığında tüm süreç çözülür. Örneğimizle ilerleyeceğiz. Başarılı sayım/kayıt R'nin 12'de olduğunu varsayalım. H sonunda kendi sayısı eksi 1'e ulaşır, yani N = K-1 = 4335...321 4 ve bu sayı başarısızdır. Ardından H, K = 4355...321 5 , yani kendi numarasını üretmek için N'yi artırır . H bunu “LDDR...DCAR”a çevirir ve karar-makine D'ye iletir. Karar-makine D'nin "tatmin edici" döndürmesi gerekir (yani: H , tanım gereği teste devam etmeli , sonsuza kadar , çünkü " daire içermeyen"). Böylece H şimdi sayıyı R'yi 12'den 13'e artırıyor ve ardından test edilen K sayısını yeniden SD'ye dönüştürüyor ve onu simüle etmek için U'yu kullanıyor. Ancak bu, H'nin kendi hareketlerini simüle edeceği anlamına gelir. Simülasyonun yapacağı ilk şey nedir? Bu simülasyon K-aka-H ya yeni bir N oluşturur ya da "eski" N'yi 1'e "sıfırlar". Bu "K-aka-H" ya yeni bir R oluşturur ya da "eski" R'yi 0'a "sıfırlar". Eski -H, 12. rakamına ulaşana kadar yeni "K-aka-H"yi "koşar".

Ama asla 13. rakama ulaşamaz; K-aka-H sonunda yine 4355...321 5'e ulaşır ve K-aka-H'nin testi tekrar etmesi gerekir. K-aka-H asla 13. rakama ulaşamayacak. H-makinesi muhtemelen kendi kopyalarını sonsuza kadar boş bant üzerine basar . Ancak bu, H'nin, köşegen sayıların 1'lerini ve 0'larını sonsuza kadar basmaya devam eden, tatmin edici, dairesel olmayan bir bilgi işlem makinesi olduğu öncülüyle çelişir. (N 1'e sıfırlanırsa ve R 0'a sıfırlanırsa aynı şeyi göreceğiz.)

Okuyucu buna inanmıyorsa, karar makinesi D için bir "sap" yazabilir ("D" saplaması "yeterli" dönecektir) ve sonra H makinesinin kendi numarasıyla karşılaştığı anda ne olduğunu kendileri görebilir.

İkinci kanıtın özeti

Bir sayfadan kısa, öncüllerden sonuca geçiş belirsiz.

Turing, reductio ad absurdum ile ilerler . Rastgele bir M makinesinin SD'si (Standart Açıklama, yani "program") verildiğinde, M'nin belirli bir sembolü basıp basmadığını (0 diyelim) belirleyecek olan bir E makinesinin varlığını iddia eder. Bu M'nin bir "bilgisayar makinesi" olduğunu iddia etmiyor.

E makinesinin varlığı göz önüne alındığında, Turing şu şekilde ilerler:

  1. E makinesi varsa, M'nin sonsuz sıklıkta 0 yazdırıp yazdırmayacağını belirleyen bir G makinesi vardır VE
  2. E varsa, M'nin sonsuz sıklıkta 1 yazdırıp yazdırmayacağını belirleyen başka bir süreç vardır [referans için süreci/makineyi G' olarak adlandırabiliriz], BU NEDENLE
  3. G'yi G' ile birleştirdiğimizde, M'nin sonsuz sayıda rakam yazdırıp basmadığını belirleyen bir işlemimiz olur, VE
  4. EĞER "G with G'" işlemi M'nin sonsuz sayıda rakam yazdırdığını belirlerse, SONRA "G with G'", M'nin daire içermediğini belirlemiştir, AMA
  5. M'nin dairesiz olup olmadığını belirleyen bu "G ile G'" işlemi, kanıt 1'e göre var olamaz, BU NEDENLE
  6. E makinesi mevcut değil.

İkinci kanıtın ayrıntıları

İspatın zorluğu 1. adımdır. Turing'in incelikli eserini açıklamadığını fark eden okuyucuya yardımcı olacaktır. (Kısacası: “varoluşsal-” ve “evrensel-işlemciler” arasındaki belirli denklikleri mantıksal işleçlerle yazılmış eşdeğer ifadeleriyle birlikte kullanıyor.)

İşte bir örnek: Diyelim ki önümüzde yüzlerce arabayla dolu bir park yeri görüyoruz. Tüm partiyi dolaşıp "Lastikleri patlamış (kötü) arabalar"ı aramaya karar veriyoruz. Bir saat kadar sonra iki "kötü lastikli araba" bulduk. Artık kesin olarak söyleyebiliriz ki “Bazı arabaların lastikleri kötüdür”. Ya da şöyle diyebiliriz: “'Bütün arabaların lastikleri iyi' olduğu doğru değil”. Veya: “'Tüm arabaların iyi lastikleri olmadığı doğrudur”. Gelelim başka bir kısma. Burada “Tüm arabaların iyi lastikleri vardır” ifadesini keşfediyoruz. “Lastiğinin bozuk olduğu tek bir araba örneği yok” diyebiliriz. Böylece görüyoruz ki, her araba için ayrı ayrı bir şey söyleyebiliyorsak, o zaman TÜMÜ hakkında toplu olarak bir şeyler söyleyebiliriz.

Turing'in yaptığı şudur: M'den bir makine koleksiyonu yaratır { M 1, M 2, M 3, M 4, ..., Mn } ve her biri hakkında bir cümle yazar: “ X en az bir 0 yazdırır” ve sadece iki “ doğruluk değerine ” izin verir , True = boş veya False = :0:. Tek tek her makine için cümlenin doğruluk değerini belirler ve bir dizi boşluk veya :0: veya bunların bir kombinasyonunu yapar. Bunun gibi bir şey elde edebiliriz: “ M 1 a 0 yazdırır” = Doğru VE “ M 2 a 0 yazdırır” = Doğru VE “ M 3 a 0 yazdırır” = Doğru VE “ M 4 a 0 yazdırır” = Yanlış, ... VE “ Mn bir 0 yazdırır” = Yanlış. o ipi alır

BBB:0::0::0: ... :0: ... sonsuza kadar

sonsuz sayıda makine varsa Mn . Öte yandan, her makine bir "Doğru" üretmiş olsaydı, banttaki ifade şöyle olurdu:

BBBBB....BBBB ... sonsuza kadar

Böylece Turing, ayrı ayrı ele alınan her makine hakkındaki ifadeleri, hepsi hakkında tek bir "ifadeye" (string) dönüştürmüştür. Bu ifadeyi yaratan makine (buna G diyor) verildiğinde, onu E makinesiyle test edebilir ve 0 üretip üretmediğini belirleyebilir. Yukarıdaki ilk örneğimizde gerçekten de öyle olduğunu görüyoruz, bu yüzden biliyoruz ki tüm Sıramızdaki M'ler 0'ları yazdırır. Ancak ikinci örnek, dize boşluk olduğundan, dizimizdeki her Mn'nin bir 0 ürettiğini gösteriyor.

Turing'in yapması gereken tek şey, tek bir M'den Mn'ler dizisini yaratmak için bir süreç yaratmak.

M'nin şu kalıbı yazdırdığını varsayalım :

M => ...AB01AB0010AB…

Turing, M'yi alan ve ilk n 0'ları art arda “0-bar”a ( 0 ) dönüştüren bir Mn dizisini ortaya çıkaran başka bir F makinesi yaratır :

Ayrıntıları göstermeden, bu F makinesinin gerçekten üretilebilir olduğunu belirtiyor. Birkaç şeyden birinin olabileceğini görebiliriz. F'nin 0'ları olan makineleri tükenebilir veya "sıfırları iptal etmek" için sonsuza kadar makineler yaratması gerekebilir .

Turing şimdi E ve F makinelerini bir kompozit makine G'de birleştiriyor. G, orijinal M ile başlar, ardından tüm ardıl makineler M1, M2, oluşturmak için F'yi kullanır. . ., Mn. Ardından G, M ile başlayan her makineyi test etmek için E'yi kullanır. E, bir makinenin hiçbir zaman sıfır yazdırmadığını algılarsa, G o makine için :0: yazdırır. E bir makinenin 0 yazdırdığını algılarsa (Turing'in söylemediğini varsayıyoruz) o zaman G :: yazdırır veya bu girişi atlayarak kareleri boş bırakır. Birkaç şeyin olabileceğini görebiliriz.

Tüm
Mn'ler 0'ları yazdırırsa , G hiçbir zaman 0 yazdırmayacaktır, VEYA, tüm M'ler 0'ları yazdırmazsa, VEYA,
G bir süre 0'ları yazdıracak ve sonra duracaktır.

Şimdi, E'yi G'nin kendisine uyguladığımızda ne olur?

E(G), G'nin asla 0 basmadığını belirlerse, o zaman tüm Mn'lerin 0'ları yazdırdığını biliyoruz. Ve bu, Mn'nin tamamı M'den geldiği için, M'nin kendisinin sonsuza kadar 0 yazdırdığı anlamına gelir , VEYA
E(G), G'nin 0 yazdırdığını belirlerse, o zaman tüm Mn'lerin 0'ları yazdırmadığını biliriz; bu nedenle M, 0'ın sonsuzluğunu yazdırmaz .

Aynı işlemi M'nin sonsuz sıklıkta 1 yazdırıp yazdırmadığını belirlemek için de uygulayabiliriz. Bu süreçleri birleştirdiğimizde, M'nin 1'leri ve 0'ları sonsuza kadar yazdırmaya devam edip etmediğini belirleyebiliriz . Böylece M'nin dairesiz olup olmadığını belirlemek için bir yöntemimiz var. Kanıt 1 ile bu imkansız. O halde E'nin var olduğuna dair ilk iddia yanlıştır: E yoktur.

Üçüncü kanıtın özeti

Burada Turing, " Hilbert Entscheidungsprobleminin hiçbir çözümü olamayacağını " kanıtlıyor ( Undecidable , s. 145). işte o

…fonksiyonel hesap K'nin belirli bir U formülünün kanıtlanabilir olup olmadığını belirlemek için genel bir süreç olamayacağını gösterir(ler). ( age .)

Hem Önermeler #1 hem de #2, ispatın gerektirdiği gerekli "IF AND ONLY IF" (yani mantıksal eşdeğerlik ) oluşturmak için gereklidir:

Bir E kümesi, ancak ve ancak hem E hem de onun tümleyeni hesaplanabilir şekilde sayılabilirse, hesaplanabilir olarak karar verilebilir (Franzén, s. 67)

Turing , aslında "M'nin tam bir konfigürasyonunda , bantta 0 görünür " diyen bir Un (M) formülünün varlığını gösterir (s. 146). Bu formül DOĞRU, yani "inşa edilebilir" ve bunun nasıl yapılacağını gösteriyor.

Ardından Turing, ilki tüm sıkı çalışmayı gerektiren iki Lemma'yı kanıtlıyor. (İkincisi, birincinin tersidir.) Ardından , nihai sonucunu kanıtlamak için reductio ad absurdum'u kullanır :

  1. Un (M) formülü vardır . Bu formül DOĞRUDUR VE
  2. Eğer Entscheidungsproblem sonra çözülebilir mekanik bir süreç olup olmadığının belirlenmesi için mevcut Un (M) olduğu kanıtlanabilir (türetilebilen), ve
  3. Önermeler 1 ve 2: Un (M) kanıtlanabilir EĞER VE YALNIZCA 0 , M'nin bazı "tam konfigürasyonunda" görünüyorsa, VE
  4. EĞER 0 , M'nin bazı "tam konfigürasyonunda" görünüyorsa, M rasgele yazdırılıp yazdırılmayacağını belirleyecek mekanik bir süreç var 0 , VE
  5. Kanıt 2'ye göre, keyfi M'nin hiç 0 yazdırıp yazdırmayacağını belirleyecek hiçbir mekanik işlem yoktur , BU NEDENLE
  6. Un (M) kanıtlanabilir değildir ( DOĞRU'dur , ancak kanıtlanamaz ) bu, Entscheidungsproblem'in çözülemez olduğu anlamına gelir .

Üçüncü kanıtın ayrıntıları

[Eğer okuyucular ispatı ayrıntılı olarak incelemek istiyorlarsa, Turing'in sağladığı düzeltmelerle üçüncü ispatın sayfalarının kopyalarını düzeltmelidirler. Okuyucular ayrıca (i) mantık (ii) Kurt Gödel'in makalesinde sağlam bir altyapıya sahip olmalıdırlar : " On Formally Undecidable Propositions of Principia Mathematica ve Related Systems " ( Undecidable , s. 5). Gödel'in makalesiyle ilgili yardım için, örneğin Ernest Nagel ve James R. Newman , Gödel's Proof , New York University Press, 1958.]

Teknik ayrıntıları takip etmek için okuyucunun "kanıtlanabilir" tanımını anlaması ve önemli "ipuçlarının" farkında olması gerekir.

"İspatlanabilir", Gödel anlamında, (i) aksiyom sisteminin kendisinin "Bu cümle kanıtlanabilir" cümlesini üretecek (ifade edecek) kadar güçlü olduğu ve (ii) herhangi bir keyfi "iyi biçimlendirilmiş" kanıtta olduğu anlamına gelir. aksiyomlar, tanımlar ve sonucun sembollerinin yerine geçen semboller.

İlk ipucu: "M'nin tanımını §6'nın ilk standart biçimine koyalım". Bölüm 6, bir "evrensel makine" U'nun bandı üzerindeki M makinesinin çok özel "kodlanmasını" anlatmaktadır. Bu, okuyucunun Turing'in evrensel U makinesinin ve kodlama şemasının bazı özelliklerini bilmesini gerektirir.

(i) Evrensel makine, bir "talimat tablosunda" bulunan bir dizi "evrensel" talimattır. Bundan ayrı olarak, U'nun bandında bir "bilgi işlem makinesi" M, "M-kodu" olarak bulunacaktır. Evrensel talimat tablosu bant üzerine A, C, D, 0, 1, u, v, w, x, y, z, : sembollerini yazdırabilir . Çeşitli makineler M bu sembolleri yalnızca dolaylı olarak U'ya bunları yazdırması için komut vererek yazdırabilir.

(ii) M'nin "makine kodu" sadece birkaç harften ve noktalı virgülden oluşur, yani D, C, A, R, L, N, ; . M'nin "kodunun" hiçbir yerinde sayısal "şekiller" (semboller) 1 ve 0 asla görünmeyecektir. M, U'nun koleksiyon boşluğundan 0, 1 bir sembol yazdırmasını isterse, U'ya bunları yazdırmasını söylemek için aşağıdaki kodlardan birini kullanır. İşleri daha da kafa karıştırıcı hale getirmek için Turing bu sembolleri S0, S1 ve S2 olarak adlandırır, yani

boş = S0 = D
0 = S1 = DC
1 = S2 = DCC

(iii) Bir "bilgisayar makinesi", ister doğrudan bir masaya yerleştirilmiş olsun (ilk örneklerinin gösterdiği gibi), ister evrensel makine U'nun bandında makine kodu M olarak, numarasını boş bir bant üzerine yazdırır (M'nin sağında). -kod varsa) 1 s ve 0 s olarak sonsuza kadar sağa doğru ilerler .

(iv) Bir "bilgisayar makinesi" U+"M-kodu" ise, kasette önce "M-kodu" görünür; bandın bir sol ucu vardır ve "M-kodu" oradan başlar ve alternatif karelerde sağa doğru ilerler. M kodu sona erdiğinde (ve bu M kodlarının sonlu algoritmalar olduğu varsayımından dolayı böyle olması gerekir), "rakamlar" alternatif karelerde 1 s ve 0 s olarak başlayacak ve sonsuza kadar sağa doğru ilerleyecektir. Turing, (boş) alternatif kareleri ("E"- "silinebilir"- kareler olarak adlandırılır) kullanarak U+"M-kodunun" hem M kodunda hem de "rakamlarda" hesaplamaların nerede olduğunu takip etmesine yardımcı olur. makine yazdırıyor.

(v) "Tam yapılandırma", o ana kadar M kodu ve "şekiller" dahil olmak üzere bant üzerindeki tüm sembollerin, o anda taranmakta olan şekille birlikte basılmasıdır. taranan sembol?). Turing'in anlamını doğru yorumlamışsak, bu çok uzun bir semboller dizisi olacaktır. Ancak M kodunun tamamının tekrarlanması gerekip gerekmediği belirsizdir; sadece mevcut M-kodu talimatının basılması ve ayrıca tüm şekillerin bir şekil işaretçisi ile basılması gereklidir).

(vi) Turing, "M-kodu"ndaki (yine: bantta görünen M kodu) olası çok sayıda talimatı küçük bir kurallı kümeye indirdi, buna benzer üçten biri: {qi Sj Sk R ql} örneğin , makine #qi talimatını yürütüyorsa ve taranan karede Sj sembolü varsa, o zaman Sk sembolünü yazdırın ve Sağa gidin ve ardından ql talimatına gidin : Diğer talimatlar benzerdir, "Sol" L ve "Hareket yok" N için kodlanır qi = DA...A, Sj = DC...C, Sk = DC...C, R, ql = DA....A sembolleri dizisi ile kodlanan bu kümedir. Her talimat diğerinden noktalı virgülle ayrılır. Örneğin, {q5, S1 S0 L q3} şu anlama gelir: Talimat #5: Taranan sembol 0 ise boş yazdırın , Sola gidin, ardından talimat #3'e gidin. Aşağıdaki gibi kodlanmıştır

; DAAAAADCDLDAAA

İkinci ipucu: Turing, Gödel'in makalesinde tanıtılan fikirleri, yani Un (M) formülünün (en azından bir kısmının) "Gödelleştirilmesini" kullanıyor . Bu ipucu yalnızca 138. sayfada bir dipnot olarak görünür ( Karar Verilemez ): "Bir r asal sayı dizisi ^ (r) ile gösterilir " ( age .) [Burada, parantez içindeki r "yükseltilmiştir".] Bu "asal sayılar dizisi" F^(n) adlı bir formülde görünür.

Üçüncü ipucu: Bu, ikinci ipucunu güçlendirir. Turing'in ispata yönelik orijinal girişimi şu ifadeyi kullanır:

(Eu)N(u) & (x)(... vb. ...) ( Karar Verilemez , s. 146)

Makalede daha önce Turing bu ifadeyi daha önce kullanmıştı (s. 138) ve N(u)'yu "u negatif olmayan bir tam sayıdır" ( ibid .) (yani bir Gödel sayısı) anlamında tanımlamıştı . Ancak, Bernays düzeltmeleriyle, Turing bu yaklaşımı (yani N(u) kullanımı) terk etti ve "Gödel sayısının" açıkça göründüğü tek yer F^(n) kullandığı yerdir.

Bu kanıt için ne anlama geliyor? İlk ipucu, bant üzerindeki M kodunun basit bir incelemesinin, U+"M-kodu" ile bir 0 sembolü yazdırılıp yazdırılmadığını ortaya çıkarmayacağı anlamına gelir . Bir test makinesi, bir talimatı temsil eden sembol dizilerinden birinde DC'nin görünümünü arayabilir. Ama bu talimat hiç "yürütülecek mi?" Bir şeyin öğrenmek için "kodu çalıştırması" gerekir. Bu bir şey bir makine olabilir veya resmi bir ispatta çizgiler olabilir, örneğin Lemma #1.

İkinci ve üçüncü ipuçları, temeli Gödel'in makalesi olduğu için ispatın zor olduğu anlamına gelir.

Aşağıdaki örnekte aslında basit bir "teorem" oluşturacağız - küçük bir Post-Turing makine programı "çalıştır". Düzgün tasarlanmış bir teoremin ne kadar mekanik olabileceğini göreceğiz. Bir ispat, göreceğimiz gibi, başlangıca bir "kanıt örneği" ekleyerek ve sonunda neyin ortaya çıktığını görerek yaptığımız teoremin bir "testi"dir.

Hem Önermeler #1 hem de #2, ispatın gerektirdiği gerekli "IF AND ONLY IF" (yani mantıksal denkliği) oluşturmak için gereklidir:

Bir E kümesi, ancak ve ancak hem E hem de onun tümleyeni hesaplanabilir şekilde sayılabilirse, hesaplanabilir olarak karar verilebilir. (Franzen, s. 67)

Franzén'den alıntı yapmak için:

Eğer A ya da onun olumsuzlaması S'de kanıtlanabilirse, bir A cümlesinin resmi bir S sisteminde karar verilebilir olduğu söylenir. (Franzén, s. 65)

Franzén daha önce kitabında "kanıtlanabilir" tanımını yapmıştı:

Biçimsel bir sistem, sistemin teoremlerini türetmek için kullanılan bir aksiyomlar sistemi (resmen tanımlanmış bir dilde ifade edilir) ve akıl yürütme kurallarıdır (çıkarım kuralları olarak da adlandırılır) . Bir teorem , aksiyomlardan başlayarak akıl yürütme kurallarının bir dizi uygulamasıyla elde edilebilen sistemin dilindeki herhangi bir ifadedir. Bir dayanıklı olan sonuç olarak bir teoremine açan, örneğin bir uygulama sonlu dizisidir. ( age. s. 17)

Dolayısıyla bir "cümle" bir semboller dizisidir ve bir teorem bir semboller dizisidir.

Turing aşağıdaki görevle karşı karşıyadır:

Bir dönüştürmek için Evrensel Turing makinası , bir (canavarca uzunluğunda) -yani bir "teoremi" içine "programını" ve banda sayısal semboller (Turing'in "rakamları", semboller "1" ve "0"), cümlelerin dize makinenin ardışık eylemlerini, (tümü) bandın şekillerini ve "bant kafasının" yerini tanımlayan.

Böylece "cümleler dizisi" sembol dizileri olacaktır. İzin verilen tek tek semboller, Gödel'in makalesinde tanımlanan sembollerinden gelecektir.(Aşağıdaki örnekte, "şekil"in makine tarafından taranan sembol olduğunu belirtmek için "şekil" etrafında "<" ve ">" kullanıyoruz. ).

Üçüncü kanıtı göstermek için bir örnek

Aşağıda, Turing'in "bilgisayar makinelerinin" her birinin "boş bant" üzerinde çalışmaya başlayan bir ikili sayı üreteci/yaratıcısı olduğunu kendimize hatırlatmalıyız. Düzgün bir şekilde inşa edildiğinde, her zaman sonsuza kadar uzaklaşır, ancak talimatları her zaman sonludur. Turing'in kanıtlarında, Turing'in kasetinin bir “sol ucu” vardı, ancak sonsuza dek uzatıldı. Aşağıdaki örnek için, "makinenin" bir Üniversal makine değil, Tablodaki talimatlarla daha basit "özel makine" olduğunu varsayacağız.

Örneğimiz, bir Turing Makinesinin değiştirilmiş Post-Turing makine modeline dayanmaktadır. Bu model sadece 0 ve 1 sembollerini yazdırır. Boş bandın tamamı b'ler olarak kabul edilir. Değiştirilmiş modelimiz, Turing Sonrası 7 talimatına iki talimat daha eklememizi gerektiriyor. Kullanacağımız kısaltmalar:

R, SAĞ: sağa bakın ve şeridi sola hareket ettirin veya şerit kafasını sağa hareket ettirin
L, SOL : sola bakın ve şeridi sağa hareket ettirin veya şerit kafasını sola hareket ettirin
E, Taranan kareyi SİL (örn. kareyi boş yap)
P0 ,: Taranan kare
P1'e 0 YAZDIR: Taranan kareye 1 YAZDIR
Jb_n, JUMP-IF-boş-
yönerge_ #n, J0_n, JUMP-IF-0-
yönerge_ #n, J1_n, JUMP-IF-1 -to-instruction_#n, DUR
.

R, L, E, P0 ve P1 durumlarında görevini yaptıktan sonra makine bir sonraki komuta sayısal sırayla devam eder; Testleri başarısız olursa atlamalar için aynen.

Ancak, kısaca, örneklerimiz yalnızca üç kare kullanacaktır. Ve bunlar her zaman solda taranan kare ile boşluklar olduğu için başlayacaktır: yani bbb. İki sembol 1, 0 ve boş ile 27 farklı konfigürasyona sahip olabiliriz:

bbb, bb0, bb1, b0b, b00, b01, b1b, b10, b11, 0bb, 0b0, 0b1, 00b, 000, 001, 01b, 010, 011, 1bb, 1b0, 1b1, 10b, 100, 101, 11b, 110, 111

Burada dikkatli olmalıyız, çünkü bir algoritmanın (geçici olarak) rakamlar arasında boşluk bırakması, sonra geri gelip bir şeyler doldurması oldukça olasıdır. Daha büyük olasılıkla, bir algoritma bunu kasıtlı olarak yapıyor olabilir. Aslında, Turing'in makinesi bunu yapıyor - alternatif kareler üzerine yazdırıyor, şekiller arasında boşluklar bırakarak konum belirleyici sembolleri yazdırabiliyor.

Turing her zaman alternatif kareleri boş bıraktı, böylece makinesi bir şeklin soluna bir sembol (veya makine evrensel makineyse ve taranan kare aslında “program”daysa bir harf) yerleştirebilirdi. Küçük örneğimizde bundan vazgeçeceğiz ve taranan sembolün etrafına aşağıdaki gibi semboller ( ) koyacağız:

b(b)0 bunun anlamı, "Bant sol boşluğun solundaki boşluktur, ancak boş bırakılan 'oyunda', taranan-kare-boş, '0', boşluklar sağa doğru"
1 (0)1 bunun anlamı, "Bant solda boşluklar, ardından 1, taranan kare '0'"

Basit bir program yazalım:

başlangıç: P1, R, P1, R, P1, H

Her zaman boş bantla başladığımızı unutmayın. Tam yapılandırma, şerit üzerindeki sembolleri ve ardından bir sonraki talimatı yazdırır:

yapılandırmayı başlat: (b) P1,
yapılandırma #1: (1) R,
yapılandırma #2: 1(b) P1,
yapılandırma #3: 1(1) R,
yapılandırma #4: 11(b) P1,
yapılandırma #5 : 11(1) H

Formüle “atlama” ekleyelim. Bunu yaptığımızda, tam konfigürasyonun neden şerit sembollerini içermesi gerektiğini keşfederiz. (Aslında bunu aşağıda daha iyi görüyoruz.) Bu küçük program sağa üç “1” yazdırır, yönü tersine çevirir ve boşluk kalana kadar 0'ları yazdırarak sola hareket eder. Makinemizin kullandığı tüm sembolleri yazdıracağız:

başlangıç: P1, R, P1, R, P1, P0, L, J1_7, H
(b)bb P1,
(1)bb R,
1(b)b P1,
1(1)b R,
11(b) P1 ,
11(1) P0,
11(0) L,
1(1)0 J1_7
1(1)0 L
(1)10 J0_7
(1)10 L
(b)110 J0_7
(b)110 H

Burada sonunda, soldaki boşluğun “oynamaya başladığını” görüyoruz, bu yüzden onu toplam konfigürasyonun bir parçası olarak bırakıyoruz.

İşimizi doğru yaptığımıza göre başlangıç ​​koşullarını toplayıp “teoremin nereye gittiğini” görüyoruz. Ortaya çıkan konfigürasyon—110 sayısı—PROOF'tur.

  • Turing'in ilk görevi, Un(M)'inin tam olarak ne yapacağını ifade etmek için mantık sembollerini kullanarak genelleştirilmiş bir ifade yazmak zorundaydı.
  • Turing'in ikinci görevi, Gödel'in yöntemine göre, Gödel'in sembollere asal sayılar atama ve asal sayıları asal kuvvetlere yükseltme tekniğini kullanarak bu son derece uzun sembol dizisini "Gödelleştirmek".

komplikasyonlar

Turing'in kanıtı çok sayıda tanımla karmaşıktır ve Martin Davis'in "küçük teknik ayrıntılar" ve "...verildiği gibi yanlış olan teknik ayrıntılar" dediği şeylerle karıştırılmıştır (Davis'in Undecidable'daki yorumu , s. 115). Turing'in kendisi 1938'de "Bir Düzeltme" yayınladı: "Yazar, bu hatalara işaret ettiği için P. Bernays'a borçludur " ( Karar Verilemez , s. 152).

Spesifik olarak, orijinal biçiminde üçüncü kanıt, teknik hatalarla kötü bir şekilde gölgelenmiştir. Bernays'in önerilerinden ve Turing'in düzeltmelerinden sonra bile, evrensel makinenin tanımında hatalar kaldı . Ve kafa karıştırıcı bir şekilde, Turing orijinal makalesini düzeltemediğinden, vücudun içindeki bazı metinler Turing'in kusurlu ilk çabasına atıfta bulunuyor.

Bernays'in düzeltmeleri Undecidable , s. 152–154'te bulunabilir; orijinali "On Computable Numbers, with a Application to the Entscheidungsproblem. A Correction", Proceedings of the London Mathematical Society (2), 43 (1938), 544-546.

Turing'in makalesinin çevrimiçi versiyonunda bu düzeltmeler bir ekte yer almaktadır; bununla birlikte, Universal Machine'deki düzeltmeler, Emil Post tarafından sağlanan bir analizde bulunmalıdır .

İlk başta, ispatın ayrıntılarına yakından dikkat eden tek matematikçi Post'tu (cf. Hodges s. 125) - esas olarak, aynı anda "algoritmanın" ilkel makine benzeri eylemlere benzer bir indirgemesine vardığı için, bu yüzden o kanıtla kişisel olarak ilgilendi. Garip bir şekilde (belki de İkinci Dünya Savaşı araya girdi) Post'un bunu , 1947'de yayımladığı Recursive Unsolvability of a Problem of Thue adlı makalesinin ekinde ( Undecidable , s. 293) incelemesi on yıl kadar aldı .

Başka sorunlar da kendini gösteriyor: Ek Postasında dolaylı olarak makalenin zorluğu ve doğrudan "anahatları" (Post in Undecidable , s. 299) ve ispatların "sezgisel biçimi" ( aynı yerde ) hakkında yorum yapıldı. Post çeşitli noktalara varmak zorunda kaldı:

Eleştirimiz doğruysa, sonsuz sayıda 0'lar ve 1'ler basan bir Turing hesaplama makinesiyse, bir makinenin çembersiz olduğu söylenir. Ve Turing'in söz konusu iki teoremi gerçekten aşağıdaki gibidir. Rasgele bir pozitif tamsayı n ile sağlandığında, n'nin daire içermeyen bir Turing hesaplama makinesinin DN'si olup olmadığını belirleyecek Turing ... makinesi yoktur. [İkinci olarak], keyfi bir pozitif tamsayı n ile sağlandığında, n'nin belirli bir sembolü basan (0 demek) bir Turing hesaplama makinesinin DN'si olup olmadığını belirleyecek hiçbir Turing kural makinesi yoktur. ( Karar Verilemez , s. 300'e gönderin )

Makaleyi okumayı deneyen herkes Hodges'ın şikayetini anlayacaktır:

Kağıt çekici bir şekilde başladı, ancak çok geçmeden (tipik Turing tarzında) evrensel makine için talimat tablosunu geliştirmek için belirsiz Alman Gotik tipi bir çalılığa daldı. Buna göz atacak son kişiler, pratik hesaplamaya başvurmak zorunda kalan uygulamalı matematikçiler olacaktır... (Hodges s. 124)

Turing tarafından kullanılan terimler sözlüğü

1 hesaplanabilir sayı — ondalık basamağı bir makine tarafından hesaplanabilen bir sayı (yani, bir algoritma gibi sonlu yollarla)

2 M — sonlu talimat tablosu ve tarama/yazdırma kafası olan bir makine. M, her biri "bir sembol taşıyabilen" karelere bölünmüş sonsuz bir şeridi hareket ettirir. Makine talimatları sadece aşağıdaki gibidir: taranan karede bir kare sola, bir kare sağa hareket ettirin, p sembolünü yazdırın, taranan kareyi silin, eğer sembol p ise o zaman aaa komutunu yapın, taranan sembol p değilse o zaman yap talimatı aaa, taranan sembol yok ise o zaman aaa talimatını yapın, taranan sembol herhangi bir do talimatı aaa ise [burada “aaa” bir talimat tanımlayıcıdır].

3 bilgisayar makinesi — iki tür sembol basan bir M, birinci tipteki sembollere “şekiller” denir ve sadece ikili semboller 1 ve 0'dır; ikinci türün sembolleri diğer sembollerdir.

4 rakam - 1 ve 0 sembolleri , namı diğer "birinci tür semboller"

5 m konfigürasyonu - talimat tanımlayıcısı, talimat tablosundaki bir sembol veya evrensel makinenin bandındaki talimat numarasını temsil eden bir sembol dizisi (örneğin "DAAAAA = #5")

İkinci türden 6 sembol — 1 ve 0 dışında herhangi bir sembol

7 dairesel — başarısız bir hesaplama makinesi. Hesapladığı sayıyı ikili olarak temsil eden 0 veya 1 rakamlarını sonsuza kadar yazdıramıyor

8 dairesiz — başarılı bir hesaplama makinesi. Hesapladığı sayıyı ikili olarak temsil eden 0 veya 1 rakamlarını sonsuza kadar yazdırır.

9 dizi — "makine tarafından hesaplanan dizi"deki gibi: birinci tür semboller, diğer adıyla rakamlar, 0 ve 1 simgeleri.

10 hesaplanabilir dizi — daire içermeyen bir makine tarafından hesaplanabilir

11 SD – Standart Açıklama: A, C, D, L, R, N, “;” sembolleri dizisi Turing makinesi bandında

12 DN — Açıklama Numara: sayıya dönüştürülen bir SD: 1=A, 2=C, 3 =D, 4=L, 5=R, 6=N, 7=;

13 M(n) — DN numarası “n” olan bir makine

14 tatmin edici — daire içermeyen bir makineyi temsil eden bir SD veya DN

15 U - "evrensel" bir talimat tablosu ile donatılmış bir makine. Eğer U, "başında bir bilgisayar M makinesinin SD'sinin yazılı olduğu bir bantla birlikte verilirse, U, M ile aynı diziyi hesaplayacaktır."

16 β' —“beta-asallı”: n'inci hesaplanabilir dizinin n'inci rakamından (yani 0 veya 1) oluşan bir sözde “köşegen sayı” [ayrıca: H'nin hesaplanabilir sayısı, aşağıya bakın ]

17 u — yetersiz, yani dairesel, SD

18 sn — tatmin edici, yani daire içermeyen SD

19 D - H'de bulunan bir makine (aşağıya bakınız). Herhangi bir bilgisayar M makinesinin SD'si ile birlikte verildiğinde, D, M'nin SD'sini test eder ve dairesel ise “u” ile, daire içermiyorsa “s” ile işaretleyin.

20 H - bir bilgisayar makinesi. H, B'yi hesaplar, R ve N'yi korur. H, D ve U'yu ve N ve R'yi koruyan ve D'ye N'nin eşdeğer SD'sini sağlayan belirtilmemiş bir makine (veya süreç) içerir. E ayrıca B' şekillerini hesaplar ve şekilleri birleştirir B'.

21 R — D tarafından test edilen başarılı (dairesiz) SD miktarının kaydı veya çetelesi

22 N — 1 ile başlayan, makine E tarafından SD'ye dönüştürülecek bir sayı. E, N'yi korur.

23 K - bir sayı. H'nin DN'si.

Kanıt #3 için gerekli

5 m konfigürasyonu — talimat tanımlayıcısı, talimat tablosundaki bir sembol veya evrensel makinenin bandındaki talimatın numarasını temsil eden bir sembol dizisi (örneğin "DAAAAA = talimat #5"). Turing'in SD'sinde m-yapılandırması her komutta iki kez görünür, en soldaki dizi "mevcut talimat"tır; en sağdaki dize bir sonraki talimattır.

24 tam konfigürasyon - taranan karenin numarası (şekil 1 veya 0 ), bant üzerindeki tüm sembollerin tam sırası ve m konfigürasyonu (talimat tanımlayıcısı, bir sayıyı temsil eden bir sembol veya bir sembol dizisi, örneğin "DAAAA komutu = #5")

25 RSi(x, y) — "M'nin tam x konfigürasyonunda y karesindeki sembol Si'dir ; "tam konfigürasyon" tanım # 5'tir

26 I(x, y) — "M'nin tam x konfigürasyonunda y karesi taranır"

27 Kqm(x) — "M'nin x konfigürasyonunun tamamında makine konfigürasyonu (komut numarası) qm'dir"

28 F(x,y) — "y, x'in doğrudan ardılıdır" (Gödel'in ardıl-fonksiyon olarak "f" kullanımını takip eder).

29 G(x,y) — " x, y'den önce gelir", hemen olması gerekmez

30 Inst{qi, Sj Sk L ql} , Inst{qi, Sj Sk R ql} ve Inst{qi, Sj Sk N ql} gibi bir kısaltmadır . Aşağıya bakınız.

Turing, talimat setini biri Sol, Sağ ve Hareketsizlik için olmak üzere üç “kanonik forma” indirger. Si ve Sk kasetteki sembollerdir.

kaset son
m-config Sembol Operasyonlar m-config
qi Si PSk, L metrekare
qi Si PSk, R metrekare
qi Si PSk, N metrekare

Örneğin, ilk satırdaki işlemler A, C, D, 0, 1, u, v, w, x, y, z, : koleksiyonundan PSk = PRINT sembolü Sk'dir , ardından bandı SOL hareket ettirin.

Bunları ayrıca şu şekilde kısalttı: (N1) qi Sj Sk L qm (N2) qi Sj Sk R qm (N3) qi Sj Sk N qm

İspat #3'te bunlardan ilkini “Inst{qi Sj Sk L ql}” olarak adlandırır ve tüm makine SD'sinin mantıksal bağlaç (mantıksal VEYA) olarak nasıl yazılacağını gösterir: bu dizgiye “Des(M)” denir. , "Description-of-M"de olduğu gibi. yani, makine 0'ı, ardından 1'leri ve 0'ları alternatif karelere sağdaki sonsuzluğa yazdırırsa, tabloya sahip olabilir (benzer bir örnek sayfa 119'da görülmektedir):

q1, boş, P0, R, q2
q2, boş, P-boş, R, q3
q3, boş, P1, R, q4
q4, boş, P-boş, R, q1

(Bu, “p-blank” komutları ile kanonik forma indirgenmiştir, bu nedenle Turing'in örneğinden biraz farklıdır.) Eğer onları “Inst( ) formuna” koyarsanız, komutlar aşağıdaki gibi olacaktır (unutma: S0 boştur, S1 = 0, S2 = 1):

Inst {q1 S0 S1 R q2}
Inst {q2 S0 S0 R q3}
Inst {q3 S0 S2 R q4}
Inst {q4 S0 S0 R q1}

Standart Açıklamaya (SD) yapılan azalma:

; DADDCRDAA ; DAADDRDAAA ; DAAAADDCCRDAAAA ; DAAAADDRDA ;

Bu, kitaptaki örneğiyle uyuşuyor (her harf ve sayı arasında bir boşluk olacak). Evrensel makine U, alternatif boş kareleri "işaretçiler" koymak için yerler olarak kullanır.

Referanslar

  • Turing, AM (1937), "Entscheidungsproblem için bir Uygulama ile Hesaplanabilir Sayılar Üzerine", Londra Matematik Derneği Bildirileri , 2, 42 (1), s. 230–65, doi : 10.1112/plms/s2-42.1. 230
  • Turing, AM (1938), "Entscheidungsproblem'e bir Uygulama ile Hesaplanabilir Sayılar Üzerine. Bir Düzeltme", Londra Matematik Derneği Bildirileri , 2, 43 (6), s. 544–6, doi : 10.1112/plms/s2 -43.6.544). ( Çevrimiçi versiyon .) Bu, Turing'in Turing makinelerini tanımladığı çığır açan makaledir , Entscheidungsproblem'in çözülemez olduğunu gösterir .
  • Hans Reichenbach (1947), Sembolik Mantığın Unsurları , Dover Publications, Inc., New York.
  • Martin Davis (1965), Karar Verilemez , Karar Verilemez Önermeler, Çözülemez Problemler ve Hesaplanabilir Fonksiyonlar Üzerine Temel Makaleler , Raven Press, New York. Yukarıda atıfta bulunulan iki Post makalesi bu ciltte yer almaktadır. Diğer makaleler Gödel, Church, Rosser ve Kleene'ninkileri içerir.
  • Andrew Hodges (1983), Alan Turing: The Enigma , Simon and Schuster , New York. Bkz. Kanıtına yol açan bir tarih ve onun tartışması için "Gerçeğin Ruhu" Bölümü.
  • Torkel Franzén (2005), Gödel Teoremi: Kullanımı ve Kötüye Kullanımı İçin Eksik Bir Kılavuz . AK Peters.