Turing bütünlüğü - Turing completeness

Bu terimin oracle makineleri tarafından göreli hesaplanabilirlik teorisinde kullanımı için, bkz. Turing indirgemesi .

In Hesaplama teorisi , (bir bilgisayarın olarak veri manipülasyon kurallar sistemi talimat seti , bir programlama dili ya da bir hücresel otomat ) olduğu söylenir Turing-tam veya hesaplama evrensel herhangi simüle etmek kullanılıp kullanılamayacağını Turing makinesi . Bu, bu sistemin diğer veri işleme kural kümelerini tanıyabileceği veya karar verebileceği anlamına gelir. Turing tamlığı, böyle bir veri işleme kural setinin gücünü ifade etmenin bir yolu olarak kullanılır. Bugün neredeyse tüm programlama dilleri Turing-tamamlandı. Konsept, İngiliz matematikçi ve bilgisayar bilimcisi Alan Turing'in adını almıştır .

İlgili bir kavram Turing denkliğidir  - eğer P, Q'yu simüle edebiliyorsa ve Q, P'yi simüle edebiliyorsa, iki P ve Q bilgisayarına eşdeğer denir. Church-Turing tezi , değerleri bir algoritma tarafından hesaplanabilen herhangi bir fonksiyonun bir Turing makinesi ve bu nedenle, herhangi bir gerçek dünyadaki bilgisayar bir Turing makinesini simüle edebiliyorsa, Turing makinesine eşdeğerdir. Bir evrensel Turing makinesi herhangi Turing makinesi ve uzantısı tarafından olası gerçek dünya bilgisayarın hesaplama açısından taklit etmek için kullanılabilir.

Bir şeyin Turing-tamamlanmış olduğunu göstermek için, onun bazı Turing-tamamlanmış sistemleri simüle etmek için kullanılabileceğini göstermek yeterlidir. Örneğin, bir zorunluluk dil o varsa Turing-tamamlandıktan koşullu dallanma (örn ve "git" ifadeleri "eğer" veya bir "dal eğer sıfır" talimat; bkz tek talimat seti bilgisayar ) ve keyfi bir değiştirme yeteneği bellek miktarı (örneğin, rastgele sayıda veri öğesini koruma yeteneği). Elbette hiçbir fiziksel sistem sonsuz belleğe sahip olamaz; ancak sonlu belleğin sınırlaması göz ardı edilirse, çoğu programlama dili aksi takdirde Turing-tamamlanır.

Matematiksel olmayan kullanım

Gelen argo kullanımı, terimler "Turing tamamlama" ve "Turing-eşdeğeri" herhangi bir gerçek hayattaki genel amaçlı bilgisayar veya bilgisayar dili başka gerçek dünya genel amaçlı bilgisayarın hesaplama yönlerini taklit veya yaklaşık anlamına kullanılır bilgisayar dili.

Şimdiye kadar yapılmış gerçek bilgisayarlar, tek bantlı bir Turing makinesi gibi (hafızalarına karşılık gelen "bant") işlevsel olarak analiz edilebilir; böylece ilişkili matematik, işlemlerini yeterince soyutlayarak uygulanabilir. Ancak, gerçek bilgisayarların sınırlı fiziksel kaynakları vardır, bu nedenle bunlar yalnızca doğrusal sınırlı otomat eksiksizdir. Buna karşılık, evrensel bir bilgisayar , Turing-complete komut setine, sonsuz belleğe ve sonsuz kullanılabilir zamana sahip bir cihaz olarak tanımlanır.

Resmi tanımlar

Gelen Hesaplama teorisi , birkaç yakından ilgili şartlar (örneğin, bir bir bilgisayar sisteminin hesaplama gücünü tarif etmek için kullanılan arka makinesi ya da bir programlama dili )

Turing bütünlüğü
Turing- hesaplanabilir her fonksiyonu hesaplayabilen bir hesaplama sistemine Turing-complete (veya Turing-güçlü) denir. Alternatif olarak, böyle bir sistem evrensel bir Turing makinesini simüle edebilen bir sistemdir .
Turing denkliği
Bir Turing-complete sistemi, hesaplayabildiği her fonksiyon aynı zamanda Turing-hesaplanabilir ise, Turing-eşdeğeri olarak adlandırılır; yani, Turing makineleriyle tam olarak aynı işlev sınıfını hesaplar . Alternatif olarak, bir Turing eşdeğeri sistem, evrensel bir Turing makinesi tarafından simüle edilebilen ve simüle edilebilen sistemdir. (Bilinen tüm fiziksel olarak uygulanabilen Turing-tamamlanmış sistemler, Church-Turing tezine destek ekleyen Turing eşdeğeridir .)
(Hesaplamalı) evrensellik
Bir sistem, o sınıftaki sistemler tarafından hesaplanabilen her işlevi hesaplayabiliyorsa (veya bu sistemlerin her birini simüle edebiliyorsa), bir sistem sınıfına göre evrensel olarak adlandırılır. Tipik olarak, evrensellik terimi, Turing-complete bir sistem sınıfına göre zımnen kullanılır. "Zayıf evrensel" terimi bazen , evrenselliği yalnızca Turing makinesinin standart tanımını sonsuz sayıda 1'li giriş akışlarını içerecek şekilde değiştirerek elde edilen bir sistemi (örneğin bir hücresel otomat ) ayırt etmek için kullanılır .

Tarih

Turing bütünlüğü, bir bilgi işlem cihazı için her gerçek dünya tasarımının evrensel bir Turing makinesi tarafından simüle edilebilmesi açısından önemlidir . Church-Turing tezi evrensel Turing makinesi, ilke olarak, herhangi bir başka programlanabilir herhangi hesaplama gerçekleştirebileceği - Bu bir matematik kanunu olduğunu devletler bilgisayar can. Bu, programı yazmak için gereken çaba veya makinenin hesaplamayı gerçekleştirmesi için gereken süre veya makinenin sahip olabileceği ve hesaplama ile ilgisi olmayan herhangi bir yetenek hakkında hiçbir şey söylemez.

Charles Babbage 'ın analitik motoru o tasarlandı zamanda yapılmış olsaydı (1830'lar) ilk Turing-tam makine olurdu. Babbage, makinenin ilkel mantıksal akıl yürütme de dahil olmak üzere büyük hesaplama yeteneklerine sahip olduğunu takdir etti, ancak başka hiçbir makinenin daha iyisini yapamayacağını takdir etmedi. 1830'lardan 1940'lara kadar, toplayıcılar ve çarpanlar gibi mekanik hesaplama makineleri yapıldı ve geliştirildi, ancak koşullu bir dal gerçekleştiremediler ve bu nedenle Turing-tam değildiler.

19. yüzyılın sonlarında, Leopold Kronecker , ilkel özyinelemeli işlevleri tanımlayan hesaplanabilirlik kavramlarını formüle etti . Bu işlevler ezber hesaplama ile hesaplanabilir, ancak evrensel bir bilgisayar yapmak için yeterli değildir, çünkü bunları hesaplayan komutlar sonsuz bir döngüye izin vermez. 20. yüzyılın başlarında, David Hilbert , bir makine tarafından gerçekleştirilebilecek kesin aksiyomlar ve kesin mantıksal tümdengelim kuralları ile tüm matematiğin aksiyomlaştırılması için bir program başlattı. Kısa bir süre sonra, herhangi bir aksiyomun sonuçlarını üretmek için küçük bir tümdengelim kuralı dizisinin yeterli olduğu anlaşıldı. Bu kuralların her teoremi üretmek için yeterli olduğu 1930 yılında Kurt Gödel tarafından kanıtlanmıştır .

Gerçek hesaplama kavramı, Gödel'in eksiklik teoremi ile başlayarak kısa bir süre sonra izole edildi . Bu teorem, aksiyom sistemlerinin, teoremlerini çıkaran hesaplama hakkında akıl yürütürken sınırlı olduğunu gösterdi. Church ve Turing bağımsız olarak Hilbert'in Entscheidungsproblem'inin (karar problemi) çözülemez olduğunu gösterdiler, böylece eksiklik teoreminin hesaplamalı çekirdeğini belirlediler. Bu çalışma, Gödel'in genel özyinelemeli fonksiyonlar üzerine çalışmasıyla birlikte, bir araya getirildiklerinde herhangi bir hesaplama üretebilen basit komut setlerinin olduğunu ortaya koydu. Gödel'in çalışması, hesaplama kavramının esasen benzersiz olduğunu gösterdi.

1941'de Konrad Zuse , Z3 bilgisayarını tamamladı . Zuse, o sırada Turing'in hesaplanabilirlik üzerine çalışmasına aşina değildi. Özellikle Z3, koşullu bir sıçrama için özel tesislere sahip değildi, bu nedenle Turing'in tamamlanmasını engelledi. Ancak 1998'de Rojas tarafından Z3'ün koşullu atlamalar yapabildiğini ve dolayısıyla Turing'in bazı özelliklerini istenmeyen bir şekilde kullanarak tamamladığını gösterdi.

hesaplanabilirlik teorisi

Hesaplanabilirlik teorisi , sorunları analiz etmek ve bunların hesaplanabilir olup olmadığını ve hangi koşullar altında olduğunu belirlemek için hesaplama modellerini kullanır . Hesaplanabilirlik teorisinin ilk sonucu, (Turing-complete) bir sistemin keyfi olarak uzun bir süre boyunca ne yapacağını tahmin etmenin imkansız olduğu problemlerin var olmasıdır.

Klasik örnek durma problemidir : Turing-complete dilindeki bir programı ve bu programa beslenecek bazı verileri girdi olarak alan ve girdi üzerinde çalışan programın sonunda duracağını veya devam edip etmeyeceğini belirleyen bir algoritma oluşturun. sonsuza kadar. Bunu bazı girdiler için yapabilen bir algoritma oluşturmak önemsizdir , ancak genel olarak bunu yapmak imkansızdır. Programın nihai çıktısının herhangi bir özelliği için, bu özelliğin tutup tutmayacağını belirlemek imkansızdır.

Bu imkansızlık, gerçek dünyadaki bilgisayar programlarını analiz ederken sorunlar yaratır. Örneğin, programcıları sonsuz döngüler yazmaktan tamamen koruyan veya kullanıcıları sonsuz döngülere neden olacak girdi sağlamaktan koruyan bir araç yazılamaz.

Bunun yerine, bir programı yalnızca sabit bir süre (zaman aşımı ) yürütmek üzere sınırlayabilir veya akış denetimi talimatlarının gücünü sınırlayabilir (örneğin, yalnızca mevcut bir dizinin öğeleri üzerinde yinelenen döngüler sağlamak). Bununla birlikte, başka bir teorem, Turing-complete dilleri tarafından çözülebilen ve yalnızca sonlu döngü yeteneklerine sahip herhangi bir dil tarafından çözülemeyen problemler olduğunu göstermektedir (yani, her programın sonunda durma noktasına geleceğini garanti eden herhangi bir dil). Yani böyle bir dil Turing-tamamlanmış değildir. Örneğin, programların tamamlanması ve durdurulması garanti edilen bir dil, Cantor'un köşegen argümanı tarafından o dildeki tüm hesaplanabilir işlevler üzerinde üretilen hesaplanabilir işlevi hesaplayamaz .

Turing kehanetleri

Ana madde: Oracle makinesi

Sonsuz bir veri bandına erişimi olan bir bilgisayar, bir Turing makinesinden daha güçlü olabilir: örneğin, bant, durma sorununun çözümünü veya Turing tarafından karar verilemeyen başka bir sorunun çözümünü içerebilir . Böyle sonsuz bir veri bandına Turing kahini denir . Rastgele verilere sahip bir Turing kahin bile hesaplanabilir değildir ( olasılık 1 ile ), çünkü yalnızca sayılabilir çok sayıda hesaplama vardır, ancak sayılamayacak kadar çok kehanet vardır. Yani rastgele bir Turing kahini olan bir bilgisayar, Turing makinesinin yapamayacağı şeyleri hesaplayabilir.

Dijital fizik

Ayrıca bakınız: Church-Turing tezi § Felsefi çıkarımlar

Bilinen tüm fizik yasalarının, dijital bir bilgisayarda bir dizi yaklaşımla hesaplanabilen sonuçları vardır. Dijital fizik adı verilen bir hipotez , bunun bir tesadüf olmadığını, çünkü evrenin kendisinin evrensel bir Turing makinesinde hesaplanabileceğini belirtir . Bu, evrensel bir Turing makinesinden daha güçlü hiçbir bilgisayarın fiziksel olarak inşa edilemeyeceği anlamına gelir.

Örnekler

Turing-tam sistemler olarak tartışılan hesaplama sistemleri (cebirler, hesaplar), teorik bilgisayar bilimlerini incelemek için tasarlanmış sistemlerdir . Hesaplamanın sınırlarını anlamak daha kolay olacak şekilde olabildiğince basit olmaları amaçlanmıştır. Burda biraz var:

Çoğu programlama dili (soyut modelleri, belki sonlu belleğin çıkarıldığını varsayan bazı özel yapılarla), geleneksel ve geleneksel olmayan, Turing-tamamlıdır. Bu içerir:

Bazı yeniden yazma sistemleri Turing-tamamlanmıştır.

Turing bütünlüğü, bu yeteneği uygulamak için kullanılan belirli dil özelliklerinin bir reçetesinden ziyade soyut bir yetenek ifadesidir. Turing tamlığını elde etmek için kullanılan özellikler oldukça farklı olabilir; Fortran sistemleri, tekrarı elde etmek için döngü yapılarını ve hatta muhtemelen goto deyimlerini kullanırdı; Neredeyse tamamen döngüden yoksun olan Haskell ve Prolog, özyinelemeyi kullanırdı . Çoğu programlama dili, belleğe (RAM ve kayıt) ve bir kontrol ünitesine sahip von Neumann mimarileri üzerindeki hesaplamaları tanımlar . Bu iki unsur, bu mimariyi Turing-tamamladı. Saf işlevsel diller bile Turing-tamamlanmıştır.

Bildirime dayalı SQL'de turing eksiksizliği, özyinelemeli ortak tablo ifadeleri aracılığıyla uygulanır . Şaşırtıcı olmayan bir şekilde, SQL'e ( PLSQL , vb.) yönelik prosedürel uzantılar da Turing-complete'dir. Bu, nispeten güçlü Turing-tamamlanmamış dillerin nadir olmasının bir nedenini göstermektedir: dil başlangıçta ne kadar güçlüyse, uygulandığı görevler o kadar karmaşıktır ve tam olmaması o kadar erken bir dezavantaj olarak algılanır ve dilin kullanımını teşvik eder. Turing-tamamlanana kadar uzatma.

Türlenmemiş lambda hesabı Turing-tamamlıdır, ancak System F dahil olmak üzere birçok yazılan lambda hesabı tam değildir. Yazılan sistemlerin değeri, daha fazla hata tespit ederken en tipik bilgisayar programlarını temsil etme yeteneklerine dayanır.

Her ikisi de hücresel otomat olan Kural 110 ve Conway'in Game of Life'ı Turing-tamamlanmıştır.

Kasıtsız Turing bütünlüğü

Bazı oyunlar ve diğer yazılımlar, tesadüfen, yani tasarım gereği değil, Turing ile tamamlanmıştır.

Yazılım:

Video oyunları:

Sosyal medya:

Kart oyunları:

Sıfır kişi oyunları (simülasyonlar):

Hesaplamalı diller:

Bilgisayar donanımı:

  • x86 MOV talimatı

Biyoloji:

Turing tamamlamayan diller

Turing-complete olmayan birçok hesaplama dili vardır. Böyle bir örnek, düzenli ifadeler tarafından oluşturulan ve sonlu otomatlar tarafından tanınan düzenli diller kümesidir . Sonlu otomatların daha güçlü ama yine de Turing-tam olmayan bir uzantısı , program derlemenin ilk aşamasında ayrıştırma ağaçları oluşturmak için yaygın olarak kullanılan aşağı itmeli otomatlar ve bağlamdan bağımsız gramerler kategorisidir . Diğer örnekler, Direct3D ve OpenGL uzantılarına gömülü piksel gölgelendirici dillerinin ilk sürümlerinden bazılarını içerir .

Gelen toplam fonksiyonel programlama gibi diller, Charity ve nükte , tüm fonksiyonlar toplam ve bitmesi gerekir. Charity , kategori teorisine dayalı bir tip sistemi ve kontrol yapıları kullanırken, Epigram bağımlı tipler kullanır . DÖNGÜ dili o sadece işlevlerini hesaplar böylece tasarlanmıştır ilkel özyinelemeli . Toplam hesaplanabilir işlevlerin tam kümesi hesaplanabilir şekilde numaralandırılamaz olduğundan, bunların tümü toplam hesaplanabilir işlevlerin uygun alt kümelerini hesaplar . Ayrıca, bu dillerdeki tüm işlevler toplam olduğundan, Turing makinelerinin aksine, yinelemeli olarak sayılabilir kümeler için algoritmalar bu dillerde yazılamaz.

(Tiplenmemiş) lambda hesabı Turing-tamamlanmış olsa da, basitçe yazılan lambda hesabı tam değildir.

Veri dilleri

Turing bütünlüğü kavramı XML , HTML , JSON ve YAML gibi diller için geçerli değildir , çünkü bunlar genellikle hesaplamayı açıklamak için değil yapılandırılmış verileri temsil etmek için kullanılır. Bunlara bazen biçimlendirme dilleri veya daha doğrusu "kapsayıcı dilleri" veya "veri açıklama dilleri" denir .

Ayrıca bakınız

Notlar

Referanslar

daha fazla okuma

Dış bağlantılar