Wang B-maszyna

Jak przedstawił Hao Wang (1954, 1957), jego podstawowa maszyna B jest niezwykle prostym modelem obliczeniowym równoważnym maszynie Turinga . Jest to „pierwsze sformułowanie teorii maszyny Turinga w kategoriach modeli komputerowych” (Minsky, 1967: 200). Z tylko 4 sekwencyjnymi instrukcjami jest bardzo podobny, ale nawet prostszy niż 7 kolejnych instrukcji maszyny Post-Turinga . W tym samym artykule Wang przedstawił różne równoważne maszyny, w tym to, co nazwał maszyną W , która jest maszyną B z instrukcją „kasowania” dodaną do zestawu instrukcji.

Opis

Zgodnie z definicją Wanga (1954) maszyna B ma do dyspozycji tylko 4 instrukcje:

(1) → : Przesuń głowicę skanującą taśmę o jedno pole taśmy w prawo (lub przesuń taśmę o jedno pole w lewo), a następnie przejdź do następnej instrukcji w kolejności numerycznej;
(2) ← : Przesuń głowicę skanującą taśmę o jedno pole taśmy w lewo (lub przesuń taśmę o jedno pole w prawo), a następnie przejdź do następnej instrukcji w kolejności numerycznej;
(3) * : Na zeskanowanej taśmie kwadratowej drukuj znak * następnie przejdź do następnej instrukcji w kolejności numerycznej;
(4) C n: Warunkowe „przejście” (skok, rozgałęzienie) do instrukcji „n”: Jeśli zeskanowany kwadrat taśmy jest zaznaczony, przejdź do instrukcji „n” w przeciwnym razie (jeśli zeskanowany kwadrat jest pusty) przejdź do następnej instrukcji w kolejności numerycznej .

Próbką prostej instrukcji B-maszyny jest jego przykład (s. 65):

1. *, 2. →, 3. C2, 4. →, 5. ←

Przepisuje to jako zbiór uporządkowanych par:

{ ( 1, * ), ( 2, → ), ( 3, C2 ), ( 4, → ), ( 5, ← ) }

Maszyna Wanga Wanga to po prostu maszyna B z jedną dodatkową instrukcją

(5) E : Na zeskanowanej taśmie kwadratowej usuń znak * (jeśli jest), a następnie przejdź do następnej instrukcji w kolejności numerycznej.

Zobacz też

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.
ZA Melzak (1961) otrzymał 15 maja 1961 r. 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 doktorami R. Hammingiem , D. McIlroyem i V. Vyssotskym z Laboratoriów telefonicznych Bell oraz z dr H. Wangiem z uniwersytetu w Oksfordzie”.
Joachim Lambek (1961) otrzymał 15 czerwca 1961 Jak zaprogramować nieskończone liczydło , 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 .
Marvin Minsky (1967), Computation: Finite and Infinite Machines , Prentice-Hall, Inc. Englewood Cliffs, NJ W szczególności zob. 262ff (kursywa w oryginale):

„Możemy teraz zademonstrować niezwykły fakt, po raz pierwszy wykazany przez Wanga [1957], że dla dowolnej maszyny Turinga _T istnieje równoważna maszyna Turinga TN , która nigdy nie zmienia raz zapisanego symbolu ! W rzeczywistości skonstruujemy dwusymbol maszyna T _N , która może tylko zamieniać puste kwadraty na swojej taśmie na jedynki, ale nie może zamieniać 1 z powrotem na puste miejsce”. Następnie Minsky przedstawia na to dowód.