Zarejestruj maszynę

W logice matematycznej i informatyce teoretycznej maszyna rejestrująca jest ogólną klasą maszyn abstrakcyjnych używanych w sposób podobny do maszyny Turinga . Wszystkie modele są odpowiednikami Turinga .

Przegląd

Maszyna rejestrująca swoją nazwę wzięła od użycia jednego lub większej liczby „ rejestrów ”. W przeciwieństwie do taśmy i głowicy używanej przez maszynę Turinga , model wykorzystuje wiele, jednoznacznie adresowanych rejestrów , z których każdy zawiera pojedynczą dodatnią liczbę całkowitą .

W literaturze można znaleźć co najmniej cztery podklasy, wymienione tutaj od najbardziej prymitywnych do najbardziej przypominających komputer :

Licznik – najbardziej prymitywny i zredukowany model teoretyczny sprzętu komputerowego. Brakuje adresowania pośredniego. Instrukcje znajdują się w maszynie skończonej, na wzór architektury Harvarda .
Maszyna wskaźnikowa – połączenie modeli maszyn liczących i pamięci RAM. Mniej powszechne i bardziej abstrakcyjne niż którykolwiek model. Instrukcje znajdują się w maszynie skończonej, na wzór architektury Harvarda.
Maszyna o dostępie swobodnym (RAM) – maszyna licznikowa z adresowaniem pośrednim i zwykle rozszerzonym zestawem instrukcji. Instrukcje znajdują się w maszynie skończonej, na wzór architektury Harvarda.
maszyny z programem zapisanym w pamięci o dostępie swobodnym (RASP) – pamięć RAM z instrukcjami w jej rejestrach analogiczna do uniwersalnej maszyny Turinga ; jest zatem przykładem architektury von Neumanna . Jednak w przeciwieństwie do komputera model jest idealizowany za pomocą efektywnie nieskończonych rejestrów (a jeśli są używane, faktycznie nieskończonych rejestrów specjalnych, takich jak akumulator). W porównaniu z komputerem zestaw instrukcji jest znacznie zmniejszony pod względem liczby i złożoności.

Każdy prawidłowo zdefiniowany model maszyny rejestrującej jest odpowiednikiem Turinga . Szybkość obliczeń zależy w dużym stopniu od specyfiki modelu.

W praktycznej informatyce podobna koncepcja znana jako maszyna wirtualna jest czasami używana w celu zminimalizowania zależności od podstawowej architektury maszyn. Maszyny tego typu wykorzystywane są także do celów dydaktycznych. W podręcznikach czasami używa się terminu „zarejestruj maszynę” w odniesieniu do maszyny wirtualnej.

Definicja formalna

Maszyna rejestrująca składa się z:

Nieograniczona liczba oznaczonych, dyskretnych, nieograniczonych rejestrów o nieograniczonym zasięgu (pojemności) : skończony (lub nieskończony w niektórych modelach) zbiór rejestrów, z których każdy jest uważany za ${\ displaystyle r_ {0} \ ldots r_ {n}}$ mieć nieskończony zakres i każdy z nich zawiera jedną nieujemną liczbę całkowitą (0, 1, 2, ...). Rejestry mogą wykonywać własną arytmetykę lub może istnieć jeden lub więcej specjalnych rejestrów, które wykonują tę arytmetykę, np. „akumulator” i/lub „rejestr adresowy”. Zobacz także Maszyna o dostępie swobodnym .
Liczniki lub znaki : oddzielne, nierozróżnialne przedmioty lub znaki tylko jednego rodzaju, odpowiedniego dla modelu. W najbardziej zredukowanej maszynie licznikowej modelu, podczas każdej operacji arytmetycznej tylko jeden obiekt/znak jest dodawany lub usuwany z jego lokalizacji/taśmy. W niektórych modelach maszyn liczących (np. Melzak (1961), Minsky (1961)) i większości modeli RAM i RASP więcej niż jeden obiekt/znak można dodać lub usunąć w jednej operacji z „dodawaniem” i zwykle „odejmowaniem”; czasami z „mnożeniem” i / lub „dzieleniem”. Niektóre modele posiadają operacje sterujące, takie jak „kopiuj” (różnie: „przenieś”, „ładuj”, „przechowuj”), które przesuwają „grupy” obiektów/znaków z rejestru do rejestru w jednej akcji.
(Bardzo) ograniczony zestaw instrukcji : instrukcje zwykle dzielą się na dwie klasy: arytmetyczną i sterującą. Instrukcje są pobierane z dwóch klas w celu utworzenia „zestawów instrukcji”, tak że zestaw instrukcji musi umożliwiać modelowi równoważność Turinga (musi być w stanie obliczyć dowolną częściową funkcję rekurencyjną ).
1. Arytmetyka : instrukcje arytmetyczne mogą działać na wszystkich rejestrach lub tylko na rejestrze specjalnym (np. akumulatorze). Zazwyczaj wybiera się je z następujących zestawów (ale jest wiele wyjątków):
  - Licznik: { Zwiększanie (r), Zmniejszanie (r), Zerowanie (r) }
  - Zredukowana pamięć RAM, RASP: { Zwiększanie (r), Zmniejszanie (r), Zerowanie do zera (r), Załaduj natychmiastową stałą k, Dodaj (r 1, r 2), właściwe _odejmij ( _r 1 _, r ₂ ), Zwiększ akumulator, Zmniejsz akumulator, Wyczyść akumulator, Dodaj do akumulatora zawartość rejestru r, Poprawnie-Odejmij od zawartości akumulatora rejestru r, }
  - Rozszerzona pamięć RAM, RASP: Wszystkie zredukowane instrukcje plus: {Mnożenie, dzielenie, różne wartości logiczne w bitach (przesunięcie w lewo, test bitowy itp.)}
2. Sterowanie :
  - Modele maszyn liczących: opcjonalne {Kopiuj (r ₁ , r ₂ ) }
  - Modele RAM i RASP: większość ma { Kopiuj (r ₁ , r ₂ ) } lub { Załaduj akumulator z r, Zapisz akumulator w r, Załaduj akumulator z natychmiastową stałą }
  - Wszystkie modele: co najmniej jeden „skok” warunkowy (gałąź, goto) po teście rejestru np. { Skok, jeśli-zero, Skok, jeśli nie jest zerem (tj. Skok, jeśli jest dodatni), Skok, jeśli jest równy, Skok, jeśli nie jest równy }
  - Wszystkie modele opcjonalne: { bezwarunkowy skok programu (goto) }
3. Sposób adresowania rejestrów :
  - Maszyna licząca: brak adresowania pośredniego, możliwe bezpośrednie operandy w modelach o dużym stopniu atomizacji
  - RAM i RASP: dostępne adresowanie pośrednie, typowe operandy bezpośrednie
4. Wejście-wyjście : opcjonalne we wszystkich modelach
Rejestr stanu : Specjalny Rejestr Instrukcji „IR”, skończony i odrębny od powyższych rejestrów, przechowuje aktualną instrukcję do wykonania i jej adres w TABELI instrukcji; ten rejestr i jego TABELA znajdują się w skończonej maszynie stanów.
- Podczerwień jest niedostępna dla wszystkich modeli. W przypadku RAM i RASP, w celu ustalenia „adresu” rejestru, model może wybrać albo (i) w przypadku adresowania bezpośredniego – adres określony w TABELI i tymczasowo znajdujący się w IR lub ( ii) w przypadku adresowania pośredniego – zawartość rejestru określonego instrukcją IR.
- IR nie jest „licznikiem programów” (PC) RASP (lub konwencjonalnego komputera). Komputer PC to po prostu kolejny rejestr podobny do akumulatora, ale przeznaczony do przechowywania numeru bieżącej instrukcji opartej na rejestrze RASP. Zatem RASP ma dwa rejestry „instrukcji/programu” - (i) IR (rejestr instrukcji maszyny o skończonych stanach) i (ii) komputer PC (licznik programów) dla programu znajdującego się w rejestrach. (Oprócz rejestru przeznaczonego dla „komputera PC” RASP może wyznaczyć inny rejestr dla „rejestru instrukcji programu” (o dowolnej liczbie nazw, takich jak „PIR, „IR”, „PR” itp.)
Lista instrukcji oznaczonych etykietami, zwykle $kolejności$ $I_{1}\ldots I_{m}$ : instrukcji W przypadku maszyny licznikowej, maszyny o dostępie swobodnym (RAM) i maszyny wskaźnikowej pamięć instrukcji znajduje się w „TABELI” maszyny o skończonych stanach; zatem modele te są przykładem architektury harwardzkiej. W przypadku RASP pamięć programu znajduje się w rejestrach; jest to zatem przykład architektury von Neumanna. Zobacz także Maszyna o dostępie swobodnym i Maszyna z zapisanym programem o dostępie swobodnym. Zwykle, jak programy komputerowe , instrukcje są wymienione w kolejności; chyba że skok się powiedzie, domyślna sekwencja jest kontynuowana w kolejności numerycznej. Wyjątkiem są modele liczydeł (Lambek (1961), Minsky (1961)) - każda instrukcja ma co najmniej jeden identyfikator „następnej” instrukcji „z”, a gałąź warunkowa ma dwa.
- Zauważ także, że model liczydła łączy w sobie dwie instrukcje, JZ, a następnie DEC: np. { INC ( r, z ), JZDEC ( r, z _true , z _false ) }. Więcej informacji na temat wyrażeń warunkowych można znaleźć w artykule Formalizm McCarthy'ego „JEŚLI r=0 TO z _prawda W przeciwnym razie z _fałsz ” (por. McCarthy (1960)).

Historyczny rozwój modelu maszyny rejestrującej

Na początku lat pięćdziesiątych XX wieku pojawiły się dwa nurty – pierwszy charakteryzujący komputer jako maszynę Turinga, drugi definiujący modele komputerowe – modele z sekwencyjnymi sekwencjami instrukcji i skokami warunkowymi – z mocą maszyny Turinga, czyli tzw. Równoważność Turinga. Potrzeba napisania tej pracy została podjęta w kontekście dwóch „trudnych” problemów: nierozwiązywalnego problemu słownego postawionego przez Emila Posta – jego problemu „znacznika” – i bardzo „trudnego” problemu problemów Hilberta – dziesiątego pytania dotyczącego równań diofantycznych . Badacze poszukiwali modeli równoważnych Turingowi, które byłyby mniej „logiczne” z natury, a bardziej „arytmetyczne” (por. Melzak (1961), s. 281, Shepherdson – Sturgis (1963), s. 218).

Wydaje się, że pierwszy trend – w kierunku charakteryzacji komputerów – zapoczątkował Hans Hermes (1954), Rózsa Péter (1958) i Heinz Kaphengst (1959), drugi nurt – Hao Wang (1954, 1957) i, jak zauważono powyżej, rozwinął się wraz ze Zdzisławem Aleksandrem Melzakiem (1961), Joachimem Lambkiem (1961) i Marvinem Minskim (1961, 1967).

Pięć ostatnich nazwisk zostało wyraźnie wymienionych w tej kolejności przez Jurija Matijasiewicza . Następnie dodaje:

„Maszyny rejestrowe [niektórzy autorzy używają słowa „maszyna rejestrująca” synonimicznie „maszyna przeciwna”] szczególnie nadają się do konstruowania równań diofantycznych. Podobnie jak maszyny Turinga, mają bardzo prymitywne instrukcje, a ponadto radzą sobie z liczbami” (Yuri Matiyasevich ( 1993), Dziesiąty problem Hilberta , komentarz do rozdziału 5 książki, pod adresem http://logic.pdmi.ras.ru/yumat/H10Pbook/commch_5htm .)

Wydaje się, że Lambek, Melzak, Minsky, Shepherdson i Sturgis niezależnie przewidzieli ten sam pomysł w tym samym czasie. Patrz Uwaga dotycząca pierwszeństwa poniżej.

Historia zaczyna się od modelu Wanga.

Model Wanga (1954, 1957): maszyna Post-Turinga

Praca Wanga była kontynuacją artykułu Emila Posta (1936) i doprowadziła Wanga do definicji maszyny Wanga B — dwusymbolowego modelu obliczeniowego maszyny Post-Turinga z tylko czterema instrukcjami atomowymi:

{ W LEWO, W PRAWO, DRUKUJ, SKOK_jeśli_oznaczony_do_instrukcji_z }

Do tych czterech zarówno Wang (1954, 1957), jak i CY Lee (1961) dodali kolejną instrukcję ze zbioru Post { ERASE }, a następnie bezwarunkowy skok Posta { JUMP_to_instrukcja_z } (lub dla ułatwienia skok warunkowy JUMP_IF_blank_to_instruction_z, lub oba. Lee nazwał ten model „W-machine”:

{ LEWY, PRAWY, DRUKUJ, KASUJ, SKOK_jeśli_zaznaczony, [może SKOK lub SKOK_IF_puste] }

Wang wyraził nadzieję, że jego model będzie „zbliżeniem” (s. 63) pomiędzy teorią maszyn Turinga a praktycznym światem komputera.

Praca Wanga wywarła duży wpływ. Odwołujemy się do niego Minsky (1961) i (1967), Melzak (1961), Shepherdson i Sturgis (1963). Rzeczywiście, Shepherdson i Sturgis (1963) zauważają, że:

„...próbowaliśmy pójść o krok dalej w «zbliżeniu» pomiędzy praktycznymi i teoretycznymi aspektami obliczeń sugerowanymi przez Wanga” (s. 218)

Martin Davis ostatecznie przekształcił ten model w (dwu-symbolową) maszynę Post-Turinga.

Trudności z modelem Wanga/Post-Turinga :

Tyle że pojawił się problem: model Wanga (sześć instrukcji siedmioinstrukcyjnej maszyny Post-Turinga) nadal był jednotaśmowym urządzeniem przypominającym Turinga, niezależnie od tego, jak przyjemny mógłby być jego sekwencyjny przepływ instrukcji programu . Zarówno Melzak (1961), jak i Shepherdson i Sturgis (1963) zaobserwowali to (w kontekście pewnych dowodów i badań):

„… maszyna Turinga ma pewną nieprzezroczystość… maszyna Turinga działa powoli (hipotetycznie) i zwykle jest skomplikowana. To sprawia, że raczej trudno ją zaprojektować, a jeszcze trudniej zbadać takie kwestie, jak czas czy pamięć optymalizacja lub porównanie wydajności dwóch algorytmów (Melzak (1961) s. 281)

„…choć nie jest to trudne… dowody są skomplikowane i żmudne w śledzeniu z dwóch powodów: (1) Maszyna Turinga ma tylko głowę, więc trzeba podzielić obliczenia na bardzo małe kroki operacji na jednej cyfrze (2) Ma tylko jedną taśmę, więc trzeba zadać sobie trochę trudu, aby znaleźć numer jeden, nad którym chce się pracować i oddzielić go od innych numerów” (Shepherdson i Sturgis (1963), s. 218).

Rzeczywiście, jak pokazują przykłady maszyn Turinga , maszyny Post-Turinga i funkcji częściowych , praca może być „skomplikowana”.

Modele Minsky'ego, Melzaka-Lambeka i Shepherdsona – Sturgisa „pocięły taśmę” na wiele

Dlaczego więc nie „przeciąć taśmy”, tak aby każda była nieskończenie długa (aby pomieścić dowolną liczbę całkowitą), ale z lewym końcem, i nazwać te trzy taśmy „taśmami post-turingowymi (tzn. podobnymi do Wanga)”? Poszczególne głowy będą poruszać się w lewo (w celu zmniejszenia) i w prawo (w celu zwiększenia). W pewnym sensie głowy wskazują „wierzchołki stosu” połączonych znaków. Podobnie u Minsky’ego (1961) oraz Hopcrofta i Ullmana (1979, s. 171 i nast.) taśma jest zawsze pusta, z wyjątkiem znaku na lewym końcu – w żadnym momencie głowa nie drukuje ani nie kasuje.

przed zmniejszeniem nastąpił test zera i skok, w przeciwnym razie nasza maszyna „spadnie z końca” lub „uderzy o koniec” — będziemy mieli instancję częściowego funkcja . Przed zmniejszeniem nasza maszyna musi zawsze zadać pytanie: „Czy taśma/licznik jest pusta? Jeśli tak, to nie mogę zmniejszyć, w przeciwnym razie mogę”.

Minsky (1961) i Shepherdson-Sturgis (1963) dowodzą, że tylko kilka taśm – zaledwie jedna – wciąż pozwala na to, aby maszyna była równoważna Turingowi JEŚLI dane na taśmie są reprezentowane jako liczba Gödla (lub inny numer, który można jednoznacznie zakodować i rozszyfrować); liczba ta będzie się zmieniać w miarę postępów obliczeń. W wersji na jedną taśmę z kodowaniem liczby Gödla licznik musi być w stanie (i) pomnożyć liczbę Gödla przez stałą (liczby „2” lub „3”) oraz (ii) podzielić przez stałą (liczby „2” lub „3”) i skocz, jeśli reszta wynosi zero. Minsky (1967) pokazuje, że zapotrzebowanie na ten dziwaczny zestaw instrukcji można zmniejszyć do { INC (r), JZDEC (r, z) } i wygodnych instrukcji { CLR (r), J (r) }, jeśli dostępne są dwie taśmy . Jednak nadal wymagana jest prosta gödelizacja. Podobny wynik pojawia się u Elgota-Robinsona (1964) w odniesieniu do ich modelu RASP.

Model Melzaka (1961) jest inny: grudki kamyków wchodzą i wychodzą z dziur

Model Melzaka (1961) jest znacząco odmienny. Wziął swój własny model, przerzucił taśmy w pionie, nazwał je „dziurami w ziemi”, które należy wypełnić „licznikami kamyków”. W przeciwieństwie do „przyrostu” i „ubytku” Minsky’ego, Melzak pozwalał na prawidłowe odejmowanie dowolnej liczby kamyków i „dodawanie” dowolnej liczby kamyków.

Definiuje adresowanie pośrednie dla swojego modelu (s. 288) i podaje dwa przykłady jego zastosowania (s. 89); jego „dowód” (s. 290-292), że jego model jest odpowiednikiem Turinga, jest tak pobieżny, że czytelnik nie jest w stanie stwierdzić, czy w jego intencji adresowanie pośrednie było wymogiem dowodu.

Dziedzictwem modelu Melzaka jest uproszczenie Lambeka i ponowne pojawienie się jego konwencji mnemonicznych w Cook i Reckhow 1973.

Lambek (1961) atomizuje model Melzaka do modelu Minsky'ego (1961): INC i DEC-z-testem

Lambek (1961) wziął trójskładnikowy model Melzaka i rozdrobnił go do dwóch instrukcji jednoargumentowych – X+, X-, jeśli to możliwe, jeszcze skok – dokładnie tych samych dwóch, które wymyślił Minsky (1961).

Jednakże, podobnie jak model Minsky'ego (1961), model Lambeka faktycznie wykonuje swoje instrukcje w sposób domyślny - zarówno X+, jak i X- niosą identyfikator następnej instrukcji, a X- przenosi także instrukcję skoku, jeśli zero -test zakończył się sukcesem.

Elgot-Robinson (1964) i problem RASP bez adresowania pośredniego

Maszyna RASP, czyli maszyna z programem zapisanym w pamięci o dostępie swobodnym, zaczyna jako maszyna licznikowa z „programem instrukcji” umieszczonym w jej „rejestrach”. Analogicznie, ale niezależnie od „rejestru instrukcji” maszyny o skończonych stanach, co najmniej jeden z rejestrów (nazywany „licznikiem programu” (PC)) i jeden lub więcej rejestrów „tymczasowych” przechowują zapis i działają na nim, numer aktualnej instrukcji. TABELA instrukcji maszyny skończonej odpowiada za (i) pobranie aktualnej programu z odpowiedniego rejestru, (ii) parsowanie programu instrukcji, (iii) pobieranie argumentów określonych w instrukcji programu oraz (iv) wykonywanie instrukcji programu .

Tyle że pojawia się problem: jeśli maszyna von Neumanna będzie oparta na obudowie maszyny liczącej , przypominającej komputer, nie będzie ona odpowiednikiem Turinga. Nie da się obliczyć wszystkiego, co da się obliczyć. Z natury model jest ograniczony rozmiarem (bardzo) instrukcji maszyny skończonej . RASP oparty na maszynie liczącej może obliczyć dowolną pierwotną funkcję rekurencyjną (np. mnożenie), ale nie wszystkie funkcje rekurencyjne mu (np. funkcję Ackermanna ).

Elgot-Robinson bada możliwość umożliwienia swojemu modelowi RASP „samodzielnej modyfikacji” instrukcji programu. Pomysł był stary, zaproponowany przez Burksa-Goldstine'a-von Neumanna (1946-7) i czasami nazywany „obliczonym goto”. Melzak (1961) wyraźnie wymienia „obliczone goto” z nazwy, ale zamiast tego zapewnia swojemu modelowi adresowanie pośrednie.

Obliczone goto: Program instrukcji RASP , który modyfikuje „adres goto” w instrukcji programu skoku warunkowego lub bezwarunkowego .

Ale to nie rozwiązuje problemu (chyba że odwołamy się do liczb Gödla ). Konieczna jest metoda pobrania adresu instrukcji programu, która leży (daleko) „poza/powyżej” górnej granicy rejestru instrukcji maszyny skończonej i TABELI.

Przykład: Licznik wyposażony tylko w cztery nieograniczone rejestry może np. pomnożyć dowolne dwie liczby ( m, n ) przez siebie, aby otrzymać p – a zatem być pierwotną funkcją rekurencyjną – niezależnie od tego, jak duże są liczby m i n; co więcej, aby to zrobić, potrzeba mniej niż 20 instrukcji! np. { 1: CLR ( p ), 2: JZ ( m, gotowe ), 3 pętla zewnętrzna: JZ ( n, gotowe ), 4: CPY ( m, temp ), 5: pętla wewnętrzna: JZ ( m, pętla zewnętrzna ), 6: DEC ( m ), 7: INC ( p ), 8: J ( wewnętrzna pętla ), 9: zewnętrzna pętla: DEC ( n ), 10 J ( zewnętrzna pętla ), HALT } Jednak przy tylko 4 rejestrach ta maszyna nie jest wystarczająco

duża zbudować RASP, który może wykonać algorytm mnożenia jako program . Bez względu na to, jak dużą zbudujemy naszą maszynę o skończonych stanach, zawsze będzie program ( łącznie z jego parametrami), który będzie większy. Zatem z definicji maszyna z ograniczonym programem, która nie używa nieograniczonych sztuczek kodowania, takich jak liczby Gödla, nie może być uniwersalna .

Minsky (1967) wskazuje na tę kwestię podczas swoich badań nad maszyną licznikową (nazywa je „modelami komputerów programowych”) wyposażonych w instrukcje {CLR (r), INC (r) i RPT („a” razy instrukcje m do n)}. Nie mówi nam, jak rozwiązać problem, ale zauważa, że:

„...komputer programu musi mieć jakiś sposób na śledzenie liczby operacji RPT pozostałych do wykonania, a to może wyczerpać dowolną ilość pamięci dozwoloną w skończonej części komputera. Operacje RPT wymagają własnych, nieskończonych rejestrów ogólnie rzecz biorąc, i należy je traktować inaczej niż inne rodzaje operacji, które rozważaliśmy.” (s. 214)

₀₀₀₀ Ale Elgot i Robinson rozwiązują problem: rozszerzają swój P RASP o indeksowany zestaw instrukcji — nieco bardziej skomplikowaną (ale bardziej elastyczną) formą adresowania pośredniego. Ich model P' adresuje rejestry, dodając zawartość rejestru „bazowego” (określonego w instrukcji) do „indeksu” określonego wyraźnie w instrukcji (lub odwrotnie, zamieniając „bazę” i „indeks”). Zatem instrukcje indeksujące P' mają o jeden parametr więcej niż instrukcje P nieindeksujące :

Przykład: INC ( r _podstawa , indeks ) ; efektywnym adresem będzie [r _podstawa ] + indeks, gdzie „indeks” liczby naturalnej jest wyprowadzany z samej instrukcji maszyny skończonej.

Hartmanisa (1971)

Do 1971 roku Hartmanis uprościł indeksowanie do pośredniego na potrzeby swojego modelu RASP.

Adresowanie pośrednie: Rejestr wskaźników dostarcza maszynie skończonej adres rejestru docelowego wymaganego dla instrukcji. Mówiąc inaczej: zawartość rejestru wskaźników jest adresem rejestru „docelowego”, który ma być używany przez instrukcję. Jeśli rejestr wskaźników jest nieograniczony, pamięć RAM i odpowiedni RASP wbudowany w jej obudowę będą odpowiednikami Turinga. Rejestr docelowy może służyć albo jako rejestr źródłowy, albo docelowy, zgodnie z instrukcją.

Należy zauważyć, że maszyna skończona nie musi jawnie określać adresu tego rejestru docelowego. Po prostu mówi do reszty maszyny: Podaj mi zawartość rejestru wskazywanego przez mój rejestr-wskaźnik, a następnie wykonaj z nim xyz. Musi wyraźnie podać nazwę, poprzez swoją instrukcję, ten rejestr wskaźników (np. „N”, „72” lub „PC” itp.), ale nie musi wiedzieć, jaki numer faktycznie zawiera ten rejestr wskaźników ( być może 279 431).

Cook i Reckhow (1973) opisują pamięć RAM

Cook i Reckhow (1973) cytują Hartmanisa (1971) i upraszczają jego model do czegoś, co nazywają maszyną o dostępie swobodnym (RAM – tj. maszyną pośrednią i architekturą Harvardu). W pewnym sensie wracamy do Melzaka (1961), ale z dużo prostszym modelem niż Melzak.

Precedens

Minsky pracował w Lincoln Laboratory MIT i tam publikował swoje prace; jego artykuł wpłynął do publikacji w Annals of Mathematics 15 sierpnia 1960 r., ale został opublikowany dopiero w listopadzie 1961 r. Chociaż odbiór nastąpił na cały rok przed otrzymaniem i publikacją pracy Melzaka i Lambka (nadeszły odpowiednio 15 maja i 15 czerwca) , 1961 i opublikowane równolegle we wrześniu 1961). Że (i) obaj byli Kanadyjczykami i opublikowano je w Canadian Mathematical Bulletin , (ii) żaden z nich nie odniósłby się do pracy Minsky'ego, ponieważ nie została ona jeszcze opublikowana w recenzowanym czasopiśmie, ale (iii) Melzak odwołuje się do Wanga, a Lambek do Melzaka, prowadzi do hipotezy, że ich prace powstały jednocześnie i niezależnie.

Prawie dokładnie to samo przydarzyło się Shepherdsonowi i Sturgisowi. Ich artykuł wpłynął w grudniu 1961 r. – zaledwie kilka miesięcy po otrzymaniu pracy Melzaka i Lambka. Ponownie, mieli niewielką (maksymalnie 1 miesiąc) korzyść z recenzowania pracy Minsky'ego. Uważnie zaobserwowali w przypisach, że artykuły Erszowa, Kaphengsta i Petera „niedawno ukazały się” (s. 219). Zostały one opublikowane znacznie wcześniej, ale ukazały się w języku niemieckim w niemieckich czasopismach, więc pojawiły się problemy z dostępnością.

Ostatnia praca Shepherdsona i Sturgisa ukazała się w recenzowanym czasopiśmie dopiero w 1963 r. Jak uczciwie i uczciwie odnotowują w swoim Dodatku A, „systemy” Kaphengsta (1959), Ershova (1958), Petera (1958) wszystkie są tak podobne do wyników uzyskanych później, że nie można ich odróżnić od zestawu następujących elementów:

wygeneruj 0, czyli 0 → n,

zwiększ liczbę, tj. n+1 → n

„tj. wykonaj operacje generujące liczby naturalne” (s. 246)

skopiuj liczbę, tj. n → m

, aby „zmienić przebieg obliczeń”, albo porównywanie dwóch liczb lub zmniejszanie do 0

Rzeczywiście, podsumowują Shepherson i Sturgis

„Różne systemy minimalne są bardzo podobne” ( str. 246)

Według daty publikacji na pierwszym miejscu znalazły się prace Kaphengsta (1959), Ershova (1958), Petera (1958).

Zobacz też

Bibliografia

Teksty uzupełniające: Poniższa bibliografia artykułów źródłowych zawiera pewną liczbę tekstów, które można wykorzystać jako tło. Matematykę, która doprowadziła do lawiny artykułów na temat abstrakcyjnych maszyn w latach pięćdziesiątych i sześćdziesiątych XX wieku, można znaleźć w van Heijenoorcie (1967) – zbiorze oryginalnych prac obejmujących okres 50 lat od Fregego (1879) do Gödla (1931). Davis (red.) The Undecidable (1965) niesie pochodnię dalej, począwszy od Gödla (1931) poprzez postscriptum Gödla (1964) (s. 71); oryginalne artykuły Alana Turinga (1936-7) i Emila Posta (1936) znajdują się w The Undecidable . Matematyka Churcha, Rossera i Kleene’a, która pojawia się jako przedruki oryginalnych artykułów w The Undecidable , jest kontynuowana w Kleene (1952), tekście obowiązkowym dla każdego, kto pragnie głębszego zrozumienia matematyki stojącej za maszynami. W wielu artykułach odwołuje się zarówno do Kleene’a (1952), jak i Davisa (1958).

Dobre omówienie maszyny liczącej można znaleźć w rozdziale 11 Minsky'ego (1967) „Modele podobne do komputerów cyfrowych” - nazywa on maszynę liczącą „komputerem programowym”. Niedawny przegląd można znaleźć w: van Emde Boas (1990). Niedawne opracowanie modelu Minsky'ego (1961)/Lambeka (1961) można znaleźć w Boolos-Burgess-Jeffrey (2002); reinkarnują „model liczydła” Lambeka, aby zademonstrować równoważność maszyn Turinga i częściowych funkcji rekurencyjnych, a także stanowią wprowadzenie na poziomie magisterskim zarówno do abstrakcyjnych modeli maszyn (przeciwnika i Turinga), jak i matematyki teorii rekurencji. Począwszy od pierwszego wydania Boolos-Burgess (1970) model ten pojawiał się w praktycznie takim samym wydaniu.

Artykuły : Artykuły rozpoczynają się od Wanga (1957) i jego dramatycznego uproszczenia maszyny Turinga. Turing (1936), Kleene (1952), Davis (1958), a zwłaszcza Post (1936) są cytowani w: Wang (1957); z kolei do Wanga odwołują się Melzak (1961), Minsky (1961) i Shepherdson – Sturgis (1961-3), ponieważ niezależnie redukują taśmy Turinga do „liczników”. Melzak (1961) zapewnia swojemu modelowi maszyny liczącej kamyki w otworach pośrednio, ale nie posuwa się dalej w leczeniu. Prace Elgota-Robinsona (1964) zdefiniowały RASP – podobne do komputera maszyny z zapisanym programem o swobodnym dostępie – i wydają się być pierwszymi, które zbadały awarię ograniczonego maszyna licząca do obliczania funkcji mu-rekurencyjnych. Ta porażka – z wyjątkiem drakońskiego użycia liczb Gödla na sposób Minsky'ego (1961)) - prowadzi do zdefiniowania przez nich instrukcji „indeksowanych” (tj. adresowania pośredniego) dla ich modelu RASP. Elgot-Robinson (1964), a bardziej Hartmanis (1971) badają RASP za pomocą samomodyfikujących się programów. Hartmanis (1971) określa zestaw instrukcji w sposób pośredni, cytując notatki z wykładów Cooka (1970). Na potrzeby badań złożoności obliczeniowej Cook i jego student Reckhow (1973) podają definicję pamięci RAM (ich model i konwencja mnemoniczna są podobne do modelu Melzaka, ale nie podają mu żadnego odniesienia w artykule). Maszyny wskaźnikowe są odgałęzieniem Knutha (1968, 1973) i niezależnie Schönhage (1980).

W większości artykuły obejmują matematykę wykraczającą poza poziom licencjacki – w szczególności prymitywne funkcje rekurencyjne i funkcje rekurencyjne mu , elegancko przedstawione przez Kleene (1952) i mniej szczegółowe, ale mimo to przydatne w Boolos-Burgess-Jeffrey (2002).

Wszystkie teksty i artykuły z wyjątkiem czterech oznaczonych gwiazdką zostały poświadczone. Te cztery są napisane w języku niemieckim i pojawiają się jako odniesienia w Shepherdson – Sturgis (1963) i Elgot – Robinson (1964); Shepherdson-Sturgis (1963) przedstawia krótką dyskusję na temat ich wyników w Dodatku A Shepherdsona-Sturgisa. Terminologia co najmniej jednego artykułu (Kaphengst (1959) wydaje się nawiązywać do Burke-Goldstine-von Neumanna (1946-7) analiza architektury komputera.

Autor	Rok	Maszyna licząca	Baran	Adresowanie pośrednie	Program samomodyfikujący się
Goldstine’a i von Neumanna	1947
Kleene	1952
*Hermes	1954, 5	?
Wanga	1957	poradnik		poradnik
*Piotr	1958	?
Davisa	1958
*Erszow	1959	?
*Kaphengst	1959	?
Melzak	1961				poradnik
Lambek	1961
Minski	1961
Shepherdsona i Sturgisa	1963			poradnik
Elgota i Robinsona	1964
Davis – Nierozstrzygnięty	1965
van Heijenoorta	1967
Minski	1967		poradnik	poradnik
Knutha	1968, 73
Hartmanisa	1971
Cooka i Reckhow	1973
Schönhage	1980
van Emde Boasa	1990
Boolos i Burgess; Boolos, Burgess i Jeffrey	1970–2002

Notatki

Źródła

George Boolos , John P. Burgess , Richard Jeffrey (2002), Obliczalność i logika: wydanie czwarte , Cambridge University Press, Cambridge, Anglia. Oryginalny tekst Boolosa-Jeffreya został gruntownie poprawiony przez Burgessa: bardziej zaawansowany niż podręcznik wprowadzający. Model „maszyny liczydła” został szczegółowo rozwinięty w rozdziale 5 Obliczalność liczydła ; jest to jeden z trzech szeroko omawianych i porównywanych modeli — maszyna Turinga (nadal w oryginalnej czterokrotkowej formie Boolosa) i dwa pozostałe modele rekurencji.
Arthur Burks , Herman Goldstine , John von Neumann (1946), „Wstępna dyskusja na temat logicznego projektu elektronicznego instrumentu obliczeniowego”, przedruk s. 92 i nast. w Gordon Bell i Allen Newell (1971), Computer Structures: Readings and Przykłady , McGraw- Hill Book Company, Nowy Jork. ISBN 0-07-004357-4 .
Stephen A. Cook i Robert A. Reckhow (1972), Maszyny o dostępie ograniczonym czasowo , Journal of Computer Systems Science 7 (1973), 354–375.
Martin Davis (1958), Obliczalność i nierozwiązywalność , McGraw-Hill Book Company, Inc. Nowy Jork.
Calvin Elgot i Abraham Robinson (1964), „Maszyny z programami przechowywanymi o dostępie swobodnym, podejście do języków programowania”, Journal of Association for Computing Machinery , tom. 11, nr 4 (październik 1964), s. 365–399.
J. Hartmanis (1971), „Złożoność obliczeniowa maszyn z programami przechowywanymi o dostępie swobodnym”, Mathematical Systems Theory 5, 3 (1971), s. 232–245.
Johna Hopcrofta i Jeffreya Ullmana (1979). Wprowadzenie do teorii automatów, języków i obliczeń , wyd. 1, Msza czytelnicza: Addison-Wesley. ISBN 0-201-02988-X . Trudna książka skupiona wokół zagadnień maszynowej interpretacji „języków”, NP-zupełności itp.
Stephen Kleene (1952), Wprowadzenie do metamatematyki , North-Holland Publishing Company, Amsterdam, Holandia. ISBN 0-7204-2103-9 .
Donald Knuth (1968), Sztuka programowania komputerowego , wydanie drugie 1973, Addison-Wesley, Reading, Massachusetts. Por. strony 462-463, gdzie definiuje on „nowy rodzaj abstrakcyjnej maszyny lub «automatu», który zajmuje się połączonymi strukturami”.
Lambek, Joachim (wrzesień 1961). „Jak zaprogramować nieskończone liczydło” . Kanadyjski Biuletyn Matematyczny . 4 (3): 295–302. doi : 10.4153/CMB-1961-032-6 . Manuskrypt wpłynął do pisma 15 czerwca 1961 r. W swoim Załączniku II Lambek proponuje „formalną definicję «programu». Odwołuje się do Melzaka (1961) i Kleene (1952) Wprowadzenie do metamatematyki .
Melzak, ZA (wrzesień 1961). „Nieformalne podejście arytmetyczne do obliczalności i obliczeń” . Kanadyjski Biuletyn Matematyczny . 4 (3): 279–293. doi : 10.4153/CMB-1961-031-9 . Manuskrypt wpłynął do czasopisma 15 maja 1961 roku. Melzak nie podaje żadnych odnośników, ale przyznaje, że „korzyści płyną z rozmów z doktorami R. Hammingiem, D. McIlroyem i V. Vyssotsem z Bell Phone Laborators oraz z dr H. Wangiem Uniwersytetu Oksfordzkiego.”
Minsky, Marvin (1961). „Rekurencyjna nierozwiązywalność problemu Postu dotyczącego„ znacznika ”i inne tematy w teorii maszyn Turinga”. Roczniki matematyki . 74 (3): 437–455. doi : 10.2307/1970290 . JSTOR 1970290 .
Minsky, Marvin (1967). Obliczenia: maszyny skończone i nieskończone (wyd. 1). Englewood Cliffs, New Jersey: Prentice-Hall, Inc. W szczególności zobacz rozdział 11: Modele podobne do komputerów cyfrowych i rozdział 14: Bardzo proste podstawy obliczalności . W pierwszym rozdziale definiuje „maszyny programowe”, a w kolejnym omawia „maszyny programowe uniwersalne z dwoma rejestrami” i „...z jednym rejestrem” itp.
John C. Shepherdson i HE Sturgis (1961) otrzymali w grudniu 1961 r. „Computability of Recursive Functions”, Journal of Association of Computing Machinery (JACM) 10:217-255, 1963. Niezwykle cenny artykuł referencyjny. W swoim Dodatku A autorzy cytują 4 inne w odniesieniu do „Minimalność instrukcji używanych w 4.1: Porównanie z podobnymi systemami”.
Kaphengst, Heinz, „Eine Abstrakte programmgesteuerte Rechenmaschine”, Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (1959), 366–379.
Ershov, AP „O algorytmach operatorskich”, (rosyjski) Dok. Akad. Nauk 122 (1958), 967-970. Tłumaczenie na język angielski, automat. Ekspres 1 (1959), 20-23.
Péter, Rózsa „Graphschemata und rekursive Funktionen”, Dialectica 12 (1958), 373.
Hermes, Hans „Die Universalität programmgesteuerter Rechenmaschinen”. Matematyka-Fiz. Semesterberichte (Göttingen) 4 (1954), 42-53.
Arnold Schönhage (1980), Maszyny do modyfikacji pamięci masowej , Towarzystwo Matematyki Przemysłowej i Stosowanej, SIAM J. Comput. Tom. 9, nr 3, sierpień 1980. W którym Schōnhage pokazuje równoważność swojego SMM z „następczą pamięcią RAM” (maszyną o dostępie swobodnym) itp. odpowiednio. Maszyny do modyfikacji pamięci masowej , w: Informatyka teoretyczna (1979), s. 36–37
Peter van Emde Boas , „Modele maszyn i symulacje” s. 3–66, w: Jan van Leeuwen , wyd. Podręcznik informatyki teoretycznej . Tom A: Algorytmy i złożoność , The MIT PRESS/Elsevier, 1990. ISBN 0-444-88071-2 (tom A). QA 76.H279 1990. Sposób leczenia SMM przez van Emde Boasa pojawia się na s. 32–35. To leczenie wyjaśnia Schōnhage 1980 - jest ściśle zgodne z leczeniem Schōnhage, ale nieznacznie je rozszerza. Do skutecznego zrozumienia mogą być potrzebne oba odniesienia.
Hao Wang (1957), „Odmiana teorii maszyn liczących Turinga”, JACM ( Journal of Association for Computing Machinery ) 4; 63–92. Zaprezentowany na posiedzeniu Stowarzyszenia w dniach 23–25 czerwca 1954 r.

Wolfram, Stephen (2002). Nowy rodzaj nauki . Wolfram Media, Inc., s. 97-102 . ISBN 1-57955-008-8 .

Linki zewnętrzne