3813100527

Definicja 1.5. Obliczeniem maszyny A na słowie u = a^a\    £ E* nazy

wamy dowolny ciąg stanów taki, że sq £ I oraz dla wszystkich i ^ m, Si+i € T(si,o’i).

Zastanówmy się nad intuicyjnym sensem Definicji 1.5. Otóż przebieg obliczenia maszyny można oddać w następujący sposób.

Etap 0. Maszyna A wybiera dowolny element sq £ I.

Etap 1. Jeśli nie istnieje s\ £ S taki, że Si £ T{sq,(Tq), to wówczas maszyna zatrzymuje się. W przeciwnym wypadku A wybiera w sposób losowy stan Si £ T(s₀,c7o). Maszyna A „dopisuje” Si do ciągu odwiedzonych stanów -- na tym etapie obliczenie składa się z dwóch stanów: sosi.

Etap k., gdzie k ^ m. Przypuśćmy, że maszyna A utworzyła już ciąg

SoSi . . . Sfc_i.

Jeśli nie istnieje stan s_k £ S taki, że s_k £ T(s_k-1,07c-i), to maszyna nie zdoła przeczytać słowa u. W przeciwnym przypadku A wybiera w sposób losowy stan s_k £ T(s_k-i,<r_k-i).

Jeśli na pewnym etapie k maszyna zatrzyma się, to A nie przeczyta całego słowa tworząc ciąg S0S1S2 ... s_k-\. W przeciwnym razie maszyna odczyta całe wejście i utworzy ciąg

S{)Si . . . S_mS_m-fi

który jest obliczeniem maszyny A na wejściu u.

Przykład 1.6.

Rozważmy ponownie maszynę A\ z Przykładu 1.3. Niech słowo ui = aaabbb £ £

będzie słowem wejściowym tej maszyny. Obliczeniem ,4i na u\ jest ciąg stanów S0S1S2S2S3S4S5.

To obliczenie jest jedynym obliczeniem .4i na u\.

Niedeterminizm maszyny oznacza, że podczas wykonywania obliczeń „musi ona dokonać wyboru” spośród wielu możliwych przejść z danego stanu, gdy czyta konkretny symbol wejściowy. Wybory te są losowe. Stąd maszyna A może mieć kilka obliczeń na tym samym słowie. Zauważmy również, że nie każde słowo zostanie przeczytane przez maszynę. Stanie się tak, gdy dla pewnego symbolu ze

10