18.Prednaska

Z Pascal
Prejsť na: navigácia, hľadanie
18. Prednáška

úlohy | cvičenie


Turingov stroj

  • Alan Turing (*1912 +1954) sa považuje za zakladateľa modernej informatiky - rok 2012 sa na celom svete oslavuje ako Turingov rok
  • Turingov stroj je veľmi zjednodušený model počítača, vďaka ktorému sa informatika dokáže zaoberať zložitosťou problémov
  • Turing ho vymyslel v roku 1936
  • základná idea takéhoto stroja je nasledovná:
  • pracuje na nekonečnej páske - postupnosť políčok, na každom môže byť nejaký symbol (my si to zjednodušíme ASCII znakmi)
  • nad páskou sa pohybuje čítacia/zapisovacia hlava, ktorá vie prečítať symbol na páske a prepísať ho iným symbolom
  • samotný stroj (riadiaca jednotka) sa nachádza v nejakom zo svojich stavov a na základe stavu a symbolu na páske sa rozhoduje, čo bude robiť
  • na začiatku je na páske nejaký vstupný reťazec (postupnosť symbolov), stroj sa nachádza v počiatočnom stave (pre nás je to stav 0), celý zvyšok nekonečnej pásky obsahuje prázdne symboly (pre nás je to symbol '_')
  • činnosť stroja sa definuje špeciálnou dvojrozmernou tabuľkou, tzv. pravidlami
  • každé pravidlo popisuje:
  • keď si v konkrétnom stave a na páske je tento symbol, tak ho prepíš týmto symbolom, posuň sa na páske o (-1, 0, 1) políčko a zmeň stav na tento stav
  • napr. pravidlo 0 a b > 1 označuje: v stave 0 so symbolom 'a' na páske ho zmeň na 'b', posuň sa o jedno políčko vpravo a zmeň svoj stav na 1
  • okrem stavu 0 (počiatočný stav) je ešte jeden stav špeciálny - koncový, my ho budeme značiť -1, ten má takýto význam:
  • keď riadiaca jednotka prejde do koncového stavu, výpočet stroja sa zastaví a stroj oznámi, že akceptoval vstupné slovo, vtedy sa môžeme pozrieť na obsah pásky a táto informácia môže byť výsledkom výpočtu
  • stroj sa zastaví aj v prípade, že neexistuje pravidlo, pomocou ktorého by sa dalo pokračovať (stroj skončil v nekoncovom stave), vtedy
  • hovoríme, že stroj oznámil, že zamietol (neakceptoval) vstupné slovo
  • zrejme sa takýto stroj môže niekedy aj zacykliť a neskončí nikdy (pre informatikov je aj toto veľmi dôležitá informácia)

Na internete sa dá nájsť veľa rôznych zábavných stránok, ktoré sa venujú Turingovmu stroju, napr.

Zostavme náš prvý program pre Turingov stroj.

0 a A > 0
0 _ _ = -1

Vidíme, že pre počiatočný stav sú tu dve pravidlá: buď je na páske symbol 'a' alebo symbol '_', ktorý označuje prázdne políčko. Ak teda čítacia hlava má pod sebou na páske symbol 'a', tak ho prepíše na symbol 'A' a posunie hlavu na políčko vpravo. Riadiaca jednotka pritom stále ostáva v stave 0. Vďaka tomuto pravidlu sa postupne všetky písmená 'a' nahradia 'A'. Ak sa pritom narazí na iný symbol, prvé pravidlo sa už nebude dať použiť a stroj sa pozrie, či nemá pre tento prípad iné pravidlo. Ak je na páske už len prázdny symbol, stroj sa zastaví a oznámi radostnú správu, že vstupné slovo akceptoval a vyrobil z neho nový reťazec. Ak ale bude na páske za postupnosťou 'a' aj nejaké iné písmeno, stroj nenájde pravidlo, ktoré by mohol použiť a preto sa zastaví. Oznámi pritom správu, že takéto vstupné slovo zamietol.

Priebeh výpočtu pre vstupné slovo 'aaa' by sme si mohli znázorniť napr. takto:

aaa
^ 0
Aaa
 ^ 0
AAa
  ^ 0
AAA_
   ^ 0
AAA_
   ^ -1  ... úspešne sa zastavil

Všimnite si, že v našej vizualizácii sa na páske automaticky objavujú prázdne symboly, keďže páska je nekonečná a okrem vstupného slova obsahuje práve tieto znaky.

Ak by sme zadali napr. slovo 'aba', tak by výpočet prebiehal takto:

aba
^ 0
Aba
 ^ 0     ... zastavil sa, lebo nevie pokračovať => zamietol vstup


Návrh interprétra

Aby sme mohli s takýmto strojom lepšie experimentovať a mať možnosť si uvedomiť, ako sa pomocou neho riešenia úlohy, naprogramujeme si veľmi jednoduchý interpreter. Začneme tým, že navrhneme triedu, ktorá bude popisovať Turingov stroj a jej metódy budú realizovať výpočet takéhoto stroja. Začneme jednoduchou verziou (vytvoríme v unite TuringUnit):

type
  TTuring = class
    Paska: string;
    PP: array of record    // pole pravidiel
          Vstave: Integer;
          Vstup, Vystup, Pohyb: Char;
          Dostavu: Integer;
        end;
    Stav: Integer;
    Poz: Integer;
    procedure PridajPravidlo(Stav1: Integer; Znak1, Znak2, Poh: Char; Stav2: Integer);
    procedure VstupneSlovo(S: string);
    procedure VykonajKrok;
  end;

Stavové premenné sú asi zrejmé:

  • Paska bude "nekonečná" postupnosť symbolov, budeme ju automaticky nafukovať, podľa toho, ako sa nad ňou pohybuje čítacia hlava
  • PP je tabuľka pravidiel - tieto pravidlá tu môžu byť uvedené v ľubovoľnom poradí a riadiaca jednotka si vyhľadá to správne
  • každé pravidlo sa skladá z piatich prvkov: v akom sme stave, aký je symbol na páske, na aký symbol sa prepíše, ako sa posunie hlava (buď '<' alebo '>') a do akého stavu sa prejde
  • Stav označuje, momentálne číslo stavu (na začiatku bude 0)
  • Poz je pozícia na páske, zrejme by vždy mala byť v intervale <1, Length(Paska)>

Metódy

  • PridajPravidlo pridá do poľa pravidiel PP ďalšie pravidlo
  • VstupneSlovo inicializuje pásku na zadané slovo a nastaví počiatočný stav (Stav = 0) a pozíciu na prvý symbol na páske (Poz = 1)
  • VykonajKrok riadiaca jednotka vykoná jeden krok , samozrejme ak sa v danom stave a nad daným symbolom dá

Naprogramujme prvú verziu týchto metód:

procedure TTuring.PridajPravidlo(Stav1: Integer; Znak1, Znak2, Poh: Char;
  Stav2: Integer);
begin
  SetLength(PP, Length(PP) + 1);
  with PP[High(PP)] do
  begin
    Vstave := Stav1;
    Vstup := Znak1;
    Vystup := Znak2;
    Pohyb := Poh;
    Dostavu := Stav2;
  end;
end;
 
procedure TTuring.VstupneSlovo(S: string);
begin
  if S = '' then
    Paska := '_'
  else
    Paska := S;
  Poz := 1;
  Stav := 0;
end;
 
procedure TTuring.VykonajKrok;
var
  I: Integer;
begin
  I := 0;
  while (I <= High(PP)) and ((PP[I].Vstave <> Stav) or (PP[I].Vstup <> Paska[Poz])) do
    Inc(I);
  if I > High(PP) then
    Exit;
  Paska[Poz] := PP[I].Vystup;
  Stav := Pp[I].Dostavu;
  if Stav < 0 then
    Exit;
  case PP[I].Pohyb of
    '<':
      if Poz = 1 then
        Paska := '_' + Paska
      else
        Dec(Poz);
    '>':
      begin
        Inc(Poz);
        if Poz > Length(Paska) then
          Paska := Paska + '_';
      end;
  end;
end;

V metóde VykonajKrok, vidíme dva prípady, keď sa celý stroj má zastaviť (na príkaz Exit) - teda ďalšie volania tejto metódy už nemajú zmysel. Stroj by si mal zrejme pamätať, čo vlastne momentálne robí, t.j. čí beží alebo už skončil, lebo akceptoval alebo skončil lebo zamietol vstupné slovo. Pridáme ešte jednu stavovú premennú CoRobi a doplníme aj metódu VykonajKrok:

type
  TTuring = class
    Paska: string;
    PP: array of record
          Vstave: Integer;
          Vstup, Vystup, Pohyb: Char;
          Dostavu: Integer;
        end;
    Stav: Integer;
    Poz: Integer;
    CoRobi: (Bezi, Akceptoval, Zamietol);
    procedure PridajPravidlo(Stav1: Integer; Znak1, Znak2, Poh: Char; Stav2: Integer);
    procedure VstupneSlovo(S: string);
    procedure VykonajKrok;
  end;
 
procedure TTuring.VstupneSlovo(S: string);
begin
  if S = '' then
    Paska := '_'
  else
    Paska := S;
  Poz := 1;
  Stav := 0;
  CoRobi := Bezi;
end;
 
procedure TTuring.VykonajKrok;
var
  I: Integer;
begin
  if CoRobi <> Bezi then
    Exit;
  I := 0;
  while (I <= High(PP)) and ((PP[I].Vstave <> Stav) or (PP[I].Vstup <> Paska[Poz])) do
    Inc(I);
  if I > High(PP) then
  begin
    CoRobi := Zamietol;
    Exit;
  end;
  Paska[Poz] := PP[I].Vystup;
  Stav := Pp[I].Dostavu;
  if Stav < 0 then
  begin
    CoRobi := Akceptoval;
    Exit;
  end;
  case PP[I].Pohyb of
    '<':
      if Poz = 1 then
        Paska := '_' + Paska
      else
        Dec(Poz);
    '>':
      begin
        Inc(Poz);
        if Poz > Length(Paska) then
          Paska := Paska + '_';
      end;
  end;
end;

Teraz máme pripravený základ a môžeme ho otestovať v hlavnom programe:

uses
  TuringUnit;
 
var
  T: TTuring;
begin
  T := TTuring.Create;
  T.PridajPravidlo(0, 'a', 'A', '>', 0);
  T.PridajPravidlo(0, '_', '_', '=', -1);
  T.VstupneSlovo('aaa');
  repeat
    T.VykonajKrok;
  until T.CoRobi <> Bezi;
  if T.CoRobi = Akceptoval then
    Write('akceptoval a vysledna paska = ', T.Paska)
  else
    Write('zamietol');
  T.Free;
  ReadLn;
end.

Ďalším vylepšením budu pridanie výpisu, aby sme počas výpočtu videli, ako sa hlava hýbe nad páskou a v akom stave je vtedy riadiaca jednotka. Aby sme mohli pravidlá zadávať pohodlnejšie, uložíme ich všetky do súboru a program ich prečíta naraz všetky. Takže najprv pridáme tieto nové metódy:

type
  TTuring = class
    Paska: string;
    PP: array of record
          Vstave: Integer;
          Vstup, Vystup, Pohyb: Char;
          Dostavu: Integer;
        end;
    Stav: Integer;
    Poz: Integer;
    CoRobi: (Bezi, Akceptoval, Zamietol);
    constructor Create;            // prázdny konštruktor
    constructor Create(Subor: string);       // konštruktor číta zo súboru
    procedure PridajPravidlo(Stav1: Integer; Znak1, Znak2, Poh: Char; Stav2: Integer);
    procedure VstupneSlovo(S: string);
    procedure VykonajKrok;
    function Vysledok: string;
    procedure Vypis;
  end;
 
constructor TTuring.Create;
begin
end;
 
constructor TTuring.Create(Subor: string);
var
  T: TextFile;
  Z: Char;
begin
  AssignFile(T, Subor);
  Reset(T);
  PP := nil;
  while not Eof(T) do
  begin
    SetLength(PP, Length(PP) + 1);
    with PP[High(PP)] do
      ReadLn(T, Vstave, Z, Vstup, Z, Vystup, Z, Pohyb, Dostavu);
  end;
  CloseFile(T);
end;
 
function TTuring.Vysledok: string;
var
  I, J: Integer;
begin
  if CoRobi = Akceptoval then
  begin
    I := 1;
    while (I <= Length(Paska)) and (Paska[I] = '_') do
      Inc(I);
    J := Length(Paska);
    while (J >= I) and (Paska[J] = '_') do
      Dec(J);
    Result := 'akceptoval a na paske =  + Copy(Paska, I, J - I + 1) + ';
  end
  else
    Result := 'zamietol';
end;
 
procedure TTuring.Vypis;
begin
  WriteLn(Paska);
  WriteLn('^': Poz, ' ', Stav);
end;

Hlavný program teraz teraz doplníme:

uses
  TuringUnit;
 
var
  T: TTuring;
  S: string;
begin
  T := TTuring.Create('turing.txt');
  repeat
    Write('vstup: ');
    ReadLn(S);
    if S = '_' then
      Break;
    T.VstupneSlovo(S);
    repeat
      T.Vypis;
      T.VykonajKrok;
    until T.CoRobi <> Bezi;
    T.Vypis;
    WriteLn('vysledok = ', T.Vysledok);
  until False;
  T.Free;
end.

A textový súbor turing.txt napr. takto

0 a A > 0
0 _ _ = -1


Niekoľko riešených úloh

Pri riešení týchto úloh používame aj iný spôsob zápisu pravidiel pre Turingov stroj. Pravidlá sú teraz v dvojrozmernej tabuľke, kde pre každý stav a každý symbol určujeme, čo treba robiť: ak sa prepisuje symbolom, ten je tu uvedený (len keď je iný ako na páske), ak sa čítacia hlava posúva, je tam < alebo >, ak sa mení stav, je tu číslo stavu. Niekedy ja takáto tabuľka čitateľnejšia, ako postupnosť doterajších pravidiel, ktorá je vstupom do nášho testovacieho programu.


  • akceptuj iba slovo 'ahoj' - Turingov stroj postupne kontroluje písmeno za písmenom, pričom na každé použije jeden stav; do koncového stavu sa dostane, až keď je za posledným písmenom prázdny symbol:
0 a a > 1
1 h h > 2
2 o o > 3
3 j j > 4
4 _ _ = -1
a h o j _
0 > 1
1 > 2
2 > 3
3 > 4
4 stop
  • akceptuj, ak sa vstupné slovo skladá z ľubovoľného počtu reťazca 'ok'
0 o o > 1
0 _ _ = -1
1 k k > 0
o k _
0 > 1 stop
1 > 0
  • akceptuj iba párny (nepárny) počet písmen 'a' - stroj má dva stavy, v stave 0 je pri párnom počte 'a', v stave 1 pri nepárnom počte:
0 a a > 1
0 _ _ = -1
1 a a > 0
a _
0 > 1 stop
1 > 0
a akceptovanie nepárneho počtu:
0 a a > 1
1 a a > 0
1 _ _ = -1
a _
0 > 1
1 > 0 stop
  • ak je párny počet 'a', tak písmená zmeň na 'b', inak na 'c' - využijeme predchádzajúce dve riešenia a namiesto ukončenia prejdeme buď do stavu 2, v ktorom sa všetky 'a' zmenia na 'b', alebo do stavu 3, v ktorom sa všetky 'a' zmenia na 'c'
0 a a > 1
0 _ _ < 2
1 a a > 0
1 _ _ < 3
2 a b < 2
2 _ _ = -1
3 a c < 3
3 _ _ = -1
a _
0 > 1 < 2
1 > 0 < 3
2 b < stop
3 c < stop
  • pripočítaj 1 k dvojkovému zápisu čísla
0 0 0 > 0
0 1 1 > 0
0 _ _ < 1
1 0 1 = -1
1 1 0 < 1
1 _ 1 = -1
0 1 _
0 > > < 1
1 1 stop 0 < 1 stop
  • zisti, či je slovo z písmen 'a' a 'b' palindrom
0 a _ > 1
0 b _ > 4
0 _ _ = -1
1 a a > 1
1 b b > 1
1 _ _ < 2
2 a _ < 3
2 _ _ = -1
3 a a < 3
3 b b < 3
3 _ _ > 0
4 a a > 4
4 b b > 4
4 _ _ < 5
5 b _ < 3
5 _ _ = -1
a b _
0 _ > 1 _ > 4 stop
1 > > < 2
2 _ < 3 stop
3 < < > 0
4 > > < 5
5 _ < 3 stop



späť | ďalej