viewer3

U. Dosu

takie zdecydować się skupić swoją uwagę no innym kwadraciku. Turing założył, że obliczający może przesunąć swoją uwagę jedynie na kwadracik będący bezpośrednim sąsiadem czy to z lewej, czy to z prawej strony kwadracika poprzednio przeczytanego. I znowu nic stanowi to istotnegoograniczenia: jeżeli chcemy zwrócić uwagę na kwadracik znajdujący się o tr/> miejsca w prawo, wystarczy po prostu trzykrotnie przesunąć się do sąsiedniego kwadracika w prawo. Obliczający może ponadto przyjrzeć się znakowi w przeczytanym kwadraciku i podjąć stosowną decyzję. Przypuszczalnie decyzja ta winna mieć posiać: „jikq czynność mam wykonać jako następną'*" Wreszcie obliczający może się zatrzymać, sygnał tztąjąC tym samym koniec obliczeń.

/rekapitulujmy: dowolne obliczenie można sobie przedstaw ić jako wyko nywane przez człowieka operującego na ciągach zer i jedynek zapisanych na liniowej taśmie, który rna do dyspozycji instrukcje następującej postaci:

Zapisz znak I.

Zapisz znak 0.

Przesuń się o jeden kwadracik w prawo.

Przesuń się o jeden kwadracik w lewo.

Przyjrzyj cię znakowi aktualaieczytaneoiu i odpowiednio wybierz następny krok.

Zatrrymaj się.

Procedura jaką wykonuje obliczający ma wówczas postać listy instrukcji tego rodzaju. Podobnie jak we współczesnej praktyce komputerowej, wyginie jest uważne, że tego rodzaju instrukcje stanowią ipecydry h'ayk progranHMinia. Lista takich instrukcji napisanych w tym języku nazywa vę wtedy probantem.

Jesteśmy obecnie przygotowani do tego. by wprowodzić język programowania Turinga-Pesta. W języku tym istnieje 7 rod*suów instrukcji:

DRUKUJł DRUKUJ 0 IDŹ W PRAWO IDŹ W LEWO

fDŹ DO KROKU i JEŚLI PRZECZYTAŁEŚ I IDŹ DO KROKU i JEŚLI PRZECZYTAJcEŚ 0 ZATRZYMA! Się

Program Turinga-Poaa jest listą instrukcji, z których każda jest jedną r. tych siedmiu instrukcji. Oczywiście w konkretnym programie litera i występujący w instrukcji 5 lub (. musi być zastąpiona określoną liczbą (dodatnia i talkowi Kt).

Aby konkretny program Turinga-PoUa mógł rozpocząć obliczenia, musi (nieć jakieś dane wjJcioue. Oznacza (o, ze program musi rozpocząć czytań k: w określonym kwadraciku taśmy, która już zawiera ciąg zer i jedynek. Znak 0

4

- 266 -

odgrywa rolę 2naku ..pustego", pomimo ze cala taśma yest nieskończona. jest *aw**ć na niej nie więcej niż skończona liczba jedynek pojawiających się podczas obliczeń. (Jeżeli Czytelnika razi pojęcie nieskończonej taśmy, może on sobie dla naszych celów wyobrazić taśmę skończoną, d© której doczepia się puste kwadraciki, tj. kwadraciki wypełnione zetami, po lewej lub prawej stromo, jeśli okaże aśę to potrzebne.)

W tablicy I przestawiony jest program Turinga-Posta składający się z 10 instrukcji, którego będziemy używali wielokrotnie <1© celów- ilustracyjnych.

t. DRUKWJO

2. itó W LEWO

1. Ulż IX) KROKU 2 JESIJ PRZECZYTAŁEŚ 1

4.    DRUKUJ I

5.    IDŹ. W PRAWO

K IDŹ IX) KROKU 5 JESU PRZECZYTAŁEŚ J 7. DRUKUJ ) i. IDŹ, W PRAWO

4. IDŹ DO KROKU t /EŚU PRZECZYTAŁEŚ J 10. ZATRZYMAJ SIĘ

Obecność instrukcji IDŹ DO umożliwia wielokrotne wykonywanie lej sunej instrukcji podczas pojedynczego obliczenia. Można to prześledzić w taW. 2 poliaząjąccj kolejne kroki pewnego obliczenia wykonanego według programu z labl. I. Obliczanie jest w zupełności zdeterminowane przez początkowy ukiad znaków na taśmie oraz przez wskazanie, od którego kwadracika należy rozpocząć czytanie. W tablicy 2 tę ostatnią informację pokazuje skierowana ku górze strzałka (?) znąjdująca się poniżej czytanego kwadracika. (Naturalnie tylko skończona liczba znaków znajdujących się na taśmie może być pokazana explicite; w tabl- 2 pokarano 6 sąuednich znaków i zakładamy, że wszystkie kwadraciki których nic pokazano zawierają znaki puste, tj. znaki 0.) Taka łączna informacja. na którą składają się znaki znajdujące się na uśmk (reprezentowane ptzez skończoną liczbę następujących po sobie kwadracikowi pizy założeniu, źe pozostałe kwadraciki są puste) oraz identyfikacja czytanego kwadraciku (orna czoncgo strzałką znajdującą się poniżej), naz ywa się konfiguracja taśmową: W tablicy 2 przedstawiono lisię takich konfiguracji taśmowych, / początkową konfiguracją znajdującą się na samej górze; każda z nich zostaje przekształcona za pomocą odpowiedniego kroku programu (tabl I) na konfi-guragę pokazaną poniżej. Kruki programu zestawione są luzem z konfigina-•cjami taśmowy mi. Obliczenie rozpoczyna się od wykonania kroku pierwszego (który w naszym przypadku polega na zastąpieniu I w czytanym kwadraciku

-267-