viewer6

U. .0*1 is

znakami przestankowymi. Następnie, przesuwając się od lewej do prawej, trzeba oddzielić- grupę 3 e>fr. Jeżeli tą grupą 3-cyfrową jest: 000.001,010,011, 100. lo odpowiadającą jej instrukcją jest odpowiednio - instrukcja DRUKUJ 0. DRUKUJ I. ID Ź W LEWO. IDŹ W PRAWO, ZATRZYMAJ SIĘ. W przeciwnym rarie grupą tą jest 101 lub 110, a pierwszą instrukcją j«St IDŹ DO. Kod będzie miał wdwouc jedną z dwu następujących postaci:

10)00    11011... 10

I    t

odpowiadających instrukcji

IDŹ DO KROKU i JEŚLI PRZECZYTAŁEŚ 0 oiaz instrukcji

IDŹ DO KROKU i JEŚLI PRZECZYTAŁEŚ 1

Po otrzymaniu pierwszej mstrukcjt należ y zapisać jej kod i kontynuować piOttS, wciąż postępując od lewęj do prawej. Czytelnicy, którzy chcą sprawdzić ery rozumują ten proces, niechaj spróbują deszyfrować ciąg następujący:

10100011010011000001010101011I

Program uniwersalny

Obecnie jesteśmy już przygotowani do tego, by przekonać się. ze analiza proccwi obliczeń wykonana przez "I uringa oraz metoda kodowania probantów Turin-pi-Posta dopiero co wprowadzona, prowadzą do wniosku, który w pierwszej chwili wy daje stę zadziwiający, wniosku. Że istnieje jeden jedyny (odpowiednio zbudowany) program Turinga-Połta. który umożliwia obliczenie wszystkiego cokolwiek tylko daje się obliczyć Taki program O (skrót od „uniwersalny") może być wywołany do zasymulowania dowolnego ustalonego programu

IV

Taśma

lascEPoaBaDcaagocoaaDDCDDBnagnaaDBPiiBflDanopgjpnga

może być rozłożona na części w następujący sposób:

I 00001011011000101111011II I00i)l(ll 11 lOlOIWl 111 II Pisanie!;    /jKoUoaar.e instrukcje progniu £«ćxa'inia    Kenia, Usnę

Turinga-Posta P puct umieszczenie ciągu kod [P). tryli ciągu zet i jedynek icprczeittująccgo P, nn taśmie i uruchomienie U na lej mimie. Mówiąc dokładniej, niepusta część ujmy winna się składać z ciągu kod (P). a po nie; winien następować ciąg wejściowy p, na którym P może pracować. (Urywamy dużych liter na oznaczenie konkretnych programów Turinga-Poeta i małych liter na oznaczenie ciągów zer i jedynek.) Dla przykładu, ciąg pokazany w ramce IV oznacza, że program U winien symulować zachowanie się programu podwajania, idy ciągiem wejściowym jest II. Po zakończeniu obliczeń za pomocą programu V taśma winna wyglądać jak końcowy odcinek taśmy w tnbl. 2.

Jednakże uniwersalny program Tuiinga-Posla U w inien tak się rachować nie tylko w przypadku naszego programu podwajania, ale dla każdego programu Turinea-PoMO. Mów iąc ściśle, pi ogram V winien rozpocząć obliczenia na taśmie, której niepusta część składa się z ciągu kod{P) pewnego programu Turinga-Posta P (czytając początkowo pierwszy mak tego kioku. którym r konieczności jest 1), po którym następuje pewien ciąg v. Program U winien obliczyć taki sam wynik jak program P, który rozpoczyna obliczenia od ciągu v będącego niepustą częścią taśmy (czytając początkowy znak ciągu v). Taki program U mógłby być użyty do symulacji dowolnego programu Turinga-Posta P przez umieszczenie ciągu kod (P) na taśmie.

Jakie mamy powody, by uwierzyć, że taki program V istnieje? Wyobraźmy sobie, jak człowiek wykonujący obliczenia mógłby zrobić to. co winien zrobić program fź Mając do dyspozycji taśmę, na której winien pracować program (/. obliczający mógłby rozpocząć od czytania tego ciągu zer i jedynek od lewej do prawej, szukając pierwszego miejsca, w którym pojawiają się uzy następujące po sobie jedynki Trójka 111 znaczy koniec ciągu kodff) i początek ciągu danych. Obliczający może wówczas zapisać kod (P) na jednej kartce papieru, a ciąg wejściowy danych na drugiej. Jak już wyjaśniliśmy, może on deszyfrować ciąg kad{P) i otrzymać konkretny program Turinga-PoMfl /’. Następnie może się ..zabawić w maszynę" i wykonywać instrukcje programu P na danym ciągu danych w sposób mechaniczny. Jeżeli obliczenia się zatrzymują, obliczający może podać jako ich wynik zawartość końcowej taśmy. Pokazuje to, że człowiek Wykonujący obliczenia może robić to, co winien robić program U. 7. drugiej strony, mając na uwadze analizę procesu obliczeń wykonaną przez Turinga, musimy uwierzyć, że istnieje program Turinga-Postn wykonujący proces dopiero cc opisany, czyli uniwersalny program Turintga-Posta.

Podane uzasadnienie istnienia takiego programu jest niezadowalające, gdyż opiera się na analizie procesu obliczeń podanej przez Turinjsi. 7. pewnością nie jest to dowód matematyczny. Okazuje się, że jeśli nie bać się pewnej żmudnej ale nic bardzo trudnej pracy, to można obejść potrzebę powoływania się na analizę Tu ringu w ogóle i wypijać szczegółowo uniwersalny program Turinga-Posta. Uczynił to w istocie Turing (w nieco innym, ak całkowicie równoważnym kontekście) w swęj podstawowej pracy z roku 1936. Później dokonano lego

273