Evrensel Turing makinesi - Universal Turing machine

İçinde bilgisayar Bilimi, bir evrensel Turing makinesi (UTM) bir Turing makinesi keyfi bir girişte keyfi bir Turing makinesini simüle eder. Evrensel makine esasen bunu hem simüle edilecek makinenin açıklamasını hem de bu makineye kendi bandından gelen girdiyi okuyarak başarır. Alan Turing 1936-1937'de böyle bir makine fikrini tanıttı. Bu ilke fikrinin kaynağı olarak kabul edilir. kayıtlı program bilgisayarı tarafından kullanılan John von Neumann 1946'da şu anda von Neumann'ın adını taşıyan "Elektronik Hesaplama Aracı" için: von Neumann mimarisi.^[1]

Açısından hesaplama karmaşıklığı, çok bantlı bir evrensel Turing makinesinin yalnızca daha yavaş ol tarafından logaritmik simüle ettiği makinelere kıyasla faktör.^[2]

Giriş

Her Turing makinesi belirli bir sabit hesaplar kısmi hesaplanabilir işlev giriş dizelerinden alfabe. Bu anlamda sabit bir programa sahip bir bilgisayar gibi davranır. Bununla birlikte, herhangi bir Turing makinesinin eylem tablosunu bir dizede kodlayabiliriz. Böylece, bandında bir eylem tablosunu açıklayan bir dizi ve ardından giriş bandını açıklayan bir dizi bekleyen ve kodlanmış Turing makinesinin hesaplayacağı bandı hesaplayan bir Turing makinesi oluşturabiliriz. Turing, 1936 tarihli makalesinde böyle bir yapıyı tüm ayrıntılarıyla anlattı:

"Herhangi bir hesaplanabilir sırayı hesaplamak için kullanılabilecek tek bir makine icat etmek mümkündür. Bu makine ise U başında bazı bilgisayar makinelerinin S.D'si [bir işlem tablosunun "standart açıklaması") yazan bir bantla birlikte verilir M, sonra U ile aynı sırayı hesaplayacak M."^[3]

Depolanan program bilgisayarı

Davis Turing'in şu anda "depolanmış program bilgisayarı" olarak bilinen, "işlem tablosu" nu - makine için talimatlar - girdi verileriyle aynı "belleğe" yerleştirme anlayışının güçlü bir şekilde etkilendiğine dair ikna edici bir argüman yapar. John von Neumann ilk Amerikan ayrık sembollü (analogun aksine) bilgisayar anlayışı — EDVAC. Davis'ten alıntılar Zaman dergisi, "bir klavyeye dokunan herkes ... bir Turing makinesinin enkarnasyonu üzerinde çalışıyor" ve "John von Neumann [Alan Turing'in çalışmaları üzerine inşa edilmiştir]" (Davis 2000: 193 alıntı Zaman 29 Mart 1999 tarihli dergi).

Davis, Turing'in Otomatik Hesaplama Motoru (ACE) bilgisayarı mikroprogramlama kavramlarını "öngördü" (mikro kod ) ve RISC işlemciler (Davis 2000: 188). Knuth Turing'in ACE bilgisayar üzerindeki çalışmasının "alt rutin bağlantısını kolaylaştırmak için donanım" tasarladığını aktarır (Knuth 1973: 225); Davis ayrıca bu çalışmaya Turing'in bir donanım "yığını" kullanması olarak atıfta bulunur (Davis 2000: 237 dipnot 18).

Turing Makinesi inşaatı teşvik ederken bilgisayarlar UTM, yeni doğanların gelişimini teşvik ediyordu bilgisayar Bilimleri. İlk olmasa da erken bir assembler, EDVAC için "genç bir ateşli programcı" tarafından önerildi (Davis 2000: 192). Von Neumann'ın "ilk ciddi programı ... basitçe verileri verimli bir şekilde sıralamaktı" (Davis 2000: 184). Knuth, özel kayıtlardan ziyade programın içine gömülü alt rutin dönüşünün von Neumann ve Goldstine'a atfedilebileceğini gözlemliyor.^[4] Knuth ayrıca şunu belirtir:

"İlk yorumlama rutininin" Evrensel Turing Makinesi "olduğu söylenebilir ... Geleneksel anlamda yorumlama rutinlerinden John Mauchly, 1946'da Moore Okulu'ndaki derslerinde bahsetmişti ... Turing de bu gelişmede yer aldı; Pilot ACE bilgisayarı için yorumlama sistemleri, onun yönetimi altında yazılmıştır "(Knuth 1973: 226).

Davis, veri olarak program kavramının sonuçları olarak işletim sistemlerinden ve derleyicilerden kısaca bahsetmektedir (Davis 2000: 185).

Ancak bazıları bu değerlendirmeyle ilgili sorunlar ortaya çıkarabilir. O zamanlar (1940'ların ortalarından 1950'lerin ortalarına) görece küçük bir araştırmacı kadrosu, yeni "dijital bilgisayarların" mimarisiyle yakından ilgileniyordu. Hao Wang O dönemde genç bir araştırmacı olan (1954) şu gözlemi yaptı:

Turing'in hesaplanabilir işlevler teorisi, geçmişte kaldı, ancak dijital bilgisayarların kapsamlı gerçek yapısını pek etkilemedi. Teori ve pratiğin bu iki yönü neredeyse tamamen birbirinden bağımsız olarak geliştirilmiştir. Ana neden şüphesiz mantıkçıların, uygulamalı matematikçilerin ve elektrik mühendislerinin öncelikli olarak ilgilendikleri sorulardan kökten farklı sorularla ilgilenmeleridir. Bununla birlikte, iki gelişmede çoğu kez aynı kavramların çok farklı terimlerle ifade edilmesi oldukça garip bir şekilde ortaya çıkamaz. "(Wang 1954, 1957: 63)

Wang, makalesinin "iki yaklaşımı birleştireceğini" umuyordu. Gerçekte, Minsky bunu doğrulamaktadır: "Bilgisayar benzeri modellerde Turing-makinesi teorisinin ilk formülasyonu Wang (1957) 'de ortaya çıkmaktadır" (Minsky 1967: 200). Minsky göstermeye devam ediyor Turing denkliği bir sayaç makinesi.

Bilgisayarların basit Turing eşdeğer modellerine indirgenmesi (ve tersi) ile ilgili olarak, Minsky'nin Wang'ın "ilk formülasyonu" yapmış olarak tanımlaması tartışmaya açıktır. Hem Minsky'nin 1961 tarihli makalesi hem de Wang'ın 1957 tarihli makalesi Shepherdson ve Sturgis (1963) tarafından alıntılanırken, Avrupalı ​​matematikçiler Kaphenst (1959), Ershov (1959) ve Péter'in (1958) çalışmalarına da atıfta bulunmakta ve bazı ayrıntıları özetlemektedir. Matematikçiler Hermes (1954, 1955, 1961) ve Kaphenst'in (1959) isimleri hem Sheperdson-Sturgis (1963) hem de Elgot-Robinson'un (1961) bibliyografyalarında yer almaktadır. Kanadalı araştırmacılar Melzak (1961) ve Lambek (1961) diğer iki önemli isimdir. Daha fazlası için bkz. Turing makinesi eşdeğerleri; referanslar bulunabilir kayıt makinesi.

Matematiksel teori

Eylem tablolarının dizge olarak kodlanmasıyla, prensip olarak Turing makinelerinin diğer Turing makinelerinin davranışları hakkındaki soruları yanıtlaması mümkün hale gelir. Ancak bu soruların çoğu karar verilemez yani söz konusu fonksiyon mekanik olarak hesaplanamaz. Örneğin, keyfi bir Turing makinesinin belirli bir girişte mi yoksa tüm girdilerde mi duracağını belirleme sorunu Durma sorunu Turing'in orijinal makalesinde genel olarak kararsız olduğu gösterildi. Rice teoremi bir Turing makinesinin çıktısıyla ilgili önemsiz olmayan herhangi bir sorunun karar verilemez olduğunu gösterir.

Evrensel bir Turing makinesi herhangi bir özyinelemeli işlev, herhangi birine karar ver yinelemeli dil ve herhangi birini kabul et yinelemeli olarak numaralandırılabilir dil. Göre Kilise-Turing tezi, evrensel bir Turing makinesi tarafından çözülebilen sorunlar, tam olarak bir algoritma veya bir etkili hesaplama yöntemi, bu şartların herhangi bir makul tanımı için. Bu nedenlerden dolayı, evrensel bir Turing makinesi, hesaplama sistemlerini karşılaştırmak için bir standart olarak hizmet eder ve evrensel bir Turing makinesini simüle edebilen bir sistem olarak adlandırılır. Turing tamamlandı.

Evrensel Turing makinesinin soyut bir versiyonu, evrensel işlev herhangi bir başka hesaplanabilir işlevi hesaplamak için kullanılabilen hesaplanabilir bir işlev. UTM teoremi böyle bir işlevin varlığını kanıtlıyor.

Verimlilik

Genelliği kaybetmeden, Turing makinesinin girdisinin {0, 1} alfabesinde olduğu varsayılabilir; diğer sonlu alfabe {0, 1} üzerinde kodlanabilir. Turing makinesinin davranışı M geçiş işlevi tarafından belirlenir. Bu işlev, {0, 1} alfabesi üzerinde de kolayca bir dize olarak kodlanabilir. Alfabesinin boyutu M, sahip olduğu bant sayısı ve durum uzayının boyutu geçiş fonksiyonunun tablosundan çıkarılabilir. Ayırt edici durumlar ve semboller, konumlarına göre tanımlanabilir, ör. ilk iki durum geleneksel olarak başlangıç ​​ve bitiş durumları olabilir. Sonuç olarak, her Turing makinesi {0, 1} alfabesi üzerinde bir dizge olarak kodlanabilir. Ek olarak, her geçersiz kodlamanın önemsiz bir Turing makinesine eşlendiğini ve anında durduğunu ve her Turing makinesinin, tıpkı yorumlar gibi, sonunda (diyelim ki) keyfi sayıda 1 ile kodlamayı doldurarak sonsuz sayıda kodlamaya sahip olabileceğini topladık. bir programlama dilinde çalışın. Bir kodlamanın varlığı göz önüne alındığında bu kodlamayı başarabilmemiz şaşırtıcı olmamalıdır. Gödel numarası ve Turing makineleri arasındaki hesaplamalı eşdeğerlik ve μ-özyinelemeli fonksiyonlar. Benzer şekilde, bizim inşaat ilişkimiz her ikili dizeyle ilişkilendirilir. αTuring makinesi M_α.

Yukarıdaki kodlamadan başlayarak, 1966 F.C. Hennie ve R. E. Stearns bir Turing makinesi verildiğini gösterdi M_α girişte durur x içinde N adımlar, sonra girişlerde duran çok bantlı evrensel bir Turing makinesi var α, x (farklı bantlarda verilmiştir) CN günlük N, nerede C girdinin uzunluğuna bağlı olmayan makineye özgü bir sabittir xama bağlıdır M 's alfabe boyutu, bant sayısı ve durum sayısı. Etkili olarak bu bir ${ displaystyle { mathcal {O}} sol (N log {N} sağ)}$ simülasyon, kullanma Donald Knuth 's Büyük O gösterimi.^[5] Zaman karmaşıklığından ziyade uzay karmaşıklığına karşılık gelen sonuç, en çok kullanılan bir şekilde simüle edebilmemizdir. CN hesaplamanın herhangi bir aşamasında hücreler, bir ${ displaystyle { mathcal {O}} (N)}$ simülasyon.^[6]

En küçük makineler

Alan Turing evrensel bir makine fikrini ortaya attığında, hesaplanabilen tüm olası fonksiyonları hesaplayacak kadar güçlü en basit hesaplama modelini aklında bulunduruyordu. Claude Shannon ilk olarak 1956'da mümkün olan en küçük evrensel Turing makinesini bulma sorusunu açıkça ortaya attı. Yeterli durum kullanıldığı sürece (veya tam tersi) iki sembolün yeterli olduğunu ve semboller için durumları değiş tokuş etmenin her zaman mümkün olduğunu gösterdi. Ayrıca tek bir devletin evrensel Turing makinesinin var olamayacağını da gösterdi.

Marvin Minsky 1962'de 7 durumlu 4 sembollü evrensel bir Turing makinesi keşfetti 2 etiketli sistemler. Diğer küçük evrensel Turing makineleri o zamandan beri Yurii Rogozhin ve diğerleri, etiket sistemi simülasyonunun bu yaklaşımını genişleterek. Eğer (m, n) ile UTM sınıfı m devletler ve n semboller aşağıdaki tuplelar bulundu: (15, 2), (9, 3), (6, 4), (5, 5), (4, 6), (3, 9) ve (2, 18) .^[7][8][9] Rogozhin'in (4, 6) makinesi yalnızca 22 talimat kullanır ve daha az açıklama karmaşıklığına sahip hiçbir standart UTM bilinmemektedir.

Bununla birlikte, standart Turing makine modelini genelleştirmek, daha küçük UTM'leri kabul eder. Böyle bir genelleme, Turing makinesi girdisinin bir veya her iki tarafında sonsuz tekrarlanan bir kelimeye izin vermek, böylece evrensellik tanımını genişletmek ve sırasıyla "yarı-zayıf" veya "zayıf" evrensellik olarak bilinir. Küçük, zayıf evrensel Turing makineleri Kural 110 (6, 2), (3, 3) ve (2, 4) durum-sembol çiftleri için hücresel otomat verilmiştir.^[10] Evrenselliğin kanıtı Wolfram'ın 2 durumlu 3 sembollü Turing makinesi belirli periyodik olmayan başlangıç ​​konfigürasyonlarına izin vererek zayıf evrensellik kavramını daha da genişletir. Standart Turing makine modelindeki küçük UTM'ler veren diğer varyantlar, çok sayıda bant veya çok boyutlu bantlara sahip makineleri ve bir sonlu otomat.

İç durumu olmayan makineler

Turing makinesinde birden fazla kafaya izin verirseniz, o zaman hiçbir dahili durumu olmayan bir Turing makineniz olabilir. "Durumlar", bandın bir parçası olarak kodlanır. Örneğin, 6 renkli bir bant düşünün: 0, 1, 2, 0A, 1A, 2A. 0,0,1,2,2A, 0,2,1 gibi 3 başlı bir Turing makinesinin üçlü (2,2A, 0) üzerine yerleştirildiği bir bant düşünün. Kurallar daha sonra herhangi bir üçlüyü başka bir üçe dönüştürür ve 3 kafayı sola veya sağa hareket ettirir. Örneğin, kurallar (2,2A, 0) 'ı (2,1,0)' a dönüştürebilir ve kafayı sola hareket ettirebilir. Bu nedenle, bu örnekte makine, A ve B dahili durumlarına sahip (harf olmadan temsil edilen) 3 renkli bir Turing makinesi gibi davranır. 2 başlı bir Turing makinesinin durumu çok benzer. Böylece 2 başlı bir Turing makinesi 6 renk ile Universal olabilir. Çok başlı bir Turing makinesi için gereken en az sayıda rengin ne olduğu veya birden fazla kafalı 2 renkli bir Universal Turing makinesinin mümkün olup olmadığı bilinmemektedir. Aynı zamanda şu anlama gelir kuralları yeniden yaz Üçlü kurallar yeniden yazma kurallarına eşdeğer olduğundan Turing tamamlandı. Bir harfi ve 8 komşusunu örnekleyen bir kafa ile bandı iki boyuta genişletmek için yalnızca 2 renge ihtiyaç vardır, örneğin 110 gibi dikey üçlü modelde bir renk kodlanabilir.

Evrensel makine kodlama örneği

Tam olarak Turing'in belirttiği gibi bir UTM tasarlama zorluğunu üstlenmek isteyenler için, Davies in Copeland (2004: 103ff) makalesine bakın. Davies, orijinaldeki hataları düzeltir ve örnek bir çalışmanın nasıl görüneceğini gösterir. Başarılı bir şekilde (biraz basitleştirilmiş) bir simülasyon çalıştırdığını iddia ediyor.

Aşağıdaki örnek Turing'den (1936) alınmıştır. Bu örnek hakkında daha fazla bilgi için sayfaya bakın Turing makinesi örnekleri.

Turing yedi sembol kullandı {A, C, D, R, L, N,; } her 5 grubu kodlamak için; makalede anlatıldığı gibi Turing makinesi onun 5 tupleları sadece N1, N2 ve N3 türlerindendir. Her "m-konfigürasyonunun" (talimat, durum) sayısı, "D" ve ardından tekli bir A dizisi ile temsil edilir, ör. "q3" = DAAA. Benzer bir şekilde boş sembolleri "D", "0" sembolünü "DC", "1" sembolünü DCC olarak kodlar, vb. "R", "L" ve "N" sembolleri olarak kalır. dır-dir.

Her 5 tuple kodlandıktan sonra, aşağıdaki tabloda gösterildiği gibi bir diziye "birleştirilir":

Son olarak, dört 5-demetinin hepsinin kodları, ";" ile başlayan bir koda dizilir. ve ";" ile ayrılır yani:

;DADDCRDAA;DAADDRDAAA;DAAADDCCRDAAAA;DAAAADDRDA

Bu kodu, "E-kareleri" (silinmesi muhtemel olanlar) boş bırakarak alternatif karelere - "F karelerine" yerleştirdi. U makinesi için bant üzerindeki kodun son montajı, iki özel sembolün ("e") birbiri ardına yerleştirilmesinden oluşur, ardından alternatif karelere ayrılan kod ve son olarak çift iki nokta simgesi "::"(burada açıklık için". "ile gösterilen boşluklar):

ee.;.D.A.D.D.C.R.D.A.A.;.D.A.A.D.D.R.D.A.A.A.;.D.A.A.A.D.D.C.C.R.D.A.A.A.A.;.D.A.A.A.A.D.D.R.D.A.::......

U makinesinin işlem tablosu (durum geçiş tablosu), sembollerin kodunu çözmekten sorumludur. Turing'in eylem tablosu, "u", "v", "x", "y", "z" işaretçileri ile "işaretli sembol" ün sağındaki "E-kareler" e yerleştirerek yerini takip eder - örneğin , mevcut talimatı işaretlemek için z ";" nin sağına yerleştirilir x yeri mevcut "m-konfigürasyonu" DAA'ya göre tutuyor. U-makinesinin işlem masası, hesaplama ilerledikçe bu sembolleri dolaştıracaktır (onları silip farklı konumlara yerleştirecektir):

ee.; .D.A.D.D.C.R.D.A.A. ; zD.A.AxD.D.R.D.A.A.A.;.D.A.A.A.D.D.C.C.R.D.A.A.A.A.;.D.A.A.A.A.D.D.R.D.A.::......

Turing'in U-makinesi için hareket tablosu çok karmaşık.

Diğer bazı yorumcular (özellikle Penrose 1989 ) Universal makine için talimatları kodlamanın yollarına örnekler verin. Penrose gibi, çoğu yorumcu yalnızca ikili semboller kullanır, yani yalnızca semboller {0, 1} veya {blank, mark | }. Penrose daha da ileri giderek U-makine kodunun tamamını yazar (Penrose 1989: 71-73). Bunun gerçekten bir U-makine kodu olduğunu iddia ediyor, 1'ler ve 0'ların neredeyse 2 tam sayfasını kapsayan muazzam bir sayı. Daha basit kodlamalarla ilgilenen okuyucular için Post – Turing makinesi Davis'in Steen'deki tartışması (Steen 1980: 251ff) faydalı olabilir.

Asperti ve Ricciotti, tüm eylem tablosunu açıkça vermek yerine, temel makineleri çok basit anlambilimle oluşturarak tanımlanan çok bantlı bir UTM tanımladı. Bu yaklaşım, makinedeki makinenin doğruluğunu resmi olarak kanıtlamalarına izin verecek kadar modülerdi. Matita kanıt asistanı.

Turing makinelerinin programlanması

Bir Turing makinesinde derlenmek üzere çeşitli yüksek seviyeli diller tasarlanmıştır. Örnekler şunları içerir: Laconic ve Turing Machine Descriptor.^[11][12]

Ayrıca bakınız

• Alternatif Turing makinesi
• Von Neumann evrensel yapıcı - kendini kopyalayan bir Turing makinesi inşa etme girişimi
• Kleene'nin T yüklemi - µ-özyinelemeli fonksiyonlar için benzer bir kavram
• Turing bütünlüğü

Referanslar

Genel referanslar

• Arora, Sanjeev; Barak, Boaz (2009). Karmaşıklık Teorisi: Modern Bir Yaklaşım. Cambridge University Press. ISBN  978-0-521-42426-4. Bölüm 1.4, "Dizeler olarak makineler ve evrensel Turing makinesi" ve 1.7, "Teorem 1.9'un Kanıtı"

Orjinal kağıt

• Turing, A.M. (1936). "Hesaplanabilir Sayılar Üzerine, Entscheidungsproblem Uygulaması ile" (PDF).

Seminal makaleler

• Hennie, F. C .; Stearns, R. E. (1966). "Çok Bantlı Turing Makinelerinin İki Bantlı Simülasyonu". ACM Dergisi. 13 (4): 533. doi:10.1145/321356.321362. S2CID  2347143.

Uygulama

• Kamvysselis (Kellis), Manolis (1999). "Universal Turing Machine Şema Uygulaması". Kendinden yayınlanan.

Resmi doğrulama

• Asperti, Andrea; Ricciotti, Wilmer (2015). "Çok bantlı Turing makinelerinin resmileştirilmesi" (PDF). Teorik Bilgisayar Bilimleri. Elsevier. 603: 23–42. doi:10.1016 / j.tcs.2015.07.013. ISSN  0304-3975.

diğer referanslar

• Copeland, Jack, ed. (2004), Temel Turing: Bilgisayar, Mantık, Felsefe, Yapay Zeka ve Yapay Yaşamda Yeni Yazılar ve Enigmanın Sırları, Oxford UK: Oxford University Press, ISBN  0-19-825079-7
• Davis, Martin (1980), "Hesaplama Nedir?" Steen, Lynn Arthur (ed.), Bugün Matematik: On İki Gayri Resmi Deneme, New York: Vintage Books (Random House), ISBN  978-0-394-74503-9.
• Davis, Martin (2000), Mantık Motorları: Matematikçiler ve Bilgisayarın Kökeni (1. baskı), New York NY: W. W. Norton & Company, ISBN  0-393-32229-7, (pb.)
• Goldstine, Herman H .; von Neumann, John. Bir Elektronik Hesaplama Aracı için Problemlerin Planlanması ve Kodlanması. İleri Araştırmalar Enstitüsü (Rep. 1947 baskısı). Princeton.
  Bell, C. Gordon; Newell, Allen (1971). Bilgisayar Yapıları: Okumalar ve Örnekler (Yeniden basıldı.). New York: McGraw-Hill Kitap Şirketi. pp.92–119. ISBN  0-07-004357-4.
• Herken, Rolf (1995), Evrensel Turing Makinesi - Yarım Asırlık Bir Araştırma, Springer Verlag, ISBN  3-211-82637-8
• Knuth, Donald E. (1968), Bilgisayar Programlama Sanatı İkinci Baskı, Cilt 1 / Temel Algoritmalar (2, 1973) | format = gerektirir | url = (Yardım) (İlk baskı), Addison-Wesley Publishing Company Knuth'un üç metinlik serisinin ilki.
• Kudlek, Manfred; Rogozhin, Yurii (2002), "3 durumlu ve 9 sembollü evrensel bir Turing makinesi", Werner Kuich; Grzegorz Rozenberg; Arto Salomaa (editörler), Dil Teorisindeki Gelişmeler: 5. Uluslararası Konferans, DLT 2001 Wien, Avusturya, 16–21 Temmuz 2001, Gözden Geçirilmiş Makaleler, Bilgisayar Bilimleri Ders Notları, 2295, Springer, s. 311–318, doi:10.1007 / 3-540-46011-x_27, ISBN  978-3-540-43453-5
• Minsky, Marvin (1962), "Etiket Sistemleri Kullanılarak Evrensel Turing Makinelerinin Boyutu ve Yapısı, Özyinelemeli Fonksiyon Teorisi", Proc. Symp. Saf MatematikProvidence RI: American Mathematical Society, 5: 229–238, doi:10.1090 / pspum / 005/0142452
• Neary, Turlough; Woods, Damien (2009), "Dört Küçük Evrensel Turing Makinesi" (PDF), Fundamenta Informaticae, 91 (1): 123–144, doi:10.3233 / FI-2009-0036
• Neary, Turlough; Woods, Damien (2009b), "Küçük Zayıf Evrensel Turing Makineleri", 17. Uluslararası Hesaplama Teorisinin Temelleri Sempozyumu, Bilgisayar Bilimleri Ders Notları, 5699, Springer, s. 262–273
• Penrose, Roger (1989), İmparatorun Yeni Aklı, Oxford UK: Oxford University Press, ISBN  0-19-851973-7, (hc.), (pb.)
• Rogozhin, Yurii (1996), "Küçük Evrensel Turing Makineleri", Teorik Bilgisayar Bilimleri, 168 (2): 215–240, doi:10.1016 / S0304-3975 (96) 00077-1
• Shannon, Claude (1956), "İki İç Durumu Olan Evrensel Turing Makinesi", Otomata Çalışmaları, Princeton, NJ: Princeton University Press, s. 157–165
• Turing, A.M. (1936), "Hesaplanabilir Sayılar Üzerine, Entscheidungsproblem Uygulaması ile", Londra Matematik Derneği Bildirileri, 2, 42, s. 230–65, doi:10.1112 / plms / s2-42.1.230
• Turing, A.M. (1938), "Hesaplanabilir Sayılar Üzerine, Entscheidungsproblem Uygulaması ile: Bir düzeltme", Londra Matematik Derneği Bildirileri, 2 (1937'de yayınlandı), 43 (6), s. 544–6, doi:10.1112 / plms / s2-43.6.544)
  Davis ed, Martin (1965). Kararsız (Baskı ed.). Hewlett, NY: Raven Press. s. 115–154. Turing'in UTM'sinde yapılan düzeltmeler ile Emil Post cf dipnot 11 syf: 299CS1 bakimi: ek metin: yazarlar listesi (bağlantı)

Dış bağlantılar

Smith, Alvy Ray. "Bir Kartvizit Evrensel Turing Makinesi" (PDF). Alındı 2 Ocak 2020.