Rastgele erişimli makine - Random-access machine

Olarak bilgisayar biliminin , rasgele erişim makinesi ( RAM ) bir bir soyut makine genel sınıfta yazmaç makineleri . RAM, sayaç makinesine çok benzer, ancak eklenmiş yazmaçlarına 'dolaylı adresleme' yeteneği ile. Sayaç makinesi gibi RAM'in de talimatları makinenin sonlu durum bölümünde ( Harvard mimarisi olarak adlandırılır ) bulunur.

RAM'in evrensel Turing makinesinin eşdeğeri - verilerinin yanı sıra kayıtlardaki programı ile - rastgele erişimli depolanmış program makinesi veya RASP olarak adlandırılır. Sözde von Neumann mimarisinin bir örneğidir ve yaygın bilgisayar kavramına en yakındır .

Birlikte Turing makinesi ve karşı-makine modellerinin , RAM ve MDP modelleri için kullanılan hesaplama karmaşıklığı analizi . Van Emde Boas (1990) , " paralel rastgele erişimli makine " modellerinden ayırt etmek için bu üç artı işaretçi makinesini "sıralı makine " modelleri olarak adlandırır.

Modele giriş

Rastgele erişimli makine (RAM) kavramı, karşı makine modeli olarak adlandırılan en basit modelle başlar . Bununla birlikte, iki ekleme, onu tezgah makinesinden uzaklaştırır. İlki, makineyi dolaylı adreslemenin rahatlığıyla geliştirir; ikincisi , en yaygını "akümülatör" olarak adlandırılan bir veya daha fazla yardımcı (adanmış) yazmaç ekleyerek modeli daha geleneksel akümülatör tabanlı bilgisayara doğru hareket ettirir .

Resmi tanımlama

Bir rasgele erişimli makinesi (RAM), bir çok-yazmacı özdeş soyut hesaplama makinesi modelidir tezgah makinesi dolaylı adresleme ilavesiyle gerçekleştirilebilir. Sonlu durum makinesinin TABLOSU'ndan bir talimatın takdirine bağlı olarak , makine bir "hedef" kaydın adresini ya (i) doğrudan talimatın kendisinden veya (ii) dolaylı olarak içeriğinden (örn. sayı, etiket) türetir . talimatta belirtilen "işaretçi" kaydı.

Tanım olarak: Bir kayıt , hem bir adrese (bir doğal sayıya eşdeğer benzersiz, ayırt edilebilir bir adlandırma/yer belirleyici) hem de bir içeriğe - tek bir doğal sayıya sahip bir konumdur . Kesinlik için Boolos-Burgess-Jeffrey'den (2002) elde edilen yarı-biçimsel sembolizmi, bir kaydı, içeriğini ve bir kayıt üzerindeki bir işlemi belirtmek için kullanacağız:

[r], "r adresli kaydın içeriği" anlamına gelir. Buradaki "r" etiketi, doğal bir sayı veya bir harf (örneğin "A") veya bir ad ile doldurulabilen bir "değişkendir".
→ "kopyala/yatır" veya "değiştirir" anlamına gelir, ancak kaynak yok edilmez

Örnek: [3] +1 → 3; "3" adresli kaynak kaydının içeriği artı 1, "3" adresli hedef kaydına konur (burada kaynak ve hedef aynı yerdir). [3]=37 ise, yani, kayıt 3 "37" sayısıdır, ardından 37+1 = 38 kayıt 3'e konur.

Örnek: [3] → 5; "3" adresli kaynak kaydın içeriği "5" adresli hedef kaydına konur. [3]=38 ise yani kayıt 3'ün içeriği 38 numara ise bu sayı kayıt 5. kayıt 3'ün içeriği bu işlem tarafından rahatsız edilmez, bu nedenle [3], şimdi [5] ile aynı olan 38 olmaya devam eder.

Tanım: Doğrudan talimat, içeriği talimatın konusu olacak kaynak veya hedef kaydının adresini talimatın kendisinde belirten bir talimattır. Tanım: Dolaylı bir talimat , içeriği bir "hedef" kaydının adresi olan bir "işaretçi kaydı" belirten bir talimattır . Hedef kayıt, bir kaynak veya bir hedef olabilir (çeşitli KOPYALAMA talimatları bunun örneklerini sağlar). Bir kayıt, kendisini dolaylı olarak adresleyebilir.

Bir standart/kural gereği, bu makale talimatta bir parametre (veya parametreler) olarak "d/i" olarak kısaltılan "doğrudan/dolaylı"yı belirtecektir:

Örnek: KOPYALAMA ( d , A, ı , K) yöntemi, direkt olarak d kaynak kasan adresi talimatı kendisinden ( "A" kayıt) elde ancak dolaylı ı , N [N] = 3 varsayalım işaretçi kayıt hedef adresini almak sonra kayıt 3 hedeftir ve talimat aşağıdakileri yapacaktır: [A] → 3.

Tanım: Kaynak kaydının içeriği talimat tarafından kullanılır. Kaynak kaydının adresi, (i) doğrudan talimat tarafından veya (ii) talimat tarafından belirtilen işaret kaydı tarafından dolaylı olarak belirtilebilir.

Tanımı: içeriği işaret kayıt olan adres "hedef" kayıt.

Tanım: İşaretçi kaydının içeriği hedef kaydı işaret eder - "hedef" bir kaynak veya hedef kaydı olabilir.

Tanım: Hedef kaydı , talimatın sonucunu verdiği yerdir. Kaynak kaydının adresi, (i) doğrudan talimat tarafından veya (ii) talimat tarafından belirtilen işaret kaydı tarafından dolaylı olarak belirtilebilir. Kaynak ve hedef kayıtlar bir olabilir.

Tazeleme: Karşı makine modeli

Melzak (1961), bir karşı makinenin kolay görselleştirilmesini sağlar: "kayıtları" zemindeki deliklerdir ve bu delikler çakıl taşlarını tutar. Bir talimat uyarınca, bu deliklerin içine ve dışına "bilgisayar" (kişi veya makine) tek bir çakıl ekler (ARTTIRIR) veya kaldırır (AZALTIR). Gerektiğinde, ek çakıl taşları gelir ve fazla çakıl taşları sonsuz bir arza geri döner; delik çakıl taşlarını barındıramayacak kadar küçükse, "bilgisayar" deliği daha büyük kazar.

Minsky (1961) ve Hopcroft-Ullman 1979 (s. 171) , "kayıtlar" kadar sol uçlu bant içeren çok bantlı bir Turing makinesinin görselleştirilmesini sunar . Her bandın uzunluğu sağa doğru sınırsızdır ve işaretli sol uç hariç her kare boştur. Mesafe bant-kareler sayılarında ölçülen sol ucundan bir bandın "kafa", bir "kayıt" doğal sayısını temsil eder. Karelerin sayısını azaltmak için bant kafası sola hareket eder; Arttır, doğru hareket eder. Bant üzerindeki işaretleri yazdırmaya veya silmeye gerek yoktur; tek koşullu talimat, başın sol uçta olup olmadığını kontrol etmek için bir sol uç işaretini bir "işaretliyse atlama talimatı" ile test etmektir.

Aşağıdaki talimat "anımsatıcılar", örneğin "CLR (r)" keyfidir; standart yok.

Kayıt makinesi onun sonlu durum makinesine harici bir bellek için, var - bir sınırsız (cf: dipnot | sayılabilen ve sınırsız) ile ayrık ve benzersiz etiketli yerlerin koleksiyonunu sınırsız "kayıt" olarak adlandırılan kapasitesi. Bu kayıtlar yalnızca doğal sayıları (sıfır ve pozitif tam sayılar) tutar. Sonlu durum makinesinin TABLOSU'ndaki sıralı talimatların bir listesine göre, bu "kayıtların" içerikleri üzerinde birkaç (örn. 2) ilkel işlem türü çalışır. Son olarak, bir veya iki kaydın içeriğini test etmek ve sonlu durum makinesini varsayılan komut dizisinden "dallamak/atlamak" için IF-THEN-ELSE biçiminde bir koşullu ifade mevcuttur.

Temel model 1 : Minsky'nin (1961) görselleştirmesine ve Lambek'e (1961) en yakın model:

{R kaydını yazmaç r kadar azaltmaya içeriklerinin Artım içeriği IF yazmaç r içeriği sıfır olduğu SONRA talimat I Git _z BAŞKA sonraki talimat devam}:

Talimat	anımsatıcı	Kayıt(lar) üzerindeki işlem "r"	Sonlu durum makinesinin Talimat Kaydı, IR üzerindeki eylem
artış	INC ( r )	[r] + 1 → r	[IR] + 1 → Kızılötesi
Azaltma	Aralık ( r )	[r] - 1 → r	[IR] + 1 → Kızılötesi
Sıfır ise atla	JZ ( r, z )	Yok	EĞER [r] = 0 SONRA z → IR ELSE [IR] + 1 → IR
Dur	H	Yok	[KÖ] → KÖ

Temel model 2 : "halef" modeli ( Peano aksiyomlarının ardıl işlevinden sonra adlandırılır ):

{ r kaydının içeriğini artır, r kaydının içeriğini CLEAR, r kaydının içeriğini IF kaydı r _j kaydının içeriğine eşittir r _k THEN komutuna atla I _z ELSE sonraki komuta git }

Talimat	anımsatıcı	Kayıt(lar) üzerindeki işlem "r"	Sonlu durum makinesinin Talimat Kaydı, IR üzerindeki eylem
Açık	CLR ( r )	0 → r	[IR] + 1 → Kızılötesi
artış	INC ( r )	[r] + 1 → r	[IR] + 1 → Kızılötesi
Eşit ise atla	JE (r1, r2, z)	Yok	EĞER [r1] = [r2] SONRA z → IR ELSE [IR] + 1 → IR
Dur	H	Yok	[KÖ] → KÖ

Temel model 3 : Elgot-Robinson (1964) tarafından sınırlı ve sınırsız RASP'lerin araştırılmasında kullanılır – CLEAR yerine COPY ile "halef" modeli:

{ARTTIRMA yazmaç r içeriği, Sicil içeriğini KOPYA _j r kayıt _k , IF Sicil içeriği _j Sicil içeriğini eşittir _k sonra kullanıcı I Git _z BAŞKA sonraki talimata Goto}

Talimat	anımsatıcı	Kayıt(lar) üzerindeki işlem "r"	Sonlu durum makinesinin Talimat Kaydı, IR üzerindeki eylem
KOPYALA	KOPYALA (r1, r2)	[r1] → r2	[IR] + 1 → Kızılötesi
artış	INC ( r )	[r] + 1 → r	[IR] + 1 → Kızılötesi
Eşit ise atla	JE (r1, r2, z)	Yok	EĞER [r1] = [r2] SONRA z → IR ELSE [IR] + 1 → IR
Dur	H	Yok	[KÖ] → KÖ

Temel kümelerden "kolaylık talimatları" oluşturma

Yukarıdaki üç temel küme 1, 2 veya 3, bir kümenin talimatlarını başka bir kümenin talimatlarını kullanarak oluşturabilme anlamında eşdeğerdir (ilginç bir alıştırma: Minsky'den bir ipucu (1967) – ayrılmış bir kayıt bildir örn. 0 sayısını içermesi için "0" (veya "sıfır" için Z veya "silme" için E). Model seçimi, bir yazarın bir gösteride veya bir kanıtta, vb. kullanmayı en kolay bulduğuna bağlı olacaktır.

Ayrıca, 1, 2 veya 3 taban kümelerinden ilkel özyinelemeli işlevlerden herhangi birini oluşturabiliriz (cf Minsky (1967), Boolos-Burgess-Jeffrey (2002)). ( Toplam ve kısmi özyinelemeli işlevleri yakalamak için ağın nasıl daha geniş hale getirileceği dolaylı adresleme bağlamında tartışılacaktır). Ancak, komut kümeleri çok ... ilkel (küçük) olduğundan, ilkel özyinelemeli işlevleri oluşturmak zordur. Bir çözüm, belirli bir kümeyi başka bir kümeden "kolaylık talimatları" ile genişletmektir:

Bunlar geleneksel anlamda alt rutinler değil , temel setten oluşturulan ve bir anımsatıcı verilen talimat blokları olacaktır . Resmi anlamda, bu blokları kullanmak için ya (i) onları temel komut eşdeğerlerine "genişletmemiz" gerekir - bunlar geçici veya "yardımcı" kayıtların kullanılmasını gerektirecektir, bu nedenle model bunu hesaba katmalıdır, veya ( ii) makinelerimizi/modellerimizi 'yerleşik' talimatlarla tasarlayın.

Örnek: Temel set 1. CLR (r) oluşturmak için, register r'yi sıfıra geri saymak için talimat bloğunu kullanın. Yukarıda belirtilen ipucunun kullanımına dikkat edin:

CLR (r) = _eşdeğer
döngü : JZ (r, çıkış )

Aralık (r)
JZ (0, döngü )

çıkış : vb.

Yine, tüm bunlar yalnızca kolaylık sağlamak içindir; bunların hiçbiri modelin içsel gücünü artırmaz.

Örneğin: en genişletilmiş küme, üç kümeden her benzersiz talimatı ve ayrıca koşulsuz J (z) atlamasını içerir, yani:

{CLR (r), DEC (r), INC (r) CPY (r _s , r, _d ), JZ (r, z), JE (r _j , R _k , z), y (Z)}

Çoğu yazar, bir veya koşullu atlar diğer Örneğin Shepherdson-Sturgis (1963) almak Yukarıdaki set eksi JE kullanmak (- eğer Jump mükemmel onlar JNZ kullanmak doğru olması için değil ; henüz başka olası kolaylık talimat Sıfır JZ yerine).

"Dolaylı" işlem

Dolaylı adresleme örneği

Günlük hayatımızda "dolaylı operasyon" kavramı olağandışı değildir.

Örnek: Bir hazine avı.

"Tom_&_Becky's_cave_in_pirate_chest" konumunda, bizi "hazineye" yönlendiren bir harita bulabileceğimiz yer olacak:

(1) "Tom_&_Becky's_cave..." konumuna gidiyoruz ve tahta bir kutu bulana kadar etrafı kazıyoruz

(2) Kutunun içinde hazinenin yerini gösteren bir harita var: "under_Thatcher's_front_porch"

(3) "under_Thatcher's_front_porch" konumuna gidiyoruz, betonu çekiçle kaldırıyoruz ve "hazineyi" keşfediyoruz: bir çuval paslı kapı kolları.

İndirection bir görevi görür korsan göğüs olarak tanımlanan bir konum "_ & _ Becky's_cave Tom ..." belirten pointer içeriğinin (hazine haritası) ait "adresi" sağlamaktadır: (kendisi de dahil) herhangi bir başka yere hedef konum "under_Thatcher 's_front_porch" gerçek eylemin gerçekleştiği yer.

Neden dolaylı bir işleme ihtiyaç duyulur: Karşı makine modeliyle ilgili iki büyük sorun

Aşağıda, bu modellerin, fiziksel olarak gerçek olan herhangi bir şeyden iki temel farkı olan soyut modeller olduğu unutulmamalıdır: her biri sınırsız kapasiteye sahip sınırsız sayıda kayıt. Sorun, Turing eşdeğeri olan bir RASP oluşturmak için bir karşı makine modeli kullanmaya ve böylece herhangi bir kısmi özyinelemeli işlevi hesaplamaya çalıştığında en çarpıcı biçimde ortaya çıkar :

Melzak (1961), modelinin kendisini bir "hesaplanmış goto" ile değiştirebilmesi için "delik-ve-çakıl" modeline dolaylılığı ekledi ve kullanımına iki örnek verdi ("d ölçeğinde ondalık gösterim" ve "Sıralama ölçütü". büyüklük", bunların modelin Turing eşdeğeri olduğunun ispatında kullanılıp kullanılmadığı belirsizdir, çünkü "programın kendisi bir alıştırma olarak okuyucuya bırakılmıştır" (s. 292). Minsky (1961, 1967), uygun (ancak kullanımı zor) Gödel sayı kodlamasıyla, kayıt modelinin Turing eşdeğeri olması için dolaylıya ihtiyacı olmadığını gösterebildi ; ancak en az bir sınırsız kayıta ihtiyacı vardı. Aşağıda belirtildiği gibi, Minsky (1967), bir RASP için soruna işaret eder, ancak bir çözüm sunmaz. Elgot ve Robinson (1964), RASP modellerinin P ₀ - dolaylı yeteneği yoktur - kendi talimatlarını değiştirme yeteneği yoksa tüm "özyinelemeli sıralı işlevleri" (rastgele uzunlukta parametrelere sahip olanlar) hesaplayamadığını kanıtladı , ancak yapıyorsa Gödel sayıları aracılığıyla da olabilir (s. 395-397; özellikle şekil 2 ve dipnot s. 395). Öte yandan, bir "indeks kaydı" (dolaylı adresleme) ile donatılmış RASP modeli P' ₀ , tüm "kısmi özyinelemeli sıralı işlevleri" (mu özyinelemeli işlevler) hesaplayabilir (s. 397-398).

Cook ve Reckhow (1973) bunu en kısa ve öz biçimde söylüyor:

Dolaylı komutlar, sabit bir programın girdiler değiştikçe sınırsız sayıda kayda erişmesi için gereklidir." (s. 73)

Sınırsız kapasiteleri durum makinesi talimatlarının sınırlı kapasite karşı kayıtları : adlandırılan sonlu makinenin durumu parçası olması gerekiyordu - algoritma normal tanımla - çok "durumları" (talimatlar) ve sayısında her iki sonlu talimatların boyutları (sembolleri/işaretleri tutma kapasiteleri). Öyleyse bir durum makinesi, keyfi olarak büyük bir sabiti doğrudan bir kayıt defterine nasıl taşır, örneğin MOVE (k, r) (k sabitini r kaydına taşıyın)? Eğer çok büyük sabitler gerekliyse, bunlar ya kayıtların kendilerinden başlamalı ya da sonlu sayıda komut kullanılarak durum makinesi tarafından oluşturulmalıdır, örneğin INC ve DEC kullanarak alt yordamları çarpma ve ekleme (ancak bunlardan yarı-sonsuz sayıda değil!).

Bazen k sabiti, CLR ( r ) ve ardından k kez tekrarlanan INC ( r ) kullanılarak oluşturulur – örneğin, k=3 sabitini r kaydına koymak, yani 3 → r, yani komutun sonunda [r ]=3: CLR (r), INC (r), INC (r), INC (r). Bu numaradan Kleene (1952) s. 223. Sorun, oluşturulacak sayı sonlu durum makinesinin kullanabileceği komut sayısını tükettiğinde ortaya çıkar ; her zaman sonlu durum makinesinin kullanabileceği komut sayısından daha büyük bir sabit vardır .

Sınırsız sayıda kayıta karşı sınırlı durum-makine talimatları : Bu, ilk problemden daha ciddi. Özellikle, bu sorun , kayıtlarında bulunan bir "talimat programını" yorumlamak için sonlu durum makinesini kullanan bir "evrensel makine" (daha fazla bilgi için Universal Turing makinesine bakınız ) olan bir RASP oluşturmaya çalıştığımızda ortaya çıkar. bugünlerde bir adlandırılan inşa ediyoruz yani bilgisayar ile von Neumann mimarisi .

Sayaç makinesinin sonlu durum makinesinin adı/numarası ile açıkça (doğrudan) bir kaydı çağırması gerektiğine dikkat edin : INC (65,356) "65,365" kayıt numarasını açıkça çağırır . Kayıt sayısı, sonlu durum makinesinin bunları adresleme kapasitesini aşarsa , sınırların dışındaki kayıtlara ulaşılamaz. Örneğin, sonlu durum makinesi sadece 65.536 = 2 ¹⁶ register'a ulaşabiliyorsa, 65.537'ye nasıl ulaşabilir?

Peki nasıl mı biz sonlu durum makinesi sınırlarının ötesinde bir kayıt ele? Bir yaklaşım, program talimatlarını (kayıtlarda depolananlar) birden fazla komut içerecek şekilde değiştirmek olacaktır . Ancak bir talimat (potansiyel olarak) sınırsız boyutta olmadıkça bu da tükenebilir. Öyleyse neden sadece bir "über-talimat" kullanmıyorsunuz - gerçekten çok büyük bir sayı - içinde kodlanmış tüm program talimatlarını içeren ! Minsky sorunu bu şekilde çözer, ancak kullandığı Gödel numaralandırması modele büyük bir rahatsızlık verir ve sonuç, sezgisel bir "depolanmış program bilgisayarı" kavramına hiç benzemez.

Elgot ve Robinson (1964), "sonlu olarak belirlenmiş" bir RASP ile ilgili olarak benzer bir sonuca varmışlardır. Aslında, sınırsız sayıda kayda erişebilir (örneğin, onlardan talimat almak için), ancak RASP program talimatlarının "kendi kendini değiştirmesine" izin verirse ve "verilerini" bir Gödel numarasıyla kodlamışsa (Şekil 2 s. 396). ).

RPT (tekrar) talimatını kullanan daha bilgisayar benzeri bir model bağlamında Minsky (1967) bizi soruna bir çözümle cezbeder (karş. s. 214, s. 259), ancak kesin bir çözüm sunmaz. O iddia ediyor:

"Genel olarak bir RPT işlemi, makinenin sonlu-durum kısmında bir talimat olamaz... RPT işlemleri, kendilerine ait sonsuz kayıtlar gerektirir." (s. 214).

O bize sunduğu sınırlı CLR (r) ve INC (r) ile birlikte herhangi hesaplama işlemini yapabilmektedir RPT ilkel özyinelemeli fonksiyon ve o μ işletmeni rolünü olarak yukarıda alıntılanan sınırsız RPT sunar; CLR (r) ve INC (r) ile birlikte mu özyinelemeli fonksiyonları hesaplayabilir. Ancak "dolaylı" veya RAM modelini kendi başına tartışmıyor.

Hartmanis'teki (1971) referanslardan, Cook'un (UC Berkeley'deyken verdiği ders notlarında, 1970) dolaylı adresleme kavramını güçlendirdiği anlaşılıyor. Cook and Reckhow (1973) – Cook, Reckhow'un Yüksek Lisans tez danışmanıdır. Hartmanis'in modeli – Melzak'ın (1961) modeline oldukça benzerdir – iki ve üç kayıtlı toplama ve çıkarmalar ve iki parametre kopyası kullanır; Cook ve Reckhow'un modeli, bir "AC" akümülatörü kullanarak parametre sayısını (program talimatlarında belirtilen kayıtlar) bir çağrıya indirger.

Özetle çözüm: Makinemizi/modelimizi sınırsız dolaylı olarak tasarlayın – kaç tane olursa olsun herhangi bir kaydı potansiyel olarak adlandırabilen (çağıran) sınırsız bir "adres" kaydı sağlayın . Bunun çalışması için, genel olarak, sınırsız kayıt, temizlenme ve daha sonra potansiyel olarak sonsuz bir döngü tarafından artırılma (ve muhtemelen azaltılma) yeteneğine ihtiyaç duyar. Bu anlamda çözüm , gerektiğinde, aradığını bulana kadar sınırsız kayıt dizisi boyunca sonsuza kadar arayabilen sınırsız μ operatörünü temsil eder . İşaret kayıt tam bir haricinde herhangi bir başka kayıt gibidir: içerir "adresleme" olarak adlandırılan koşullarda kendi yerine, içeriği adresi-işlenen durumu makinenin TABLO hedef kaydının adres olduğu (muhtemelen kendisi de dahil olmak üzere !).

Sınırlı dolaylı ve ilkel özyinelemeli fonksiyonlar

Bir kayıttaki bir canavar sayısının Minsky yaklaşımından kaçınırsak ve makine modelimizin "bir bilgisayar gibi" olacağını belirtirsek, özyinelemeli işlevleri ( μ-özyinelemeli olarak da adlandırılır) hesaplayacaksak, bu dolaylılık sorunuyla yüzleşmemiz gerekir. fonksiyonlar ) – hem tam hem de kısmi çeşitler.

Daha basit karşı-makine modelimiz, "durumlara göre tanımlama" (Kleene (1952) p'de tanımlanmıştır) olarak adlandırılan ilkel özyinelemeli bir "operatör" kullanarak "sınırlı" bir dolaylılık biçimi yapabilir ve böylece ilkel özyinelemeli işlevlerin alt sınıfını hesaplayabilir. 229 ve Boolos-Burgess-Jeffrey s. 74). Böyle bir "sınırlı dolaylı yönlendirme" zahmetli, sıkıcı bir iştir. "Durumlara göre tanımlama", makinenin, her seferinde başarılı olana kadar, bu içeriği vaka operatörünün açıkça beyan ettiği bir sayı/ad ile eşleştirmeye çalışarak işaretçi kaydının içeriğini belirlemesini/ayırt etmesini gerektirir . Bu nedenle, vakalara göre tanımlama, örneğin alt sınır adresinden başlar ve bir eşleşme yapmaya çalışan üst sınır adresine doğru mide bulandırıcı bir şekilde devam eder:

N kaydındaki sayı 0'a eşit mi? Değilse, o zaman 1'e eşit mi? 2? 3? ... 65364? Değilse, son 65365 numaradayız ve bu numara olsa iyi olur, yoksa bir sorunumuz var!

"Sınırlı" dolaylılık, kısmi özyinelemeli işlevleri hesaplamamıza izin vermeyecektir - bunlar için sınırsız dolaylıya ihtiyacımız olanlar için μ operatörü .

Diyelim ki 65367 numaraya kadar devam edebildik ve aslında aradığımız şey o kasadaydı. O zaman hesaplamamızı başarıyla tamamlayabilirdik! Ama diyelim ki 65367 ihtiyacımız olana sahip değil. Ne kadar ileri gitmeye devam etmeliyiz?

To be eşdeğer Turing talihsiz tek kayıt Minsky ya kullanımına karşı makine ihtiyaçlarını Gödel sayısı yöntemi veya kayıt dize uçlarını keşfetmek için bir yeteneği sonsuza gerekirse de eklenmesi gerekiyor. ("Orada" bir şey bulamama hatası, bir algoritmanın sonlanmamasının ne anlama geldiğini tanımlar; bkz. Kleene (1952) s. 316ff Bölüm XII Kısmi Özyinelemeli İşlevler , özellikle s. 323-325.) aşağıdaki örnek.

Sınırsız dolaylı ve kısmi özyinelemeli fonksiyonlar

İçin sınırsız üçkâğıtla bizim makine modelinde bir "donanım" değişiklik yapılması gerekir. Bu değişikliği yaptığımızda, model artık bir sayaç makinesi değil, rastgele erişimli bir makinedir.

Şimdi, örneğin INC belirtildiğinde, sonlu durum makinesinin talimatı , ilgilenilen kaydın adresinin nereden geleceğini belirtmelidir . Bu , (i) açık bir etiket sağlayan durum makinesinin talimatı veya (ii) içeriği ilgilenilen adres olan işaretçi kaydı olabilir . Bir talimat bir kayıt adresi belirttiğinde, şimdi ayrıca "i/d" – "dolaylı/doğrudan" ek bir parametre belirtmesi gerekecektir. Bir anlamda, bu yeni "i/d" parametresi, talimatta belirtildiği gibi doğrudan adresi almak için bir yolu veya işaretçi kaydından dolaylı adresi almak için diğer yolu çeviren bir "anahtardır" (hangi işaretçi kaydı - bazılarında modellerde her kayıt bir işaretçi kaydı olabilir - talimat tarafından belirtilir). Bu "birbirini dışlayan fakat kapsamlı seçim", "durumlara göre tanımlamanın" bir başka örneğidir ve aşağıdaki örnekte gösterilen aritmetik eşdeğer, Kleene (1952) s. 229.

Örnek: CPY ( dolaylı _kaynak , r _kaynak , doğrudan _hedef , r _hedef )

Doğrudan adreslemeyi d="0" ve dolaylı adreslemeyi i="1" olarak belirtmek için bir kod atayın. Daha sonra makinemiz kaynak adresini şu şekilde belirleyebilir:

i*[r _s ] + (1-i)*r _s

Örneğin, kayıt 3'ün içeriğinin "5" (yani [3]=5 ) ve kayıt 4'ün içeriğinin "2" (yani [4]=2 ) olduğunu varsayalım:

Örnek: CPY ( 1, 3, 0, 4 ) = CPY ( dolaylı, kayıt 3, doğrudan, kayıt 4)

1*[3] + 0*3 = [3] = kaynak-kayıt adresi 5

0*[4] + 1*4 = 4 = hedef kayıt adresi 4

Örnek: CPY ( 0, 3, 0, 4)

0*[3] + 1*3 = 3 = kaynak-kayıt adresi 3

0*[4] + 1*4 = 4 = hedef kayıt adresi 4

Örnek: CPY ( 0, 3, 1, 4)

0*[3] + 1*3 = 3 = kaynak-kayıt adresi 3

1*[4] + 0*4 = [4] = hedef kayıt adresi 2

Dolaylı KOPYALAMA talimatı

Muhtemelen eklenen talimatların en kullanışlısı COPY'dir. Gerçekten de, Elgot-Robinson (1964) P ₀ ve P' ₀ modellerine COPY talimatlarını sağlar ve Cook-Reckhow (1973) akümülatör temelli modellerine yalnızca iki dolaylı talimat sağlar – akümülatöre dolaylı olarak COPY, akümülatörden dolaylı olarak COPY .

Çok sayıda talimat : Tek bir kayıt üzerinde hareket eden herhangi bir talimat dolaylı "ikili" (koşullu ve koşulsuz atlamalar dahil, Elgot-Robinson modeline bakınız) ile artırılabildiğinden, dolaylı talimatların dahil edilmesi tek parametre/ komutları kaydedin (örn. INC (d, r), INC (i, r)). Daha da kötüsü, her iki parametre/kayıt talimatının 4 olası çeşidi olacaktır, örneğin:

CPY (d, R _s , D, R _d =) doğrudan kopyalama hedef-kayıt doğrudan kaynak kayıt

CPY (i, r _sp , d, r _d ) = Kaynak işaretçi kaydında bulunacak kaynak adresini kullanarak dolaylı olarak hedef kaydına COPY r _sp .

CPY (d, R _s , ı, r, _dp ) ait = KOPYA içeriği hedef-işaret kayıt R bulunabilir hedef adresini kullanarak yazmacına dolaylı kaynak kayıt _dp .

CPY (i, r _sp , i, r _dp ) = Kaynak-işaretçi kaydında r _sp bulunacak adrese sahip kaynak kaydının içeriğini , hedef-işaretçi kaydında r bulunacak adresle birlikte hedef kaydına dolaylı olarak KOPYALA _dp )

Benzer şekilde, iki kaynak kaydı r _s1 r _s2 ve bir hedef kaydı r _d içeren her üç kayıt talimatı 8 çeşitle sonuçlanacaktır, örneğin aşağıdakiler:

[r _s1 ] + [r _s2 ] → r _d

verecek:

EKLE ( d, r _s1 , d, r _s2 , d, r _d )
EKLE ( i, r _sp1 , d, r _s2 , d, r _d )
EKLE ( d, r _s1 , i, r _sp2 , d, r _d )
EKLE ( i, r _sp1 , i, r _sp2 , d, r _d )
EKLE ( d, r _s1 , d, r _s2 , i, r _dp )
EKLE ( i, r _sp1 , d, r _s2 , i, r _dp )
EKLE ( d, r _s1 , i, r _sp2 , i, r _dp )
EKLE ( i, r _sp1 , i, r _sp2 , i, r _dp )

Bir kaydı "akümülatör" olarak belirlersek (aşağıya bakın) ve izin verilen çeşitli talimatlara güçlü kısıtlamalar koyarsak, doğrudan ve dolaylı işlemlerin bolluğunu büyük ölçüde azaltabiliriz. Bununla birlikte, sonuçta ortaya çıkan azaltılmış komut kümesinin yeterli olduğundan emin olunmalı ve azaltmanın "önemli" işlem başına daha fazla talimat pahasına olacağının farkında olmalıyız.

"Akümülatör A" kavramı

Tarihsel gelenek, bir dizi aritmetik işlem sırasında sayısını tam anlamıyla biriktiren bir "aritmetik organ" olan akümülatöre bir kayıt ayırır:

"Aritmetik organımızın ilk kısmı... bir sayı alabilen ve içinde bulunana ekleyebilen, içeriğini de temizleyebilen ve içerdiğini depolayabilen paralel bir depolama organı olmalıdır. Böyle bir organa Akümülatör deyin.Örneğin masa çarpanları, standart IBM sayaçları, daha modern röle makineleri, ENIAC" (orijinalinde kalın yazı: Goldstine ve von Neumann) , 1946; s. 98, Bell ve Newell 1971).

Bununla birlikte, akümülatör, özellikle "kayıt r2 tarafından işaret edilen kaydın içeriğini dolaylı olarak artır" gibi "oku-değiştir-yaz" talimatları ile ilgili olarak, aritmetik "işlem" başına daha fazla talimat pahasına gelir. "A", "akümülatör" kaydı A'yı belirtir:

Etiket	Talimat	A	r2	r378.426	Açıklama
		. . .	378.426	17
INCi ( r2 ):	CPY ( i, r2, d, A )	17	378.426	17	r2 içeriği "17" içerikli r378,426'yı gösterir: bunu A'ya kopyalayın
	INC (A)	18	378.426	17	A'nın tütsü içeriği
	CPY ( d, A, ben, r2 )	18	378.426	18	r2'nin içeriği r378.426'yı gösterir: A'nın içeriğini r378.426'ya kopyalayın

Akümülatör için belirli bir isimle, örneğin "A" ile kalırsak, akümülatörü talimatlarda ima edebiliriz, örneğin,

INC ( A ) = INCA

Ancak, CPY talimatlarını akümülatör çağırmadan yazdığımızda, talimatlar belirsizdir veya boş parametrelere sahip olmalıdır:

CPY ( d, r2, d, A ) = CPY (d, r2, , )

CPY ( d, A, d, r2 ) = CPY ( , , d, r2)

Tarihsel olarak bu iki CPY talimatı ayırt edici isimler almıştır; ancak, herhangi bir sözleşme mevcut değildir. Gelenek (örneğin Knuth'un (1973) hayali MIX bilgisayarı) LOAD ve STORE adında iki isim kullanır. Burada "i/d" parametresini ekliyoruz:

LDA ( d/i, r _s ) = _def CPY ( d/i, r _s , d, A )

STA ( d/i, r _d ) = _def CPY ( d, A, d/i, r _d )

Tipik akümülatör tabanlı model, iki değişkenli aritmetik ve sabit işlemlerinin tümüne sahip olacaktır (örneğin ADD (A, r), SUB (A, r)) ) kullanımı (i) akümülatörün içeriği ile birlikte (ii) belirli bir kaydın içeriği . Tek değişkenli işlemler (örneğin INC (A), DEC (A) ve CLR (A) ) yalnızca akümülatörü gerektirir. Her iki komut türü de sonucu (örneğin toplam, fark, çarpım, bölüm veya kalan) akümülatöre depolar.

Örnek: INCA = [A] +1 → A

Örnek: ADDA (r _s ) = [A] [r _s ] → bir

Örnek: MULA (r _s ) = [A] * [r _s ] → bir

Böyle seçersek, anımsatıcıları kısaltabiliriz çünkü en az bir kaynak kayıt ve hedef kayıt her zaman akümülatör A'dır. Böylece elimizde:

{LDA (I / D, R _s ), STA (I / D, R _d ), CLRA INCA, deka, ADDA (r _s ), SUBA (r _s ), MULA (r _s ), DIVA (r _s ) , vesaire.)

Dolaylı adres kaydı "N" kavramı

Bizim model ise sınırsız akümülatör biz yapabilirsiniz bağlı tüm diğer kayıtlarını? Dolaylı adreslerimizi türettiğimiz en az bir sınırsız kayıt sağlayana kadar olmaz.

Minimalist yaklaşım kendini kullanmaktır (Bunu Schönhage yapar).

Başka bir yaklaşım (Schönhage bunu da yapar) belirli bir kaydı "dolaylı adres kaydı" olarak ilan etmek ve bu kayıtla ilgili dolaylılığı sınırlamaktır (Schonhage'in RAM0 modeli, dolaylı ve doğrudan talimatlar için hem A hem de N kayıtlarını kullanır). Yine yeni kaydımızın geleneksel bir adı yoktur - belki "iNdex"ten "N" veya "iNdirect" veya "adres Numarası".

Maksimum esneklik için, A akümülatörü için yaptığımız gibi – N'yi artırma, eksiltme, temizleme, test etme, doğrudan kopyalama, vb.'ye tabi olan başka bir kayıt olarak ele alacağız. Yine talimatı, yön sağlayan tek bir parametreye küçültebiliriz. ve örneğin dolaylılık.

LDAN (i/d) = CPY (i/d, N, d, A); iNdirection kaydı aracılığıyla LoaD Akümülatörü

STAN (i/d) = CPY (d, A, i/d, N). iNdirection kaydı aracılığıyla Depo Akümülatörü

Bu neden bu kadar ilginç bir yaklaşım? En az iki neden:

(1) Parametresiz bir komut seti:

Schönhage bunu RAM0 komut setini üretmek için yapar. Aşağıdaki bölüme bakın.

(2) Bir RAM'i Turing Sonrası makineye azaltın:

Minimalistler gibi davranarak, akümülatör A ve dolaylı kayıt N eg r = { r0, r1, r2, ... } dışındaki tüm kayıtları sınırsız (çok) sınırlı kapasiteli güvercin delikleri dizisine indirgeriz. Bunlar (çok-) sınırlı sayıları tutmaktan başka bir şey yapmazlar, örneğin { 0, 1 } değerine sahip yalnız bir bit. Aynı şekilde akümülatörü de tek bir bite küçültüyoruz. Herhangi bir aritmetiği { A, N } kayıtlarıyla sınırlandırıyoruz, kayıtların içeriğini akümülatöre çekmek için dolaylı işlemler kullanıyoruz ve akümülatörden bir kayda 0 veya 1 yazıyoruz:

{ LDA (i, N), STA (i, N), CLR (A/N), INC (A/N), DEC(N), JZ (A/N, I _z ), JZ (I _z ), H }

"ERASE" ve "PRINT" olarak adlandırılan iki "sabit" kayıt kullanarak A'yı daha da zorlarız ve tamamen ortadan kaldırırız: [ERASE]=0, [PRINT]=1.

{ CPY (d, ERASE, i, N), CPY (d, PRINT, i, N), CLR (N), INC (N), DEC (N), JZ (i, N, I _z ), JZ ( ben _z ), H }

COPY talimatlarını yeniden adlandırın ve INC (N) = RIGHT, DEC (N) = LEFT'i arayın ve Post-Turing makinesiyle aynı talimatlara ve ayrıca fazladan bir CLRN'ye sahibiz:

{ SİL, YAZDIR, CLRN, SAĞ, SOL, JZ (i, N, I _z ), JZ (I _z ), H }

Dolaylı olarak RAM'in Turing denkliği

Yukarıdaki bölümde, resmi olmayan bir şekilde, sınırsız bir dolaylı kapasiteye sahip bir RAM'in bir Post-Turing makinesi ürettiğini gösterdik . Post-Turing makinesi Turing eşdeğeridir, dolayısıyla dolaylı RAM'in Turing eşdeğeri olduğunu gösterdik.

Burada biraz daha resmi bir gösteri yapıyoruz. Modelimizi üç ayrılmış kayıt "E", "P" ve "N" artı sağda sınırsız bir kayıt kümesi 1, 2, ..., n ile tasarlayarak başlayın. 1, 2, ..., n kayıtları "bantın kareleri" olarak kabul edilecektir. Kayıt "N", "kafanın" şu anda gözlemlediği "taranan kareye" işaret eder. "Kafa" koşullu atlamada olarak düşünülebilir – dolaylı adresleme kullandığını gözlemleyin (bkz. Elgot-Robinson s. 398). "N"yi azaltıp artırdıkça (görünür) kafa kareler boyunca "sola" veya "sağa" hareket edecektir. Dolaylı CPY'yi kullanarak "E"=0 veya "P"=1'in içeriğini N ile gösterildiği gibi "taranmış kareye" taşıyacağız.

Kasetimizin sol uçlu olması bize küçük bir sorun sunuyor: SOL olduğunda, talimatlarımız "N" içeriğinin sıfır olup olmadığını belirlemek için test etmek zorunda kalacak; öyleyse, sayısını "0" olarak bırakmalıyız (tasarımcılar olarak bu bizim seçimimizdir - örneğin, makine/modelin bizim seçtiğimiz "bir olayı tetiklemesini" sağlayabiliriz).

Komut seti 1 (arttırılmış): { INC (N), DEC (N), CLR (N), CPY (d, r _s ,i, N), JZ ( i, r, z ), HALT }

Aşağıdaki tablo, hem Turing Sonrası talimatlarını RAM eşdeğeri talimatları açısından tanımlar hem de işlevlerine bir örnek verir. r0-r5 kayıtlarının bandı boyunca başın (görünür) konumu. . . gölgeli olarak gösterilir:

Örnek: Sınırlı dolaylı, Turing eşdeğeri olmayan bir makine verir

Bu gösteri boyunca, sonlu durum makinesinin TABLOSU'ndaki talimatların sınırlı , yani sonlu olduğunu aklımızda tutmalıyız :

" Belirli bir problem tipini çözmek için bir işlemler dizisi veren yalnızca sonlu bir kurallar dizisi olmanın yanı sıra , bir algoritmanın beş önemli özelliği vardır [Sonluluk, Kesinlik, Girdi, Çıktı, Etkililik]" (italikler eklendi, Knuth s. 4 -7).

Zorluk, kayıtların açık "adları" (numaraları) olması ve makinemizin "erişmek" için her birini adıyla çağırması gerektiğinden ortaya çıkar.

CASE operatörü ile dolaylı CPY'yi ( i, q, d, φ ) oluşturacağız. Hedef kaydın adresi, "q" kaydının içeriği ile belirlenecektir; CASE operatörü bu numaranın ne olduğunu belirlediğinde, CPY bu numaraya sahip kaydın içeriğini doğrudan "φ" kaydına yatıracaktır. "y" olarak adlandıracağımız ek bir register'a ihtiyacımız olacak – bu bir up-counter işlevi görür.

Dolayısıyla, aşağıdakiler aslında dolaylı CPY'yi ( i, q, d, φ ) karşı makinemizde/modelimizde bir "donanım" tasarım değişikliği olmadan simüle edebileceğimizin yapıcı bir gösterimi veya kanıtıdır. Ancak, bu dolaylı CPY'nin sonlu durum makinesinin boyutu/kapsamı ile "sınırlı" olması nedeniyle, bu dolaylı CPY'yi kullanan bir RASP , mu özyinelemeli işlevlerin tam takımını değil, yalnızca ilkel özyinelemeli işlevleri hesaplayabilir .

CASE "operatörü", Kleene (1952) (s. 229) ve Boolos-Burgess-Jeffrey (2002) (s. 74); sonraki yazarlar onun faydasını vurgularlar. Aşağıdaki tanım Kleene'ye göredir ancak tanıdık "IF-THEN-ELSE" yapısını yansıtacak şekilde değiştirilmiştir.

CASE operatörü, "case_0" ile başlayan ve art arda "case_last" ile devam eden, hangi "durumun" karşılandığına bağlı olarak doğal bir sayıyı φ'ye "döndürür"; hiçbir durum karşılanmazsa, "varsayılan" (diğer adıyla "woops") olarak adlandırılan sayı φ'ye döndürülür (burada x bazı parametre seçimlerini belirtir, örneğin q kaydı ve r0, ... rlast dizesi):

Durumlara göre tanımlama φ ( x , y):

case_0: IF Q ₀ ( x , y) true ise SONRA φ ₀ ( x , y) ELSE
case_1: IF Q ₁ ( x , y) true ise SONRA φ ₁ ( x , y) ELSE
case_2 ile case_next_to_last: vb. . . . . . . . BAŞKA
case_last: IF Q _last ( x , y) true ise THEN φ _last ( x , y) ELSE
varsayılan: do φ _varsayılan ( x , y)

Kleene, "yüklemlerin" Q _n testi yaparken birbirini dışlayan olmasını ister – "yüklemler" çıktı için yalnızca { true, false } üreten işlevlerdir; Boolos-Burgess-Jeffrey, vakaların "kapsamlı" olması gerekliliğini ekliyor.

Hedef kaydın adresini temsil eden q kaydındaki bir sayı ile başlıyoruz. Ama bu sayı nedir? "Yüklemler", birbiri ardına denemeler yapmak için onu test edecek: JE (q, y, z) ve ardından INC (y). Numara açıkça tanımlandıktan sonra, CASE operatörü bu kaydın içeriğini doğrudan/açıkça φ'ye kopyalar:

Durumlara göre tanımlama CPY (i, q, d, φ) = _def φ (q, r0, ..., rlast, y) =

case_0: IF CLR (y), [q] - [y]=0 SONRA CPY ( r0, φ ), J (çıkış) ELSE
case_1: IF INC (y), [q] = [y]=1 SONRA CPY ( r1, φ ), J (çıkış) YANLIŞ
case_2 ile case n: IF . . . SONRA . . . BAŞKA
case_n: IF INC (y), [q] = [y]=n THEN CPY ( rn, φ ), J (çıkış) ELSE
case_n+1'den case_last'a: EĞER . . . SONRA . . . BAŞKA
case_last: IF INC (y), [q] = [y]="son" THEN CPY ( rlast, φ ), J (çıkış) ELSE
varsayılan: woops

Case_0 (y üzerindeki özyinelemenin temel adımı) şöyle görünür:

vaka_0 :

CLR(y); set kaydı y = 0
JE ( q, y, _φ0 )
J ( vaka_1 )

_φ0: CPY ( r0, φ )
J ( çıkış )

case_1: vb.

Case_n (tümevarım adımı) şöyle görünür; "n", "n+1", ..., "last"ın her örneğinin açık bir doğal sayı olması gerektiğini unutmayın:

case_n :

INC (y)
JE ( q, y, _φn )
J ( case_n+1 )

_φn: CPY ( rn, φ )
J ( çıkış )

case__n+1: vb.

Case_last, indüksiyonu durdurur ve CASE operatörünü sınırlar (ve dolayısıyla "dolaylı kopya" operatörünü sınırlar):

case_last :

INC (y)
JE ( q, y, _φson )
J ( woops )

_φson : CPY ( rlast, φ )
J ( çıkış )

woops: Bir sınır dışı girişimi nasıl ele alırız?
çıkış: vb.

VAKA sonsuza kadar devam edebilseydi, mu operatörü olurdu . Ama yapamıyor – sonlu durum makinesinin "durum kaydı" maksimum sayısına ulaştı (örn. 65365 = 11111111,11111111 ₂ ) veya tablosunda talimatlar tükendi; sonuçta sonlu bir makine.

Model örnekleri

Cook ve Reckhow'un (1973) kayıt için kayıt ("oku-değiştir-yaz") modeli

Yaygın olarak karşılaşılan Cook ve Rechkow modeli, üçlü kayıt Malzek modeline biraz benziyor (Knuth anımsatıcılarıyla yazılmış - orijinal talimatlarda TRA, Read, Print dışında anımsatıcılar yoktu).

LOAD ( C, r_d ) ; C → r_d, C herhangi bir tamsayıdır

Örnek: LOAD ( 0, 5 )kayıt 5'i temizleyecektir.

ADD ( r_s1, r_s2, r_d ) ; [r_s1] + [r_s2] → r_d, kayıtlar aynı veya farklı olabilir;

Örnek: ADD ( A, A, A )A kaydının içeriğini ikiye katlayacaktır.

SUB ( r_s1, r_s2, r_d ) ; [r_s1] - [r_s2] → r_d, kayıtlar aynı veya farklı olabilir:

Örnek: SUB ( 3, 3, 3 )kayıt 3'ü temizleyecektir.

COPY ( i, r_p, d, r_d ) ; [[r_p] ] → r_d, İşaretçi-kayıt r _{p ile} gösterilen kaynak-kayıt içeriğini hedef kaydına dolaylı olarak kopyalayın .
COPY ( d, r_s, i, r_p ) ; [r_s] → [r_p]. Kaynak Sicil içeriğini kopyalama _s işaretçi Sicil ile hedef kaydediciden işaret içine _p .
JNZ ( r, I_z ) ;[r] pozitif ise koşullu atlama; yani EĞER [r] > 0 SONRA z komutuna atlayın, aksi takdirde sırayla devam edin (Cook ve Reckhow buna şöyle der: "Xj > 0 ise kontrolü m satırına aktarın")
READ ( r_d ) ;"girişi" hedef kayıt defterine kopyalayın r _d
PRINT ( r_s ) ;r _s kaynak kaydının içeriğini "çıktı"ya kopyalayın .

Schönhage'in RAM0 ve RAM1'i (1980)

Schönhage (1980), SMM işaretçi makine modelinin eşdeğerliğini kanıtlaması için seçilen çok ilkel, atomize bir modeli tanımlar :

"Herhangi bir açık adreslemeden kaçınmak için RAM0'da z içerikli akümülatör ve mevcut içerik n (başlangıçta 0) olan ek bir adres kaydı bulunur " (s. 494)

RAM1 modeli : Schönhage, yapısının daha yaygın, kullanılabilir "ardıl" benzeri RAM biçimini oluşturmak için nasıl kullanılabileceğini gösterir (bu makalenin anımsatıcılarını kullanarak):

LDA k ; k --> A , k bir sabittir, "47" gibi açık bir sayıdır
LDA ( d, r ) ; [r] → A ; A'yı doğrudan yükle
LDA ( i, r ) ; [[r]] → A ; dolaylı olarak yük A
STA ( d, r ) ; [A] → r ; A'yı doğrudan depola
STA ( i, r ) ; [A] → [r] ; dolaylı olarak A depolamak
JEA ( r, z ) ; IF [A] = [r] then I_z else continue
INCA ; [A] + 1 --> A

RAM0 modeli : Schönhage'in RAM0 makinesinde tek bir harfle gösterilen 6 talimat vardır (6'ncı "C xxx", "sonraki parametreyi atla"yı içeriyor gibi görünmektedir. Schönhage, akümülatörü "z", "N"yi "n" vb. ile belirlemiştir. Schönhage'in anımsatıcılarından ziyade yukarıda geliştirilen anımsatıcıları kullanacağız.

(Z), CLRA: 0 → A
(A), INCA: [A] +1 → A
(N), CPYAN: [A] → N
(A), LDAA: [[A]] → A ; A noktalarının içeriği kayıt adresi; kayıt içeriğini A'ya koy
(S), STAN: [A] → [N] ; adresi kaydetmek için N noktalarının içeriği; A'nın içeriğini N ile gösterilen kayıt defterine koy
(C), JAZ ( z ): [A] = 0 then go to I_z ; tedavisinde belirsiz

Dolaylılık (i) store_A_via_N STAN ile çalışan CPYAN'dan (içeriği A'dan N'ye kopyala/aktar) ve (ii) özel dolaylı talimattan gelir LDAA ( [[A]] → [A] ).

Dipnotlar

Sonlu vs sınırsız

Sınırsız kayıt-"adres" kaydı olmayan herhangi bir tür sayaç makinesinin adıyla bir "r" kaydı belirtmesi gerektiği şeklindeki tanımsal gerçek, modelin "r"nin sonlu olmasını gerektirdiğini gösterir , ancak bu anlamda "sınırsız"dır. model, işini/işlerini yapmak için gerekli olan kayıt sayısı için herhangi bir üst sınır içermez. Örneğin, r < 83,617,563,821,029,283,746 veya r < 2^1,000,001 vb. gerekli değildir.

Böylece modelimiz, gerekirse, belirli bir hesaplamayı gerçekleştirmek için kayıt sayısını "genişletebilir". Ancak bu yapar modeli olmalı genişler ne sayı o ortalama sonlu - Doğal bir sayı ile çift taraflı olması gerekir: ω bir seçenek değildir .

Dolaylı bir adres belirten kaydın adresini sağlamak için sınırsız bir kayıt sağlayarak bu kısıtlamadan kurtulabiliriz.

Ayrıca bakınız

Dış bağlantılar

Referanslar

Birkaç istisna dışında, bu referanslar Register machine'dekilerle aynıdır .

- Goldstine, Herman H. ve von Neumann, John, "Planning and Coding of the Problems for a Electronic Computing Instrument", Rep. 1947, Institute for Advanced Study , Princeton. 92–119'da Bell, C. Gordon ve Newell, Allen (1971), Computer Structures: Readings and Example , McGraw-Hill Book Company, New York'ta yeniden basılmıştır . ISBN 0-07-004357-4 }.
George Boolos , John P. Burgess , Richard Jeffrey (2002), Hesaplanabilirlik ve Mantık: Dördüncü Baskı , Cambridge University Press, Cambridge, İngiltere. Orijinal Boolos-Jeffrey metni Burgess tarafından kapsamlı bir şekilde revize edildi: bir giriş ders kitabından daha gelişmiş. "Abaküs makinesi" modeli, Bölüm 5 Abaküs Hesaplanabilirliği'nde kapsamlı bir şekilde geliştirilmiştir ; kapsamlı bir şekilde işlenen ve karşılaştırılan üç modelden biridir - Turing makinesi (hala Boolos'un orijinal 4 demet biçiminde) ve diğer ikisini özyineleme.
Arthur Burks , Herman Goldstine , John von Neumann (1946), Bir elektronik hesaplama aracının mantıksal tasarımının ön tartışması , yeniden basıldı s. 92ff, Gordon Bell ve Allen Newell (1971), Bilgisayar Yapıları: Okumalar ve Örnekler , mcGraw-Hill Book Şirket, New York. ISBN 0-07-004357-4 .
Stephen A. Cook ve Robert A. Reckhow (1973), Zamana bağlı rastgele erişim makineleri , Journal of Computer Systems Science 7(4):354-375.
Martin Davis (1958), Hesaplanabilirlik ve Çözülemezlik , McGraw-Hill Book Company, Inc. New York.
Calvin Elgot ve Abraham Robinson (1964), Random-Access Stored-Program Machines, an Approach to Programming Languages , Journal of the Association for Computing Machinery, Cilt. 11, No. 4 (Ekim, 1964), s. 365–399.
J. Hartmanis (1971), "Rastgele Erişim Depolanan Program Makinelerinin Hesaplamalı Karmaşıklığı", Matematiksel Sistemler Teorisi 5, 3 (1971) s. 232–245.
John Hopcroft , Jeffrey Ullman (1979). Otomat Teorisine Giriş, Diller ve Hesaplama , 1. Baskı, Okuma Kitlesi: Addison-Wesley. ISBN 0-201-02988-X . "Dillerin" makine yorumu, NP-Tamlık, vb. konularına odaklanan zor bir kitap.
Stephen Kleene (1952), Metamatematiğe Giriş , North-Holland Publishing Company, Amsterdam, Hollanda. ISBN 0-7204-2103-9 .
Donald Knuth (1968), Bilgisayar Programlama Sanatı , İkinci Baskı 1973, Addison-Wesley, Reading, Massachusetts. Bkz. sayfa 462-463, burada "bağlantılı yapılarla ilgilenen yeni bir tür soyut makine veya 'otomat'ı" tanımlar.
Joachim Lambek (1961, 15 Haziran 1961'de alındı), Sonsuz Abaküs Nasıl Programlanır , Matematik Bülteni, cilt. 4, hayır. 3. Eylül 1961 sayfa 295-302. Lambek, Ek II'de "programın" resmi bir tanımını önerir. Melzak (1961) ve Kleene (1952) Metamathematics'e Giriş'e atıfta bulunur .
ZA Melzak (1961, 15 Mayıs 1961), Hesaplanabilirlik ve Hesaplamaya Gayri Resmi Bir Aritmetik Yaklaşım , Kanada Matematik Bülteni , cilt. 4, hayır. 3. Eylül 1961, sayfa 279-293. Melzak hiçbir referans sunmaz, ancak "Bell telefon Laboratuvarlarından Dr. R. Hamming, D. McIlroy ve V. Vyssots ile ve Oxford Üniversitesi'nden Dr. H. Wang ile yapılan görüşmelerin yararını" kabul eder.
Marvin Minsky (1961). "Post'un 'Etiket' Probleminin Özyinelemeli Çözülemezliği ve Turing Makineleri Teorisindeki Diğer Konular". Matematik Annals . Annals of Mathematics, Cilt. 74, No. 3. 74 (3): 437–455. doi : 10.2307/1970290 . JSTOR 1970290 .
Marvin Minsky (1967). Hesaplama: Sonlu ve Sonsuz Makineler (1. baskı). Englewood Cliffs, NJ: Prentice-Hall, Inc.Özellikle bkz. bölüm 11: Dijital Bilgisayarlara Benzer Modeller ve bölüm 14: Hesaplanabilirlik için Çok Basit Temeller . Önceki bölümde "Program makineleri"ni tanımlar ve sonraki bölümde "İki Kayıtlı Evrensel Program makineleri" ve "...tek kayıtlı" vb. konuları tartışır.
John C. Shepherdson ve HE Sturgis (1961), Aralık 1961'de Computability of Recursive Functions , Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963'ü aldı. Son derece değerli bir referans makalesi. Ek A'da yazarlar, "4.1'de Kullanılan Talimatların Asgariliği: Benzer Sistemlerle Karşılaştırma" ile ilgili 4 tane daha alıntı yapmaktadır.

Kaphengst, Heinz, Eine Abstrakte programmgesteuerte Rechenmaschine' , Zeitschrift für mathematische Logik und Grundlagen der Mathematik: 5 (1959), 366-379.
Ershov, AP On operatör algoritmaları , (Rusça) Dok. Akad. Nauk 122 (1958), 967-970. İngilizce çeviri, Otomat. Ekspres 1 (1959), 20-23.
Péter, Rózsa Graphschemata und rekursive Funktionen , Dialectica 12 (1958), 373.
Hermes, Hans Die Universalität programmgesteuerter Rechenmaschinen. Matematik.-Fizik. Semsterberichte (Göttingen) 4 (1954), 42-53.

Arnold Schönhage (1980), Depolama Modifikasyon Makineleri , Endüstriyel ve Uygulamalı Matematik Derneği, SIAM J. Comput. Cilt 9, No. 3, Ağustos 1980. Burada Schōnhage, SMM'sinin "ardıl RAM" (Rastgele Erişim Makinesi), vb. ile eşdeğerliğini gösterir. Depolama Modifikasyon Makineleri , Teorik Bilgisayar Biliminde (1979), s. 36–37
Peter van Emde Boas , "Makine Modelleri ve Simülasyonlar" s. 3-66, içinde: Jan van Leeuwen , ed. Teorik Bilgisayar Bilimi El Kitabı. Cilt A: Algoritmalar ve Karmaşıklık , MIT Press /Elsevier, 1990. ISBN 0-444-88071-2 (cilt A). QA 76.H279 1990. van Emde Boas'ın SMM'leri ele alışı, sayfa 32-35'te görülmektedir. Bu tedavi Schōnhage 1980'i netleştirir – Schōnhage tedavisini yakından takip eder, ancak biraz genişletir. Etkili bir anlayış için her iki referansa da ihtiyaç duyulabilir.
Hao Wang (1957), Turing'in Bilgi İşlem Makineleri Teorisinin Bir Varyantı , JACM ( Bilgisayar Makineleri Derneği Dergisi) 4; 63-92. Derneğin 23-25 Haziran 1954 tarihli toplantısında sunulmuştur.

anımsatıcı	etiket:		E	P	n	r0	r1	r2	r3	r4	r5	vesaire.	Kayıtlar üzerinde işlem	Sonlu durum makinesinde eylem Komut Kaydı IR

	Başlat:		0	1	3				1	0

r	sağ:	INC ( N )	0	1	4				1	0			[N] +1 → H	[IR] +1 → Kızılötesi

P	Yazdır:	CPY ( d, P, ben, N )	0	1	4				1	1			[P]=1 → [N]=r4	[IR] +1 → Kızılötesi

E	sil:	CPY ( d, E, ben, N )	0	1	4				1	0			[E]=0 → [N]=r4	[IR] +1 → Kızılötesi

L	sol:	JZ ( ben, N, son )	0	1	4				1	0			Yok	EĞER N =r4] =0 SONRA "son" → IR başka [IR]+1 → IR
		Aralık (N)	0	1	3				1	0			[N] -1 → H

J0 (dur)	jump_if_blank:	JZ ( ben, N, son )	0	1	3				1	0			Yok	IF N =r3] =0 SONRA "son" → IR başka [IR]+1 → IR

J1 (dur)	jump_if_mark:	JZ ( i, N, dur )	0	1	3				1	0			N =r3] → A	IF N =r3] =0 SONRA "son" → IR başka [IR]+1 → IR
	son	. . . vesaire.	0	1	3				1	0

	dur:	H	0	1	3				1	0			Yok	[IR] +1 → Kızılötesi

Languages

In other projects