Kayıt makinesi - Register machine

Gelen matematiksel mantık ve teorik bilgisayar bilimleri bir kayıt makinesi genel bir sınıftır soyut makinelerin bir benzer bir şekilde kullanılan Turing makinası . Tüm modeller Turing eşdeğeridir .

genel bakış

Kayıt makinesi, adını bir veya daha fazla " kayıt " kullanımından alır. Bir Turing makinesi tarafından kullanılan teyp ve kafanın aksine , model , her biri tek bir pozitif tamsayı tutan birden çok, benzersiz adresli yazmaç kullanır .

Literatürde bulunan en az dört alt sınıf vardır, burada en ilkelden bir bilgisayara en çok benzeyene kadar listelenmiştir :

• Sayaç makinesi - bir bilgisayar donanımının en ilkel ve azaltılmış teorik modeli. Dolaylı adreslemeden yoksundur. Talimatlar, Harvard mimarisi tarzında sonlu durum makinesindedir .
• İşaretçi makinesi – sayaç makinesi ve RAM modellerinin bir karışımı. Her iki modelden daha az yaygın ve daha soyut. Talimatlar, Harvard mimarisi tarzında sonlu durum makinesindedir.
• Rastgele erişimli makine (RAM) – dolaylı adreslemeli ve genellikle artırılmış komut setli bir sayaç makinesi. Talimatlar, Harvard mimarisi tarzında sonlu durum makinesindedir.
• Rastgele erişimli depolanmış program makine modeli (RASP) – Universal Turing makinesine benzer şekilde kayıtlarında talimatlar içeren bir RAM ; dolayısıyla von Neumann mimarisinin bir örneğidir . Ancak bir bilgisayardan farklı olarak, model etkili bir şekilde sonsuz kayıtlarla (ve eğer kullanılıyorsa, akümülatör gibi etkili bir şekilde sonsuz özel kayıtlarla) idealleştirilir . Bir bilgisayardan ve hatta RISC'den farklı olarak , komut seti sayı olarak çok daha azdır.

Düzgün tanımlanmış herhangi bir kayıt makinesi modeli Turing eşdeğeridir . Hesaplama hızı, model özelliklerine çok bağlıdır.

Pratik bilgisayar biliminde, sanal makine olarak bilinen benzer bir kavram , bazen temeldeki makine mimarilerine olan bağımlılıkları en aza indirmek için kullanılır. Bu tür makineler aynı zamanda öğretim için de kullanılmaktadır. "Makineyi kaydet" terimi bazen ders kitaplarında sanal bir makineye atıfta bulunmak için kullanılır.

Resmi tanımlama

Bir kayıt makinesi şunlardan oluşur:

1. Sınırsız sayıda etiketlenmiş, ayrık, sınırlandırılmamış kayıtlar, kapsamı (kapasitesi) sınırsızdır : her biri sonsuz ölçüde olduğu düşünülen ve her biri negatif olmayan tek bir tamsayı (0, 1, 2, ...). Kayıtlar kendi aritmetiğini yapabilir veya aritmetiği yapan bir veya daha fazla özel kayıt olabilir, örneğin bir "akümülatör" ve/veya "adres kaydı". Ayrıca bkz. Rastgele erişimli makine .${\displaystyle r_{0}\ldots r_{n}}$
2. Tally sayaçları veya işaretleri : ayrık, ayırt edilemez nesneler veya modele uygun yalnızca tek türden işaretler. En azaltılmış sayaç makinesi modelinde, her aritmetik işlem başına, konumuna/bantına yalnızca bir nesne/işaret eklenir veya çıkarılır. Bazı karşı makine modellerinde (örn. Melzak (1961), Minsky (1961)) ve çoğu RAM ve RASP modellerinde, "toplama" ve genellikle "çıkarma" ile tek bir işlemde birden fazla nesne/işaret eklenebilir veya çıkarılabilir; bazen "çarpma" ve/veya "bölme" ile. Bazı modellerde nesnelerin/işaretlerin "kümelerini" tek bir eylemde kayıttan kayda taşıyan "kopyala" (çeşitli olarak: "taşı", "yükle", "sakla") gibi kontrol işlemleri vardır.
3. (Çok) sınırlı bir talimat seti : talimatlar iki sınıfa ayrılma eğilimindedir: aritmetik ve kontrol. Talimatlar, "talimat kümeleri" oluşturmak için iki sınıftan çekilir, öyle ki bir talimat kümesi, modelin Turing eşdeğeri olmasına izin vermelidir (herhangi bir kısmi özyinelemeli işlevi hesaplayabilmelidir ).
   1. Aritmetik : aritmetik komutlar tüm kayıtlarda veya sadece özel bir kayıtta (örneğin akümülatör) çalışabilir. Bunlar edilir genellikle şu setleri seçilen (ama istisnalar bol):
      • Sayaç makinesi: { Arttırma (r), Azaltma (r), Sıfıra Doğru (r) }
      • Azaltılmış RAM, RASP: { Artış (r), Azaltma (r), Sıfıra Sıfır (r), Yük anında sabit k, Ekle (r ₁ ,r ₂ ), uygun-Çıkar (r ₁ ,r ₂ ), Artış akümülatörü, Azaltma akümülatörü, Akümülatörü temizle, r kaydının akümülatör içeriğini ekle, uygun- r kaydının akümülatör içeriğinden çıkar, }
      • Artırılmış RAM, RASP: Tüm azaltılmış komutlar artı: { Çarpma, Bölme, çeşitli Boolean bit-wise (sola kaydırma, bit testi, vb.)}
   2. Kontrol :
      • Sayaç makine modelleri: isteğe bağlı { Copy (r ₁ ,r ₂ ) }
      • RAM ve RASP modelleri: çoğunda { Copy (r ₁ ,r ₂ ) } veya { Load Akümülatörü r'den Yükle, Akümülatörü r'ye depola, Akümülatörü anında sabitle Yükle}
      • Tüm modeller: bir kayıt testinin ardından en az bir koşullu "atlama" (dal, git) örneğin { Sıfır ise Atla, Sıfır değilse Atla (yani Pozitif ise Atla), Eşitse Atla, Eşit değilse atlama }
      • Tüm modeller isteğe bağlı: { koşulsuz program atlama (goto) }
   3. Kayıt-adresleme yöntemi :
      • Sayaç makinesi: dolaylı adresleme yok, yüksek oranda atomize modellerde anında işlenenler mümkün
      • RAM ve RASP: dolaylı adresleme mevcut, tipik anlık işlenenler
   4. Giriş-Çıkış : tüm modellerde opsiyonel
4. Durum kaydı : Özel bir Komut Kaydı "IR", sonlu ve yukarıdaki kayıtlardan ayrı, yürütülecek mevcut komutu ve adresini talimat TABLOSU'nda saklar; bu kayıt ve onun TABLOSU sonlu durum makinesinde bulunur.
   • IR tüm modellerde yasaklanmıştır. RAM ve RASP durumunda, bir kaydın "adresini" belirlemek amacıyla model, (i) doğrudan adresleme durumunda - TABLO tarafından belirtilen ve geçici olarak IR'de bulunan adres veya ( ii) dolaylı adresleme durumunda—IR'nin talimatıyla belirtilen kayıt içeriği.
   • İR olduğu değil RASP (ya da geleneksel bilgisayar) "programı sayacı" (PC) oluşmasıdır. PC, akümülatöre benzer başka bir kayıttır, ancak RASP'nin mevcut kayıt tabanlı talimatının numarasını tutmaya adanmıştır. Dolayısıyla bir RASP'nin iki "komut/program" kaydı vardır - (i) IR (sonlu durum makinesinin Komut Kaydı) ve (ii) kayıtlarda bulunan program için bir PC (Program Sayacı). ("PC"ye tahsis edilmiş bir kayıtın yanı sıra, bir RASP "Program-Talimat Kaydı"na başka bir kayıt atayabilir ("PIR, "IR", "PR", vb. gibi herhangi bir sayıda isimle gidiyor)
5. Genellikle sıralı olarak etiketlenmiş talimatların listesi: Sonlu bir talimat listesi . Sayaç makinesi, rastgele erişimli makine (RAM) ve işaretçi makinesi söz konusu olduğunda, talimat deposu sonlu durum makinesinin "TABLOSU"ndadır; dolayısıyla bu modeller Harvard mimarisinin örnekleridir. RASP durumunda program deposu kayıtlardadır; dolayısıyla bu, von Neumann mimarisinin bir örneğidir. Ayrıca bkz. Rastgele erişimli makine ve Rastgele erişimli depolanmış program makinesi. Genellikle, bilgisayar programları gibi, talimatlar sırayla listelenir; bir atlama başarılı olmadıkça, varsayılan sıralama sayısal sırayla devam eder. Bunun bir istisnası, abaküs (Lambek (1961), Minsky (1961)) karşı makine modelleridir; her talimatın en az bir "sonraki" talimat tanımlayıcısı "z" vardır ve koşullu dalda iki tane bulunur. ${\displaystyle I_{1}\ldots I_{m}}$
   
   • Abaküs modelinin JZ ve ardından DEC olmak üzere iki komutu birleştirdiğini de gözlemleyin: örneğin { INC ( r, z ), JZDEC ( r, z _true , z _false ) }. "IF r=0 THEN z
   _true ELSE z _false " koşullu ifadesi hakkında daha fazla bilgi için McCarthy Formalism'e
   bakın (cf McCarthy (1960)).

Kayıt makinesi modelinin tarihsel gelişimi

1950'lerin başında iki eğilim ortaya çıktı: birincisi bilgisayarı bir Turing makinesi olarak nitelendiren, ikincisi bilgisayar benzeri modelleri tanımlayan - sıralı talimat dizileri ve koşullu sıçramalara sahip modeller - bir Turing makinesinin gücüyle, yani sözde Turing denkliği. Bu çalışmaya duyulan ihtiyaç, iki "zor" problem bağlamında gerçekleştirildi: Emil Post'un ortaya koyduğu çözülemeyen kelime problemi - onun "etiket" problemi - ve Hilbert'in problemlerinin çok "zor" problemi - Diophantine denklemleri etrafındaki 10. soru . Araştırmacılar, doğası gereği daha az "mantıksal" ve daha "aritmetik" olan Turing eşdeğeri modelleri araştırıyorlardı (karş. Melzak (1961) s. 281, Shepherdson–Sturgis (1963) s. 218).

Bilgisayarları karakterize etmeye yönelik ilk eğilim, Hans Hermes (1954), Rózsa Péter (1958) ve Heinz Kaphengst (1959), ikinci eğilim Hao Wang (1954, 1957) ile ortaya çıkmış gibi görünüyor ve yukarıda belirtildiği gibi, daha da ileri gitti. birlikte Zdzislaw Alexander Melzak (1961), Joachim Lambek (1961) ve Marvin Minsky (1961, 1967).

Son beş isim, Yuri Matiyasevich tarafından bu sırayla açıkça listelenmiştir . Şunları takip ediyor:

"Kayıt makineleri [bazı yazarlar "karşı makine" ile eşanlamlı "kayıt makinesi" kullanır] özellikle Diophantine denklemleri oluşturmak için uygundur. Turing makineleri gibi çok ilkel komutlara sahiptirler ve ayrıca sayılarla ilgilenirler" (Yuri Matiyasevich ( 1993), Hilbert'in Onuncu Problemi , kitabın 5. Bölümünün yorumu, http://logic.pdmi.ras.ru/yumat/H10Pbook/commch_5htm .)

Görünüşe göre Lambek, Melzak, Minsky ve Shepherdson ve Sturgis aynı fikri bağımsız olarak aynı anda öngördüler. Aşağıdaki Öncelik Üzerine Nota bakın.

Tarih, Wang'ın modeliyle başlar.

Wang'ın (1954, 1957) modeli: Post-Turing makinesi

Wang'ın çalışması Emil Post'un (1936) makalesinden takip edildi ve Wang'ı kendi Wang B-makinesinin tanımına götürdü - sadece dört atomik talimat içeren iki sembollü Post-Turing makine hesaplama modeli:

{ SOL, SAĞ, YAZDIR, JUMP_if_marked_to_instruction_z }

Bu dördüne hem Wang (1954, 1957) hem de CY Lee (1961) Posta kümesinden { ERASE } başka bir talimat ekledi ve ardından bir Gönderinin koşulsuz atlamasını { JUMP_to_ talimat_z } (veya işleri kolaylaştırmak için JUMP_IF_blank_to_instruction_z koşullu atlamasını, veya her ikisi. Lee buna "W-makine" modeli adını verdi:

{ SOL, SAĞ, YAZDIR, SİL, JUMP_işaretliyse, [belki JUMP veya JUMP_IF_blank] }

Wang, modelinin Turing makineleri teorisi ile bilgisayarın pratik dünyası arasında "bir yakınlaşma" (s. 63) olacağını umduğunu ifade etti.

Wang'ın çalışması son derece etkili oldu. Ona Minsky (1961) ve (1967), Melzak (1961), Shepherdson ve Sturgis (1963) tarafından atıfta bulunulduğunu görüyoruz. Gerçekten de Shepherdson ve Sturgis (1963) şunları belirtir:

"...Wang tarafından önerilen hesaplamanın pratik ve teorik yönleri arasındaki 'uzlaşmayı' bir adım daha ileriye taşımaya çalıştık" (s. 218)

Martin Davis sonunda bu modeli (2 sembollü) Post-Turing makinesine dönüştürdü.

Wang/Post-Turing modeliyle ilgili zorluklar :

Bir sorun dışında: Wang modeli (7 komutlu Turing Sonrası makinesinin altı talimatı) hala tek bantlı Turing benzeri bir cihazdı, ancak sıralı program talimat akışı ne kadar güzel olursa olsun . Hem Melzak (1961) hem de Shepherdson ve Sturgis (1963) bunu gözlemlediler (belirli deliller ve araştırmalar bağlamında):

"...bir Turing makinesinin belirli bir opaklığı vardır... bir Turing makinesi (varsayımsal) işlemde yavaştır ve genellikle karmaşıktır. Bu, onu tasarlamayı oldukça zorlaştırır ve zaman veya depolama gibi konuları araştırmayı daha da zorlaştırır. optimizasyon veya iki algoritmanın verimliliği arasında bir karşılaştırma (Melzak (1961) s. 281)

"... zor olmasa da ... kanıtları takip etmek iki nedenden dolayı karmaşık ve sıkıcıdır: (1) Bir Turing makinesinin yalnızca kafası vardır, bu nedenle hesaplamayı tek bir basamakta çok küçük işlem adımlarına bölmek zorunda kalır. (2) Tek bir kaseti vardır, bu yüzden kişinin üzerinde çalışmak istediği numarayı bulmak ve onu diğer numaralardan ayrı tutmak için biraz zahmete girmesi gerekir” (Shepherdson ve Sturgis (1963) s. 218).

Gerçekten de, Turing makinesi örnekleri , Post-Turing makinesi ve kısmi fonksiyondaki örneklerin gösterdiği gibi, iş "karmaşık" olabilir.

Minsky, Melzak-Lambek ve Shepherdson–Sturgis modelleri "kaseti keser"

Öyleyse neden her biri sonsuz uzunlukta (herhangi bir boyuttaki tamsayıyı barındıracak şekilde) ama sol uçlu olacak ve bu üç kasete "Post-Turing (yani Wang benzeri) bantlar" diyebilecek şekilde 'kaseti kesmiyorsunuz'? Tek tek kafalar sola (azaltma için) ve sağa (artırma için) hareket edecektir. Bir anlamda, kafalar, birleştirilmiş işaretlerin "yığının üst kısımlarını" gösterir. Veya Minsky (1961) ve Hopcroft ve Ullman'da (1979, s. 171ff) bant, sol uçtaki bir işaret dışında her zaman boştur - hiçbir zaman bir kafa yazdırır veya silmez.

Talimatlarımızı yazarken dikkatli olmalıyız, böylece azaltmadan önce bir sıfır testi ve atlama gerçekleşir, aksi takdirde makinemiz "sondan düşer" veya "sona çarpar" - kısmi bir örneğiniz olacak işlev. Bir eksiltmeden önce makinemiz her zaman şu soruyu sormalıdır: "Bant/sayaç boş mu? Eğer öyleyse ben eksiltemem, yoksa yapabilirim."

(im-) uygun çıkarma örneği için Kısmi işlev bölümüne bakın .

Minsky (1961) ve Shepherdson-Sturgis (1963) sadece bir kaç bantlar-olarak tek hala makine eşdeğer Turing izin olduğunca az kanıtlamak IF kasete veriler olarak temsil edilir Gödel sayısı (ya da diğer bazı benzersiz encodable- çözülebilir sayı); bu sayı hesaplama ilerledikçe gelişecektir. Gödel numarasının kodlandığı tek bant versiyonunda, sayaç makinesi (i) Gödel sayısını bir sabitle ("2" veya "3" sayıları) çarpabilmeli ve (ii) bir sabite ("2" sayıları) bölebilmelidir. veya "3") ve kalan sıfır ise atlayın. Minsky (1967), bu tuhaf talimat setine olan ihtiyacın, eğer iki bant mevcutsa { INC(r), JZDEC (r, z) } ve kolaylık talimatları { CLR (r), J(r) } ile gevşetilebileceğini göstermektedir. . Ancak yine de basit bir Gödelleştirme gereklidir. Elgot-Robinson'da (1964) RASP modellerine göre benzer bir sonuç ortaya çıkıyor.

Melzak'ın (1961) modeli farklıdır: çakıl yığınları deliklere girip çıkar

Melzak'ın (1961) modeli önemli ölçüde farklıdır. Kendi modelini aldı, bantları dikey olarak çevirdi, onlara "çakıl taşları" ile doldurulması için "yerdeki delikler" adını verdi. Minsky'nin "arttırma" ve "azaltma"sının aksine, Melzak herhangi bir çakıl sayısının uygun şekilde çıkarılmasına ve herhangi bir çakıl sayısının "eklenmesine" izin verdi.

Modeli için dolaylı adreslemeyi tanımlar (s. 288) ve kullanımına ilişkin iki örnek verir (s. 89); onun modelinin Turing eşdeğeri olduğuna dair "kanıtı" (s. 290-292) o kadar kabataslaktır ki, okuyucu dolaylı adreslemenin ispat için bir gereklilik olmasını isteyip istemediğini söyleyemez.

Melzak'ın modelinin mirası Lambek'in basitleştirilmesi ve onun anımsatıcı geleneklerinin Cook ve Reckhow 1973'te yeniden ortaya çıkmasıdır.

Lambek (1961), Melzak'ın modelini Minsky (1961) modeline atomize eder: INC ve DEC-testli

Lambek (1961), Melzak'ın üçlü modelini aldı ve onu iki tekli komuta atomize etti -X+, X- mümkünse aksi takdirde zıpla- Minsky'nin (1961) bulduğuyla tamamen aynı ikisi.

Bununla birlikte, Minsky (1961) modeli gibi, Lambek modeli de talimatlarını varsayılan-sıralı bir şekilde yürütür - hem X+ hem de X- bir sonraki komutun tanımlayıcısını taşır ve X- ayrıca, eğer sıfır ise atlama talimatını taşır. -test başarılı.

Elgot-Robinson (1964) ve dolaylı adresleme olmaksızın RASP sorunu

Bir RASP veya rasgele erişimli depolanmış program makinesi, "kayıtlarına" yerleştirilmiş "talimat programı" ile bir sayaç makinesi olarak başlar. Sonlu durum makinesinin "Talimat Kaydı"na benzer, ancak ondan bağımsız olarak, kayıtlardan en az biri ("program sayacı" (PC) olarak adlandırılır) ve bir veya daha fazla "geçici" kayıt, aşağıdakilerin kaydını tutar ve üzerinde çalışır: geçerli talimatın numarası. Sonlu durum makinesinin talimat TABLOSU, (i) mevcut program talimatını uygun kayıttan getirmekten, (ii) program talimatını ayrıştırmaktan , (iii) program talimatı tarafından belirtilen işlenenleri getirmekten ve (iv) program talimatını yürütmekten sorumludur. .

Bunun dışında bir sorun var: Karşı makine şasisine göre bu bilgisayar benzeri, von Neumann makinesi Turing eşdeğeri olmayacaktır. Hesaplanabilir olan her şeyi hesaplayamaz. Özünde model, (çok) sonlu durum makinesinin talimatlarının boyutuyla sınırlıdır . Sayaç makinesi tabanlı RASP, herhangi bir ilkel özyinelemeli işlevi (örn. çarpma) hesaplayabilir, ancak tüm özyinelemeli işlevleri (örn. Ackermann işlevi ) hesaplayamaz .

Elgot-Robinson, RASP modellerinin program talimatlarını "kendi kendine değiştirmesine" izin verme olasılığını araştırıyor. Fikir, Burks-Goldstine-von Neumann (1946-7) tarafından önerilen ve bazen "hesaplamalı git" olarak adlandırılan eski bir fikirdi. Melzak (1961) özellikle "hesaplanan goto"dan ismiyle bahseder, ancak bunun yerine modeline dolaylı adresleme sağlar.

Bilgisayarlı git: Bir MDP programı talimatlarının olduğunu değiştirir bir conditional- veya koşulsuz atlama içinde "git adresi" programı talimatı.

Ancak bu, sorunu çözmez (kişi Gödel sayılarına başvurmadıkça ). Gerekli olan, sonlu durum makinesinin talimat kaydının ve TABLO'nun üst sınırının (uzak) "ötesinde/üstünde" bulunan bir program komutunun adresini almak için bir yöntemdir .

Örnek: Yalnızca dört sınırsız yazmaçla donatılmış bir sayaç makinesi, örneğin, m ve n sayıları ne kadar büyük olursa olsun, p'yi vermek için herhangi iki sayıyı ( m, n ) birlikte çarpabilir ve böylece ilkel bir özyinelemeli işlev olabilir; üstelik bunu yapmak için 20'den az talimat gerekiyor! örneğin { 1: CLR ( p ), 2: JZ ( m, bitti ), 3 external_loop: JZ ( n, done ), 4: CPY ( m, temp ), 5: inner_loop: JZ ( m, external_loop ), 6: DEC ( m ), 7: INC ( p ), 8: J ( iç_döngü ), 9: dış_döngü: Aralık ( n ), 10 J ( dış_döngü ), DUR }

Ancak, yalnızca 4 kayıtla, bu makine, çarpma algoritmasını bir program olarak yürütebilen bir RASP oluşturmak için neredeyse yeterince büyük değil . Sonlu durum makinemizi ne kadar büyük inşa edersek edelim, her zaman daha büyük bir program (parametreleri dahil) olacaktır. Dolayısıyla, tanımı gereği, Gödel sayıları gibi sınırsız kodlama hilelerini kullanmayan sınırlı program makinesi evrensel olamaz .

Minsky (1967), { CLR (r), INC (r) ve RPT ("a" çarpı m komutları) ile donatılmış bir karşı makine (onlara "program bilgisayar modelleri" der) araştırmasında bu konuya işaret eder. n) }. Bize sorunu nasıl çözeceğimizi söylemiyor, ancak şunu gözlemliyor:

"... program bilgisayarının yapılması gereken kaç RPT'nin kaldığını takip etmenin bir yolu olmalı ve bu, bilgisayarın sonlu bölümünde izin verilen herhangi bir belirli depolama miktarını tüketebilir. RPT işlemleri kendi sonsuz kayıtlarını gerektirir. , genel olarak ve ele aldığımız diğer operasyon türlerinden farklı şekilde ele alınmalıdır." (s. 214)

Ancak Elgot ve Robinson sorunu çözüyor: P ₀ RASP'lerini dizinlenmiş bir dizi talimatla artırıyorlar - dolaylı adreslemenin biraz daha karmaşık (ama daha esnek) bir biçimi. P' ₀ modelleri, "temel" kaydın (talimatta belirtilen) içeriğini talimatta açıkça belirtilen "endekse" ekleyerek (veya tam tersi, "taban" ve "indeks" değiştirerek) kayıtları ele alır. Böylece indeksleme P' ₀ komutları, indeksleme yapmayan P ₀ komutlarından bir fazla parametreye sahiptir :

Örnek: INC ( r _taban , dizin ) ; etkin adres [r _base ] + index olacaktır, burada doğal sayı "indeks" sonlu durum makine talimatının kendisinden türetilmiştir.

Hartmanis (1971)

1971'de Hartmanis, RASP modelinde kullanılmak üzere dolaylı endekslemeyi basitleştirdi .

Dolaylı adresleme: Bir işaretçi kaydı, sonlu durum makinesine talimat için gereken hedef kaydın adresini sağlar. Başka bir şekilde söyledi: İşaretçi kaydının içeriği , talimat tarafından kullanılacak "hedef" kaydının adresidir . İşaretçi kaydı sınırsızsa, RAM ve kasasında yerleşik uygun bir RASP, Turing eşdeğeri olacaktır. Hedef kayıt, talimatta belirtildiği gibi, kaynak veya hedef kayıt olarak hizmet edebilir.

Sonlu durum makinesinin bu hedef kaydın adresini açıkça belirtmesi gerekmediğine dikkat edin. Sadece makinenin geri kalanına şunu söylüyor: İşaretçi kaydım tarafından işaret edilen kaydın içeriğini bana getir ve onunla xyz yap. Bu işaretçi kaydını (örneğin "N" veya "72" veya "PC", vb.) kendi talimatı aracılığıyla açıkça belirtmesi gerekir, ancak işaretçi kaydının gerçekte hangi sayıyı içerdiğini bilmesi gerekmez ( belki 279.431).

Cook ve Reckhow (1973) RAM'i tanımlar

Cook ve Reckhow (1973) Hartmanis'ten (1971) alıntı yapar ve modelini rastgele erişimli bir makine (RAM—yani dolaylı ve Harvard mimarisi olan bir makine) olarak adlandırdıkları şeye basitleştirir. Bir anlamda Melzak'a (1961) geri döndük ama Melzak'ınkinden çok daha basit bir modelle.

Öncelik

Minsky, MIT Lincoln Laboratuvarı'nda çalışıyordu ve çalışmalarını orada yayınladı; makalesi 15 Ağustos 1960'ta Annals of Mathematics'te yayınlanmak üzere alındı , ancak Kasım 1961'e kadar yayınlanmadı. Alındı, Melzak ve Lambek'in çalışmalarının alınmasından ve yayınlanmasından tam bir yıl önce gerçekleşti (sırasıyla, Mayıs ve 15 Haziran'da alındı). , 1961 ve Eylül 1961'de yan yana yayınlandı). (i) her ikisinin de Kanadalı olduğunu ve Kanada Matematik Bülteni'nde yayınlandığını , (ii) Minsky'nin çalışmasına atıfta bulunmayacağını çünkü henüz hakemli bir dergide yayınlanmadığını, ancak (iii) Melzak'ın Wang'a ve Lambek referanslarına atıfta bulunduğunu Melzak, birinin çalışmalarının eşzamanlı ve bağımsız olarak gerçekleştiğini varsaymasına yol açar.

Hemen hemen aynı şey Shepherdson ve Sturgis'e de oldu. Kağıtları Aralık 1961'de, Melzak ve Lambek'in çalışmalarının alınmasından sadece birkaç ay sonra alındı. Yine, Minsky'nin çalışmalarını gözden geçirmekten çok az (en fazla 1 ay) ya da hiç yararları yoktu. Dipnotlarda, Ershov, Kaphengst ve Peter'ın makalelerinin "yakın zamanda ortaya çıktığını" (s. 219) gözlemlemeye özen gösterdiler. Bunlar çok daha önce yayınlandı, ancak Almanca dergilerde Almanca olarak yayınlandı, bu nedenle erişilebilirlik sorunları ortaya çıktı.

Shepherdson ve Sturgis'in son makalesi, 1963'e kadar hakemli bir dergide yayımlanmadı. Ve onların Ek A'da adil ve dürüstçe belirttikleri gibi, Kaphengst (1959), Ershov (1958), Peter (1958)'in 'sistemleri'. hepsi daha sonra elde edilen sonuçlara o kadar benzer ki, aşağıdakilerden bir diziden ayırt edilemez:

0 üret, yani 0 → n

bir sayıyı artır, yani n+1 → n

"yani doğal sayıları oluşturan işlemleri yapmak" (s. 246)

bir sayıyı kopyala, yani n → m

iki sayıyı karşılaştırarak veya 0'a kadar azaltarak "hesaplamanın gidişatını değiştirmek" için

Gerçekten de, Shepherson ve Sturgis şu sonuca varıyor:

"Çeşitli minimal sistemler çok benzer"( s. 246)

Emriyle yayın tarihini KAPHENGST (1959), Ershov (1958), (1958) Peter çalışmalarını ilk idi.

Ayrıca bakınız

bibliyografya

Arka plan metinleri: Aşağıdaki kaynak makale bibliyografyası, arka plan olarak kullanılacak bir dizi metin içerir. 1950'lerde ve 1960'larda soyut makinelerle ilgili makalelerin telaşına yol açan matematik, van Heijenoort'ta (1967) bulunabilir; bu, Frege'den (1879) Gödel'e (1931) 50 yılı kapsayan orijinal makalelerin bir derlemesidir. Davis (ed.) Karar Verilemez (1965) meşaleyi Gödel'den (1931) başlayarak Gödel'in (1964) postscriptum'u (s. 71) boyunca taşır; orijinal kağıtları Alan Turing (1936-7) ve Emil Post (1936) yer almaktadır undecidable . The Undecidable'daki orijinal makalelerin yeniden basımları olarak görünen Church, Rosser ve Kleene'nin matematiği, makinelerin arkasındaki matematiği daha derinden anlamak isteyen herkes için zorunlu bir metin olan Kleene'de (1952) daha da ileri götürülür . Hem Kleene (1952) hem de Davis (1958) birkaç makale tarafından referans alınmıştır.

Sayaç makinesinin iyi bir şekilde ele alınması için Minsky (1967) Bölüm 11 "Dijital Bilgisayarlara Benzer Modeller"e bakın—sayaç makinesine "program bilgisayarı" diyor. Van Emde Boas'ta (1990) yeni bir genel bakış bulunmaktadır. Minsky (1961)/Lambek (1961) modelinin yakın tarihli bir incelemesi Boolos-Burgess-Jeffrey (2002); Turing makinelerinin eşdeğerliğini ve kısmi özyinelemeli işlevleri göstermek için Lambek'in "abakus modelini" yeniden canlandırıyorlar ve hem soyut makine modellerine (ters ve Turing-) hem de özyineleme teorisinin matematiğine lisansüstü düzeyde bir giriş sağlıyorlar. Boolos-Burgess'in (1970) ilk baskısından başlayarak bu model hemen hemen aynı işlemle ortaya çıktı.

Makaleler : Makaleler Wang (1957) ve onun Turing makinesini çarpıcı biçimde basitleştirmesiyle başlıyor. Turing (1936), Kleene (1952), Davis (1958) ve özellikle Post (1936) Wang (1957); sırayla, Turing bantlarını bağımsız olarak "sayaçlara" indirgedikleri için Melzak (1961), Minsky (1961) ve Shepherdson–Sturgis (1961-3) tarafından Wang'a atıfta bulunulur. Melzak (1961), delikli çakıl karşı makine modelini dolaylı olarak sağlar, ancak işlemi daha ileriye taşımaz. Elgot-Robinson'ın (1964) çalışması RASP'yi (bilgisayar benzeri rasgele erişimli depolanmış program makineleri) tanımlar ve mu-özyinelemeli işlevleri hesaplamak için sınırlı sayaç makinesinin başarısızlığını araştıran ilk kişi gibi görünmektedir . Bu başarısızlık - Gödel sayılarının Minsky (1961) tarzında acımasız kullanımı dışında - RASP modelleri için "dizine alınmış" yönergeler (yani dolaylı adresleme) tanımlamalarına yol açar. Elgot–Robinson (1964) ve daha fazlası Hartmanis (1971) kendi kendini değiştiren programlarla RASP'leri araştırır. Hartmanis (1971), Cook'un (1970) ders notlarına atıfta bulunarak dolaylı bir talimat seti belirtir. Hesaplama karmaşıklığı araştırmalarında kullanılmak üzere Cook ve yüksek lisans öğrencisi Reckhow (1973), bir RAM tanımını sağlar (modelleri ve anımsatıcı kuralları Melzak'ınkine benzer, ancak makalede ona herhangi bir referans sunmaz). İşaret makineleri, Knuth'un (1968, 1973) ve bağımsız olarak Schönhage'in (1980) bir dalıdır.

Makalelerin çoğu, lisans seviyesinin ötesinde matematik içerir - özellikle Kleene'de (1952) zarif bir şekilde sunulan ve daha az derinlemesine, ancak yine de Boolos-Burgess-Jeffrey'de (2002) yararlı olan ilkel özyinelemeli işlevler ve öz yinelemeli işlevler .

Dört yıldızlı hariç tüm metinler ve kağıtlar tanık oldu. Bu dördü Almanca yazılmıştır ve Shepherdson–Sturgis (1963) ve Elgot–Robinson'da (1964); Shepherdson–Sturgis (1963), Shepherdson–Sturgis'in Ek A'sında elde ettikleri sonuçların kısa bir tartışmasını sunar. En az bir makalenin terminolojisi (Kaphengst (1959), Burke-Goldstine-von Neumann'a (1946-7) benziyor gibi görünmektedir. bilgisayar mimarisinin analizi.

Yazar	Yıl	Referans	Turing makinesi	Sayaç makinesi	Veri deposu	TÖRPÜ	işaretçi makinesi	dolaylı adresleme	Kendi kendini değiştiren program
Goldstine ve von Neumann	1947
Kleene	1952
*Hermes	1954, 5			?
Wang	1957			ipuçları				ipuçları
*Peter	1958			?
Davis	1958
*Erşov	1959			?
*Kopengst	1959			?
melzak	1961								ipuçları
Lambek	1961
Minsky	1961
Shepherdson ve Sturgis	1963							ipuçları
Elgot ve Robinson	1964
Davis - Kararsız	1965
van Heijenoort	1967
Minsky	1967				ipuçları			ipuçları
Knuth	1968, 73
Hartmani	1971
Cook & Reckhow	1973
Schönhage	1980
van Emde Boas	1990
Boolos ve Burgess; Boolos, Burgess ve Jeffrey	1970-2002

Referanslar

Notlar

Kaynaklar

• Wolfram, Stephen (2002). Yeni Bir Bilim Türü . Wolfram Media, Inc. s.  97-102 . ISBN'si 1-57955-008-8.

Dış bağlantılar

• Weisstein, Eric W. "Makineyi kaydet " . Matematik Dünyası .
• Igblan - Minsky Kayıt Makinaları