Maszyna licznikowa

Licznik to abstrakcyjna maszyna używana w logice formalnej i informatyce teoretycznej do modelowania obliczeń . Jest to najbardziej prymitywny z czterech rodzajów maszyn rejestrujących . Maszyna licząca składa się z zestawu jednego lub większej liczby nieograniczonych rejestrów , z których każdy może przechowywać jedną nieujemną liczbę całkowitą, oraz listę (zwykle sekwencyjnych) instrukcji arytmetycznych i sterujących, które maszyna ma wykonać. Licznik jest zwykle wykorzystywany w procesie projektowania algorytmów równoległych w odniesieniu do zasady wzajemnego wykluczania. Używana w ten sposób maszyna licznika służy do modelowania dyskretnych kroków czasowych systemu obliczeniowego w odniesieniu do dostępów do pamięci. Poprzez modelowanie obliczeń w odniesieniu do dostępów do pamięci dla każdego odpowiedniego kroku obliczeniowego, algorytmy równoległe mogą być zaprojektowane w taki sposób, aby uniknąć blokowania, jednoczesnej operacji zapisu przez dwa (lub więcej) wątki do tego samego adresu pamięci.

Podstawowe funkcje

Dla danego modelu licznika zestaw instrukcji jest niewielki — od jednej do sześciu lub siedmiu instrukcji. Większość modeli zawiera kilka operacji arytmetycznych i co najmniej jedną operację warunkową (jeśli warunek jest prawdziwy, wykonaj skok). Z poniższej kolekcji wylosowano trzy modele podstawowe , z których każdy używa trzech instrukcji. (Skróty są dowolne.)

  • CLR (r): KASUJ rejestr r . (Ustaw r na zero.)
  • INC (r): ZWIĘKSZ zawartość rejestru r .
  • DEC (r): ZMNIEJSZ zawartość rejestru r .
  • rk ( r j , rk ) : Skopiuj zawartość rejestru r j do rejestru pozostawiając zawartość r j nienaruszoną.
  • JZ (r, z): JEŚLI rejestr r zawiera zero TO skocz do instrukcji z ELSE kontynuuj sekwencyjnie.
  • JE (r j , r k , z): JEŚLI zawartość rejestru r j jest równa zawartości rejestru r k TO skocz do instrukcji z ELSE kontynuuj sekwencyjnie.

Ponadto maszyna zwykle ma instrukcję HALT, która zatrzymuje maszynę (zwykle po obliczeniu wyniku).

Korzystając z instrukcji wspomnianych powyżej, różni autorzy omówili pewne maszyny licznikowe:

  • zestaw 1: {INC (r), DEC (r), JZ (r, z)}, (Minsky (1961, 1967), Lambek (1961))
  • zestaw 2: { CLR (r), INC (r), JE (r j , rk , z)}, (Ershov (1958), Peter (1958) w interpretacji Shepherdsona-Sturgisa (1964); Minsky (1967) ; Schönhage (1980))
  • zestaw 3: {INC (r), CPY (rj , rk ) , JE (rj , rk , z)}, (Elgot-Robinson (1964), Minsky (1967))

Trzy podstawowe modele licznika mają taką samą moc obliczeniową, ponieważ instrukcje jednego modelu można wyprowadzić z instrukcji drugiego. Wszystkie odpowiadają mocy obliczeniowej maszyn Turinga . Ze względu na ich jednoargumentowy styl przetwarzania, liczniki są zwykle wykładniczo wolniejsze niż porównywalne maszyny Turinga.

Alternatywne nazwy, alternatywne modele

Główny artykuł: Model przeciw-maszyny

liczników mają wiele różnych nazw, które mogą pomóc w ich odróżnieniu na podstawie ich cech szczególnych . Poniżej instrukcja "JZDEC ( r )" jest instrukcją złożoną, która sprawdza, czy rejestr r jest pusty; jeśli tak, to przejdź do instrukcji I z , jeśli nie, to ZMNIEJSZ zawartość r:

  • Maszyna Shepherdsona-Sturgisa , ponieważ autorzy ci formalnie przedstawili swój model w łatwo dostępnej prezentacji (1963). Wykorzystuje zestaw instrukcji (1) rozszerzony o dodatkowe wygodne instrukcje (JNZ to „Jump if Not Zero, używany zamiast JZ):
    { INC ( r ), DEC ( r ), CLR ( r ), CPY ( r j , r k ), JNZ ( r, z ), J ( z ) }
  • Maszyna Minsky'ego , ponieważ Marvin Minsky (1961) sformalizował model. Zwykle używa zestawu instrukcji (1), ale wykonanie instrukcji nie jest domyślnie sekwencyjne, więc dodatkowy parametr „z” wydaje się określać następną instrukcję po INC i jako alternatywę w JZDEC: {
    INC ( r, z ), JZDEC ( r , z prawda , z fałsz ) }
  • Zaprogramuj maszynę , zaprogramuj komputer , nazwy nadał modelowi Minsky (1967), ponieważ podobnie jak komputer jego instrukcje postępują sekwencyjnie, chyba że skok warunkowy się powiedzie. Wykorzystuje (zwykle) zestaw instrukcji (1), ale można go rozszerzyć podobnie do modelu Shephersona-Sturgisa. JZDEC jest często dzielony:
    { INC ( r ), DEC ( r ), JZ ( r, z prawda )}
  • Abacus machine , nazwę Lambek (1961) nadał swojemu uproszczeniu modelu Melzaka (1961) i temu, co nazywa go Boolos-Burgess-Jeffrey (2002). Używa zestawu instrukcji (1), ale z dodatkowym parametrem z, aby określić następną instrukcję w sposób zgodny z modelem Minsky'ego (1961);
    { INC ( r, z ), JZDEC (r, z prawda , z fałsz ) }
  • Maszyna Lambek , alternatywna nazwa, którą Boolos-Burgess-Jeffrey (2002) nadał maszynie liczącej. Używa zestawu instrukcji (1-reduced) z dodatkowym parametrem do określenia następnej instrukcji:
    { INC ( r, z ), JZDEC ( r, z true , z false ) }
  • Maszyna następcza , ponieważ wykorzystuje „operację następcy” i bardzo przypomina aksjomaty Peano. Używany jako podstawa dla następcy modelu RAM . Używa zestawu instrukcji (2) np. Schönhage'a jako podstawy dla jego modeli RAM0 i RAM1, które prowadzą do jego maszyny wskaźnikowej , również krótko omówionego w van Emde Boas (1990):
    { CLR ( r ), INC ( r ), JE ( r jo , r k , z ) }
  • Model Elgota-Robinsona , użyty do zdefiniowania ich modelu RASP (1964). Model ten wymaga na starcie jednego pustego rejestru (np. [r0] =0). (Rozbudowali ten sam model o adresowanie pośrednie za pomocą dodatkowego rejestru, który ma być używany jako rejestr „indeksowy”)
    {INC (r), CPY ( r s , r d ), JE ( r j , rk , z ) }
  • Inne maszyny liczące : Minsky (1967) demonstruje, jak zbudować trzy podstawowe modele (program/Minsky/Lambek-abacus, następca i Elgot-Robinson) z nadzbioru dostępnych instrukcji opisanych w pierwszym akapicie tego artykułu. Model Melzaka (1961) różni się od powyższego, ponieważ obejmuje „dodawanie” i „odejmowanie”, a nie „przyrost” i „zmniejszenie”. Dowody Minsky'ego (1961, 1967), że jeden rejestr wystarczy dla równoważności Turinga, wymagają dwóch instrukcji { MULTiply k i DIV k } do kodowania i dekodowania liczby Gödla w rejestrze reprezentującym obliczenia. Minsky pokazuje, że jeśli dostępne są dwa lub więcej rejestrów, wówczas odpowiednie są prostsze INC, DEC itp. (Ale liczba Gödla jest nadal wymagana do wykazania równoważności Turinga ; wykazano również w Elgot-Robinson 1964).

Definicja formalna

Licznik składa się z:

  1. 0 Oznakowane nieograniczone rejestry o wartościach całkowitych : skończony (lub nieskończony w niektórych modelach) zestaw rejestrów r ... r n , z których każdy może przechowywać dowolną nieujemną liczbę całkowitą (0, 1, 2, ... - tj. nieograniczony) . Rejestry wykonują własne działania arytmetyczne; może istnieć jeden lub więcej rejestrów specjalnych, np. „akumulator”, ale nie musi ( więcej informacji na ten temat można znaleźć w maszynie o swobodnym dostępie ).
  2. Rejestr stanu , który przechowuje/identyfikuje bieżącą instrukcję do wykonania. Ten rejestr jest skończony i oddzielny od powyższych rejestrów; zatem model licznika jest przykładem architektury Harvardu
  3. 0 Lista oznaczonych instrukcji sekwencyjnych : Skończona lista instrukcji I ... I m . Magazyn programu (instrukcje maszyny stanów skończonych ) nie znajduje się w tej samej fizycznej „przestrzeni” co rejestry. Zwykle, ale nie zawsze, podobnie jak programy komputerowe , instrukcje są wymienione w kolejności; chyba że skok się powiedzie, domyślna sekwencja jest kontynuowana w porządku numerycznym. Każda z instrukcji na liście pochodzi z (bardzo) małego zestawu, ale ten zestaw nie zawiera pośredniości. Historycznie większość modeli czerpała instrukcje z tego zestawu:
{ Zwiększ (r), Zmniejsz (r), Wyczyść (r); Kopiuj (r j , r k ), skok warunkowy, jeśli zawartość r=0, skok warunkowy, jeśli r j = r k , skok bezwarunkowy, HALT }
Niektóre modele albo jeszcze bardziej rozproszyły niektóre z powyższych instrukcji w instrukcje bez parametrów, albo połączyły je w pojedynczą instrukcję, taką jak „Decrement” poprzedzoną warunkowym jump-if-zero „JZ ( r, z )” . Atomizacja instrukcji lub włączenie instrukcji wygodnych nie powoduje zmiany mocy koncepcyjnej, ponieważ każdy program w jednym wariancie można bezpośrednio przetłumaczyć na inny.
Alternatywne zestawy instrukcji są omówione w dodatku Register-machine models .

Przykład: SKOPIUJ licznik z rejestru #2 do #3

Ten przykład pokazuje, jak utworzyć trzy bardziej przydatne instrukcje: clear , bezwarunkowy skok i copy .

Następnie r s będzie zawierało swoją pierwotną liczbę (w przeciwieństwie do MOVE, które opróżnia rejestr źródłowy, tj. czyści go do zera).

Zestaw podstawowy (1) jest używany zgodnie z definicją tutaj:

Instrukcja Wpływ na rejestr „j” Wpływ na rejestr licznika instrukcji ICR Streszczenie
INC ( j ) [j] +1 → j [IC] +1 → IC Zwiększ zawartość rejestru j; następna instrukcja
grudzień ( j ) [j] -1 → j [IC] +1 → IC Zmniejsz zawartość rejestru j; następna instrukcja
JZ (j, z) JEŻELI [j] = 0 TO I z → IC W PRZECIWNYM PRZYPADKU [IC] +1 → IC Jeżeli zawartość rejestru j=0 to instrukcja z, w przeciwnym razie następna instrukcja
POSTÓJ

Warunki początkowe

Początkowo rejestr nr 2 zawiera „2”. Rejestry #0, #1 i #3 są puste (zawierają „0”). Rejestr #0 pozostaje niezmieniony przez cały czas obliczeń, ponieważ jest używany do skoku bezwarunkowego. Rejestr nr 1 to notatnik. Program rozpoczyna się instrukcją 1.

Warunki końcowe

Program ZATRZYMUJE się z zawartością rejestru nr 2 według pierwotnego stanu i zawartością rejestru nr 3 równą oryginalnej zawartości rejestru nr 2, tj.

[2] = [3].

Opis programu na wysokim poziomie

Program COPY (#2, #3) składa się z dwóch części. W pierwszej części program przenosi zawartość rejestru źródłowego nr 2 zarówno do notatnika nr 1, jak i do rejestru docelowego nr 3; w ten sposób #1 i #3 będą kopiami siebie nawzajem i oryginalnej liczby w #2, ale #2 jest usuwane w procesie zmniejszania go do zera. Skoki bezwarunkowe J(z) wykonywane są testami rejestru #0, który zawsze zawiera liczbę 0:

[#2] →#3; [#2] →#1; 0 →#2

W drugiej części program przenosi (zwraca, przywraca) zawartość zdrapki #1 z powrotem do #2, czyszcząc zdrapkę #1 w procesie:

[#1] →#2; 0 →#1

Program

Program, podświetlony na żółto, jest zapisany od lewej do prawej w prawym górnym rogu.

Poniżej przedstawiono „przebieg” programu. Czas biegnie w dół strony. Instrukcje są w kolorze żółtym, rejestry w kolorze niebieskim. Program jest odwrócony o 90 stopni, z numerami instrukcji (adresami) u góry, mnemonikami instrukcji pod adresami i parametrami instrukcji pod mnemonikami (po jednym na komórkę):

1 2 3 4 5 6 7 8 9 10 ← Numer dyspozycji (adres)
J Z grudzień INC INC J Z J Z grudzień INC J Z H ← Instrukcja
2 2 3 1 0 1 1 2 0 ← Numer rejestru
6 1 10 6 ← Numer instrukcji skoku
krok IC Inst # nr rej. Adres J reg0 reg1 reg2 reg3 reg4 IC
początek 0 0 2 0 0 1 przesuń [#2] do #1 i #3:
1 1 J Z 2 6 0 0 2 0 0 1→2 J Z Skok nie powiódł się: rejestr nr 2 zawiera 2
2 2 grudzień 2 0 0 0 2→1 0 0 2→3 grudzień Zmniejsz rejestr nr 2 z 2 do 1
3 3 INC 3 0 0 0 1 0→1 0 3→4 INC Zwiększ rejestr nr 3 od 0 do 1
4 4 INC 1 0 0 0→1 1 1 0 4→5 INC Zwiększ rejestr nr 1 od 0 do 1
5 5 J Z 0 1 0 1 1 1 0 5→1 J Z U-Jump: rejestr #0 jest pusty
6 1 J Z 2 6 0 1 1 1 0 1→2 J Z Skok nie powiódł się: rejestr nr 2 zawiera 1
7 2 grudzień 2 0 0 1 1→0 1 0 2→3 grudzień Zmniejsz rejestr nr 2 od 1 do 0
8 3 INC 3 0 0 1 0 1→2 0 3→4 INC Zwiększ rejestr nr 3 od 1 do 2
9 4 INC 1 0 0 1→2 0 2 0 4→5 INC Zwiększ rejestr nr 1 od 1 do 2
10 5 J Z 0 1 0 2 0 2 0 5→1 J Z U-Jump: rejestr #0 jest pusty
11 1 J Z 2 6 0 2 0 2 0 1→6 J Z Skocz!: rejestr nr 2 jest pusty
przesuń [1] na 2:
12 6 J Z 1 10 0 2 0 2 0 6→7 J Z Skok nie powiódł się: rejestr nr 1 zawiera 2
13 7 grudzień 1 0 0 2→1 0 2 0 7→8 grudzień Zmniejsz rejestr nr 1 z 2 do 1
14 8 INC 2 0 0 1 0→1 2 0 8→9 INC Zwiększ rejestr nr 2 od 0 do 1
15 9 J Z 0 6 0 1 1 2 0 9→6 J Z U-Jump: rejestr #0 jest pusty
16 6 J Z 1 10 0 1 1 2 0 6→7 J Z Skok nie powiódł się: rejestr nr 1 zawiera 1
17 7 grudzień 1 0 0 1→0 1 2 0 7→8 grudzień Zmniejsz rejestr nr 1 od 1 do 0
18 8 INC 2 0 0 0 1→2 2 0 8→9 INC Zwiększ rejestr #2 od 1 do 2
19 9 J Z 0 6 0 0 2 2 0 9→6 J Z U-Jump: rejestr #0 jest pusty
20 6 J Z 1 10 0 0 2 2 0 6→10 J Z Skocz!: rejestr nr 1 jest pusty
21 10 H 0 0 0 0 2 2 0 10→10 H POSTÓJ

Częściowe funkcje rekurencyjne: budowanie „wygodnych instrukcji” z wykorzystaniem rekurencji

Powyższy przykład pokazuje, jak pierwsze podstawowe instrukcje {INC, DEC, JZ} mogą utworzyć trzy kolejne instrukcje — skok bezwarunkowy J, CLR, CPY. W pewnym sensie CPY używał zarówno CLR, jak i J oraz zestawu podstawowego. Gdyby rejestr #3 zawierał początkowo zawartość, suma zawartości #2 i #3 znalazłaby się w #3. Aby więc być w pełni dokładnym, program CPY powinien poprzedzić swoje ruchy CLR (1) i CLR (3).

Widzimy jednak, że ADD byłoby możliwe z łatwością. I faktycznie, poniżej znajduje się podsumowanie tego, jak mogą powstać prymitywne funkcje rekurencyjne , takie jak ADD, MULTiply i EXPonent (patrz Boolos-Burgess-Jeffrey (2002) s. 45-51).

  • Początkowy zestaw instrukcji: { DEC, INC, JZ, H }
  • Zdefiniuj bezwarunkowy „skok J (z)” w kategoriach JZ ( r0, z ), biorąc pod uwagę, że r0 zawiera 0.
{ J, DEC, INC, JZ, H }
  • Zdefiniuj „CLeaR ( r ) w odniesieniu do powyższego:
{ CLR, J, DEC, INC, JZ, H }
  • Zdefiniuj „CoPY ( r j , r k )” z zachowaniem zawartości r j pod względem powyższego:
{ CPY, CLR, J, DEC, INC, JZ, H }
Powyższe jest zbiorem instrukcji Shepherdsona-Sturgisa (1963).
  • Zdefiniuj „ADD ( r j , r k , r i )", (być może zachowując zawartość r j i r k ), używając powyższego:
{ ADD, CPY, CLR, J, DEC, INC, JZ, H }
  • Zdefiniuj " MULTiply ( r j , r k , r i )" (MUL) (być może zachowując zawartość r j , r k ), w odniesieniu do powyższego:
{ MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }
  • Zdefiniuj "EXPonential ( r j , r k , r i )" (EXP) (być może zachowując zawartość r j , r k ) w odniesieniu do powyższego,
{ EXP, MUL, ADD, CPY, CLR, J, DEC, INC, JZ, H }

Ogólnie rzecz biorąc, możemy zbudować dowolną częściowo lub całkowicie prymitywną funkcję rekurencyjną , używając tych samych metod. Rzeczywiście, Minsky (1967), Shepherdson-Sturgis (1963) i Boolos-Burgess-Jeffrey (2002) demonstrują, jak utworzyć pięć prymitywnych „operatorów” funkcji rekurencyjnych (1-5 poniżej) ze zbioru podstawowego (1).

Ale co z pełną równoważnością Turinga ? Musimy dodać szósty operator — operator μ — aby uzyskać pełną równoważność, zdolną do tworzenia funkcji całkowicie i częściowo rekurencyjnych :

  1. Funkcja zerowa (lub funkcja stała)
  2. Funkcja następcy
  3. Funkcja tożsamości
  4. Funkcja kompozycji
  5. Prymitywna rekurencja (indukcyjna)
  6. operator μ (nieograniczony operator wyszukiwania)

Autorzy pokazują, że można to łatwo zrobić w dowolnym z dostępnych zestawów podstawowych (1, 2 lub 3) (przykład można znaleźć w μ operator ). Należy jednak ostrzec czytelnika, że ​​nawet jeśli operator μ jest łatwo tworzony przez podstawowy zestaw instrukcji, nie oznacza to, że można łatwo utworzyć dowolną funkcję częściowej rekurencji za pomocą modelu podstawowego - implikują równoważność Turinga i częściowe funkcje rekurencyjne nieograniczony operator μ, który może biec do końca łańcucha rejestrów w nieskończoność, szukając swojego celu . Problem polega na tym, że rejestry muszą być wywoływane jawnie przez numer/nazwę, np. INC (47 528) i DEC (39 347), co spowoduje wyczerpanie TABELI instrukcji maszyny skończonej. Bez względu na to, jak „duża” jest skończona maszyna stanów, możemy znaleźć funkcję, która wykorzystuje „większą” liczbę rejestrów.

Problemy z modelem licznika

Problemy zostały szczegółowo omówione w artykule Maszyna o swobodnym dostępie . Problemy dzielą się na dwie główne klasy i trzecią klasę „niedogodności”:

(1) Nieograniczona pojemność rejestrów a ograniczona pojemność instrukcji maszyny stanowej: W jaki sposób maszyna stworzy stałe większe niż pojemność jej skończonej maszyny stanowej?

(2) Nieograniczona liczba rejestrów w porównaniu z ograniczoną liczbą instrukcji maszyny stanowej: W jaki sposób maszyna uzyska dostęp do rejestrów z numerami adresowymi poza zasięgiem/możliwościami jej skończonej maszyny stanowej?

(3) W pełni zredukowane modele są nieporęczne:

Shepherdson i Sturgis (1963) nie przepraszają za swój zestaw 6 instrukcji. Dokonali wyboru w oparciu o „łatwość programowania… a nie oszczędność” (s. 219 przypis 1).

Instrukcje Shepherdsona i Sturgisa ( [r] oznacza „zawartość rejestru r”):

    • PRZYROST ( r ) ; [r] +1 → r
    • ZMNIEJSZENIE ( r ) ; [r] -1 → r
    • WYCZYŚĆ ( r ) ; 0 → r
    • KOPIUJ ( r s do r d ) ; [r s ] → r re
    • SKOK-BEZWARUNKOWY do instrukcji I z
    • SKOK IF [r] = 0 do instrukcji I z

Minsky (1967) rozszerzył swój zestaw 2 instrukcji {INC (z), JZDEC (r, I z )} do { CLR (r), INC (r), JZDEC (r, I z ), J (I z )} przed jego dowodem na to, że „uniwersalną maszynę programową” można zbudować tylko z dwoma rejestrami (s. 255ff).

Maszyny z dwoma licznikami są odpowiednikami Turinga (z zastrzeżeniem)

Dla każdej maszyny Turinga istnieje 2 CM, które ją symuluje, biorąc pod uwagę, że dane wejściowe i wyjściowe 2 CM są odpowiednio zakodowane. Zostało to udowodnione w książce Minsky'ego ( Computation , 1967, s. 255-258), a poniżej naszkicowano alternatywny dowód w trzech krokach. Po pierwsze, maszynę Turinga można symulować za pomocą maszyny skończonej (FSM) wyposażonej w dwa stosy. Wtedy dwa stosy mogą być symulowane przez cztery żetony. Wreszcie, cztery liczniki mogą być symulowane przez dwa liczniki. Maszyna z dwoma licznikami używa zestawu instrukcji {INC( r, z ), JZDEC ( r, z true , z false ) }.

Krok 1: Maszyna Turinga może być symulowana przez dwa stosy.

Maszyna Turinga składa się z FSM i nieskończonej taśmy, początkowo wypełnionej zerami, na których maszyna może zapisywać jedynki i zera. W dowolnym momencie głowica odczytu/zapisu maszyny wskazuje jedną komórkę na taśmie. W tym momencie taśmę można koncepcyjnie przeciąć na pół. Każdą połowę taśmy można traktować jako stos , gdzie górna część to komórka najbliższa głowicy odczytu/zapisu, a dolna część znajduje się w pewnej odległości od głowicy, a wszystkie zera na taśmie znajdują się poza dołem. W związku z tym maszynę Turinga można symulować za pomocą FSM plus dwa stosy. Przesunięcie głowy w lewo lub w prawo jest równoznaczne z wyjęciem kawałka z jednego stosu i przesunięciem go na drugi. Pisanie jest równoznaczne ze zmianą bitu przed jego wciśnięciem.

Krok 2: Stos może być symulowany przez dwa żetony.

Stos zawierający zera i jedynki może być symulowany przez dwa liczniki, gdy bity na stosie są traktowane jako reprezentujące liczbę binarną (najwyższy bit na stosie jest bitem najmniej znaczącym). Włożenie zera na stos jest równoznaczne z podwojeniem liczby. Wciśnięcie jedynki jest równoznaczne z podwojeniem i dodaniem 1. Przebicie jest równoznaczne z dzieleniem przez 2, gdzie reszta to usunięty bit. Dwa liczniki mogą symulować ten stos, w którym jeden z liczników przechowuje liczbę, której reprezentacja binarna reprezentuje bity na stosie, a drugi licznik służy jako notatnik. Aby podwoić liczbę w pierwszym liczniku, FSM może zainicjować drugi licznik do zera, a następnie wielokrotnie zmniejszać pierwszy licznik raz i zwiększać drugi licznik dwukrotnie. Trwa to do momentu, gdy pierwszy licznik osiągnie zero. W tym momencie drugi licznik będzie zawierał podwojoną liczbę. Zmniejszanie o połowę polega na dwukrotnym zmniejszeniu jednego licznika i zwiększeniu drugiego raz oraz powtarzaniu, aż pierwszy licznik osiągnie zero. Resztę można określić na podstawie tego, czy osiągnęła zero po parzystej, czy nieparzystej liczbie kroków, gdzie parzystość liczby kroków jest zakodowana w stanie FSM.

Krok 3: Cztery liczniki mogą być symulowane przez dwa liczniki.

Tak jak poprzednio, jeden z żetonów służy jako notatnik. Drugi zawiera liczbę całkowitą , której rozkład na czynniki pierwsze to 2 a 3 b 5 c 7 d . Wykładniki a , b , c i d można traktować jako cztery wirtualne liczniki, które są pakowane (za pomocą numeracji Gödla ) do jednego rzeczywistego licznika. Jeśli licznik rzeczywisty jest ustawiony na zero, a następnie zwiększany raz, jest to równoznaczne z ustawieniem wszystkich liczników wirtualnych na zero. Jeśli rzeczywisty licznik zostanie podwojony, jest to równoważne zwiększeniu a , a jeśli zmniejszy się o połowę, jest to równoważne zmniejszeniu a . Za pomocą podobnej procedury można ją pomnożyć lub podzielić przez 3, co jest równoważne zwiększaniu lub zmniejszaniu b . Podobnie c i d można zwiększać lub zmniejszać. Aby sprawdzić, czy wirtualny licznik, taki jak c , jest równy zeru, po prostu podziel rzeczywisty licznik przez 5, zobacz, jaka jest reszta, a następnie pomnóż przez 5 i dodaj resztę. To pozostawia prawdziwy licznik bez zmian. Reszta będzie różna od zera wtedy i tylko wtedy, gdy c wynosi zero.

W rezultacie FSM z dwoma licznikami może symulować cztery liczniki, które z kolei symulują dwa stosy, które symulują maszynę Turinga. Dlatego FSM plus dwa liczniki jest co najmniej tak potężny jak maszyna Turinga. Maszyna Turinga może łatwo symulować FSM z dwoma licznikami, dlatego te dwie maszyny mają równoważną moc.

Zastrzeżenie: *Jeśli* jego liczniki są ustawione na N i 0, to 2CM nie może obliczyć 2 N

Wynik ten, wraz z listą innych funkcji N , których nie da się obliczyć na maszynie z dwoma licznikami — po zainicjowaniu N w jednym liczniku i 0 w drugim — takich jak N 2 , sqrt( N ), log 2 ( N ) itp. pojawia się w artykule Schroeppela (1972). Wynik nie jest zaskakujący, ponieważ model maszyny z dwoma licznikami został udowodniony (przez Minsky'ego) jako uniwersalny tylko wtedy, gdy argument N jest odpowiednio zakodowany (przez Gödelization), aby symulować maszynę Turinga, której początkowa taśma zawiera N zakodowane w systemie jednoargumentowym; ponadto wyjście maszyny dwulicznikowej będzie podobnie zakodowane. Zjawisko to jest typowe dla bardzo małych baz obliczeniowych, których uniwersalność dowodzi jedynie symulacja (np. wiele tarpitów Turinga , najmniejsza znana uniwersalna maszyna Turinga itp.).

Dowód poprzedzony jest kilkoma interesującymi twierdzeniami:

  • „Twierdzenie: maszyna z trzema licznikami może symulować maszynę Turinga” (s. 2, również por. Minsky 1967: 170-174)
  • „Twierdzenie: 3CM [maszyna z trzema licznikami] może obliczyć dowolną częściową funkcję rekurencyjną jednej zmiennej. Zaczyna się od argumentu [tj. N ] w liczniku i (jeśli się zatrzymuje) pozostawia odpowiedź [tj. F ( N )] w liczniku”. (str. 3)
  • „Twierdzenie: Maszyna licząca może być symulowana przez maszynę 2CM [maszyna z dwoma licznikami], pod warunkiem zaakceptowania niejasnego kodowania dla wejścia i wyjścia” [s. 3; „niejasne kodowanie” to: 2 W 3 X 5 Y 7 Z gdzie symulowane liczniki to W, X, Y, Z]
  • „Twierdzenie: Dowolna maszyna licząca może być symulowana przez 2 cm, pod warunkiem, że akceptowane jest niejasne kodowanie dla wejścia i wyjścia”. (str. 3)
    • „Wniosek: problem zatrzymania dla 2CM jest nierozwiązywalny.
    • „Wniosek: 2CM może obliczyć dowolną częściową funkcję rekurencyjną jednego argumentu, pod warunkiem, że wejście jest zakodowane jako 2 N , a wyjście (jeśli maszyna się zatrzyma) jest zakodowane jako 2 odpowiedzi ”. (str. 3)
  • „Twierdzenie: nie ma maszyny z dwoma licznikami, która oblicza 2 N [jeśli jeden licznik jest zainicjowany na N ]”. (str. 11)

W odniesieniu do drugiego twierdzenia, że ​​„3CM może obliczyć dowolną cząstkową funkcję rekurencyjną”, autor rzuca czytelnikowi „Trudny problem: pomnóż dwie liczby, używając tylko trzech liczników” (s. 2). Główny dowód dotyczy poglądu, że maszyny z dwoma licznikami nie mogą obliczać ciągów arytmetycznych o nieliniowym tempie wzrostu (s. 15), tj. „funkcja 2 X rośnie szybciej niż jakikolwiek postęp arytmetyczny”. (s. 11).

Praktyczny przykład obliczania przez liczenie

Kalkulator Friden EC-130 jako taki nie miał logiki sumatora. Jego logika była wysoce szeregowa, wykonując arytmetykę poprzez liczenie. Wewnętrznie cyframi dziesiętnymi były podstawa-1 — na przykład szóstka była reprezentowana przez sześć kolejnych impulsów w przedziale czasowym przydzielonym tej cyfrze. Każdy przedział czasowy zawierał jedną cyfrę, zaczynając od najmniej znaczącej. Carrie ustawia przerzutnik, który powoduje dodanie jednego licznika do cyfry w następnym przedziale czasowym.

Dodawanie odbywało się za pomocą licznika w górę, a odejmowanie za pomocą licznika w dół, z podobnym schematem postępowania z pożyczkami.

Schemat szczeliny czasowej definiował sześć rejestrów po 13 cyfr dziesiętnych, każdy z bitem znaku. Mnożenie i dzielenie odbywało się zasadniczo poprzez wielokrotne dodawanie i odejmowanie. Wersja z pierwiastkiem kwadratowym, EC-132, skutecznie odejmowała kolejne nieparzyste liczby całkowite, a każdy spadek wymagał dwóch kolejnych odejmowań. Po pierwszym odejmowaniu zwiększano o jeden przed drugim odejmowaniem.

Zobacz też

  • George Boolos , John P. Burgess , Richard Jeffrey (2002), Computability and Logic: Fourth Edition , Cambridge University Press, Cambridge, Anglia. Oryginalny tekst Boolos-Jeffrey został obszernie poprawiony przez Burgessa: bardziej zaawansowany niż podręcznik wprowadzający. Model „maszyny liczydła” został szeroko rozwinięty w rozdziale 5 Obliczalność liczydła ; jest to jeden z trzech obszernie omawianych i porównywanych modeli - maszyna Turinga (nadal w oryginalnej postaci 4-krotek Boolosa) i rekurencja pozostałych dwóch.
  •   Arthur Burks , Herman Goldstine , John von Neumann (1946), Wstępne omówienie logicznego projektu elektronicznego instrumentu obliczeniowego , przedruk s. 92ff w Gordon Bell i Allen Newell (1971), Struktury komputerowe: odczyty i przykłady , książka mcGraw-Hill Firma, Nowy Jork. ISBN 0-07-004357-4 .
  • Stephen A. Cook i Robert A. Reckhow (1972), Maszyny o ograniczonym czasie dostępu swobodnego , 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 o swobodnym dostępie, podejście do języków programowania , Journal of Association for Computing Machinery, tom. 11, nr 4 (październik 1964), s. 365–399.
  •    Fischer, Patrick C .; Meyer, AR ; Rosenberg, Arnold L. (1968), „Maszyny licznikowe i języki przeciwne”, Teoria systemów matematycznych , 2 (3): 265–283, doi : 10.1007 / bf01694011 , MR 0235932 , S2CID 13006433 . Rozwija o hierarchii czasu i hierarchii przestrzeni dla liczników, analogiczne do hierarchii dla maszyn Turinga.
  • J. Hartmanis (1971), „Złożoność obliczeniowa maszyn z programami o dostępie swobodnym”, Mathematical Systems Theory 5, 3 (1971), s. 232–245.
  •   Hopcroft, John; Jeffreya Ullmana (1979). Wprowadzenie do teorii automatów, języków i obliczeń (wyd. 1). Czytanie mszy: Addison-Wesley. ISBN 0-201-02988-X . Trudna książka skupiona wokół kwestii maszynowej interpretacji „języków”, NP-kompletnoś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. Zobacz strony 462-463, gdzie definiuje „nowy rodzaj abstrakcyjnej maszyny lub„ automatu ”, który zajmuje się połączonymi strukturami”.
  • Joachim Lambek (1961, otrzymany 15 czerwca 1961), How to Program an Infinite Abacus , Mathematical Bulletin, tom. 4, nie. 3. Wrzesień 1961 strony 295–302. W swoim dodatku II Lambek proponuje „formalną definicję programu”. Odwołuje się do Melzaka (1961) i Kleene (1952) Wprowadzenie do metamatematyki .
  • ZA Melzak (1961, otrzymano 15 maja 1961), Nieformalne podejście arytmetyczne do obliczalności i obliczeń , Canadian Mathematical Bulletin , tom. 4, nie. 3. Wrzesień 1961 strony 279-293. Melzak nie podaje żadnych odniesień, ale uznaje „korzyści płynące z rozmów z dr R. Hammingiem, D. McIlroyem i V. Vyssotsem z Laboratoriów telefonicznych Bell oraz z dr H. Wangiem z Uniwersytetu Oksfordzkiego”.
  •   Marvin Minsky (1961). „Rekurencyjna nierozwiązywalność problemu Posta z„ znacznikiem ”i inne tematy w teorii maszyn Turinga”. Roczniki matematyki . 74 (3): 437–455. doi : 10.2307/1970290 . JSTOR 1970290 .
  • Marvin Minsky (1967). Obliczenia: maszyny skończone i nieskończone (wyd. 1). Englewood Cliffs, NJ: Prentice-Hall, Inc. W szczególności patrz rozdział 11: Modele podobne do komputerów cyfrowych i rozdział 14: Bardzo proste podstawy obliczalności . W poprzednim rozdziale definiuje „maszyny programowe”, aw następnym omawia „maszyny programu uniwersalnego z dwoma rejestrami” i „… z jednym rejestrem” itp.
  • John C. Shepherdson i HE Sturgis (1961) otrzymali w grudniu 1961 Computability of Recursive Functions , Journal of the Association of Computing Machinery (JACM) 10:217-255, 1963. Niezwykle cenny artykuł referencyjny. W swoim Dodatku A autorzy cytują 4 inne w odniesieniu do „Minimalizacji 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 operatorów , (rosyjski) Dok. Akad. Nauk 122 (1958), 967-970. Tłumaczenie angielskie, 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-Fizyka. Semesterberichte (Göttingen) 4 (1954), 42–53.
  • A. Schönhage (1980), Storage Modification Machines , Society for Industrial and Applied Mathematics, SIAM J. Comput. Tom. 9, nr 3, sierpień 1980. W którym Schönhage pokazuje równoważność swojego SMM z „następcą RAM” (Random Access Machine) itp.
  • Rich Schroeppel , maj 1972, „Maszyna z dwoma licznikami nie może obliczyć 2 N ”, Massachusetts Institute of Technology, AI Laboratory, notatka dotycząca sztucznej inteligencji nr 257. Autor odwołuje się do Minsky'ego 1967 i zauważa, że ​​„ Frances Yao niezależnie udowodniła nieobliczalność przy użyciu podobnej metody w kwietniu 1971”.
  • Peter van Emde Boas , Machine Models and Simulations s. 3–66, pojawiające się w:
  Jana van Leeuwena , 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.
Leczenie SMM przez van Emde Boasa pojawia się na s. 32-35. Ten zabieg wyjaśnia Schōnhage 1980 - ściśle podąża za leczeniem Schōnhage, ale nieznacznie go rozszerza. Do skutecznego zrozumienia mogą być potrzebne oba odniesienia.
  • Hao Wang (1957), Wariant teorii maszyn obliczeniowych Turinga , JACM (Journal of Association for Computing Machinery) 4; 63–92. Przedstawione na zebraniu Towarzystwa w dniach 23-25 ​​czerwca 1954 r.

Linki zewnętrzne

  1. ^ „Zarchiwizowana kopia” (PDF) . stedolan.net . Zarchiwizowane od oryginału (PDF) w dniu 14.02.2021 r. {{ cite web }} : CS1 maint: zarchiwizowana kopia jako tytuł ( link )
Pobrano z „ https://en.wikipedia.org/w/index.php?title=Counter_machine&oldid=1114685990 ”