Co je to nenaprogramovatelné?

Mnozí z vás jistě už někdy programovali, mnozí z vás jistě již někdy po někom nějaký ten program četli a mnohým z vás z toho dozajista zůstal rozum stát. Ano, přiznejme si to, lidé jsou líní, programátoři jsou čuníci a své programy odbývají. Čert aby se v tom vyznal. Padá to, nedělá to, co má, cyklí to. Prostě by to chtělo něco, co by nám, project-managerům, dokázalo překontrolovat práci těch druhých. Bohužel, nebude to tak jednoduché. Ono totiž napsat program, který o jiném programu rozhodne, zda se tento program v konečném čase zastaví, není možné.

Bylo by to moc krásné, kdybychom mohli napsat něco jako:

extern bool zastavi(void (* funkce)(void));
void Q(void) {  ... }
int main(int argc, char **argv) {
  if (zastavi(Q)) {
    printf("Ano, program zastaví...\n");
  } else {
    printf("Ne, funkce Q se zacyklí!\n");
  }
}

To ale bohužel nejde a já vám tu teď ukážu, že funkci zastavi, která by o jiném programu řekla, zda zastaví, nebo ne, nedokáže naprogramovat ani ten nejchytřejší programátor.

Nyní si asi říkáte: „Ten problém se zastavením určitě nějak vyřešit půjde.“ Prostě si ten program napíšu, spustím, chvilku počkám a po chvilce uvidím. Ale po jaké chvilce? Po minutě? Po hodině? Po roce? Co když se ale program nezastaví nikdy? Abych vám ukázal, že je problém skutečně neřešitelný, podívejte se na následující funkci Q a položte si otázku: Zastaví?

1 void Q(void) {
2   if (zastavi(Q))
3     while(1) { }
4 }

Ukažme si, že funkce Q je nesmysl. A protože jediné sporné, co v této funkci používáme, je funkce zastavi, ukážeme tím i, že ona funkce zastavi je vlastně nesmysl. Poznamenejme ještě, že každý program buď zastaví, a nebo nezastaví, nic mezi tím (žádné „polozastavení“) neexistuje.

Dejme tomu, že funkce Q zastaví. Pak ale bude splněna podmínka na řádku 2 a z toho nám vyplyne, že vlastně nezastaví.

Dejme tomu, že funkce Q nezastaví. Pak ale podmínka na řádku 2 splněna nebude a z toho nám vyplyne, že vlastně zastaví.

Funkci zastavi nelze naprogramovat.

Sedový problém

V tuto chvíli se může zdát, že „problém zastavení“ je tak trochu uměle vykonstruovaný a že se vám v praxi vlastně nemůže stát, že by vám nějaký project-manager zadal úkol, který by nešel vyřešit. Chyba lávky! Za dalším neřešitelným/ne­naprogramovatel­ným problémem nemusíme chodit daleko. Jistě všichni znáte užitečný program sed(1). Omezme se pouze na náhrady řetězce za jiný řetězec. Například:

sed 's/kos/sok/'
sed 's/oso/kosos/'
sed 's/s/sksosok'
sed 's/soso/kk/'

Nyní si můžete z těchto „sedů“ vybírat v libovolném pořadí a od každého libovolný počet a seřadit je rourami tak, aby například:

echo "kokos" | sed '...' | sed '...' | sed '...' || ... sed ... || sed '...'

vypsalo „kkkkk“.

Můžete si to zkusit vymyslet a zjistíte, že to skutečně není nic jednoduchého. Řešení může být v tomto případě více, například:

echo kokos | sed 's/kos/sok/' | sed 's/oso/kosos/' | sed 's/kos/sok/' | sed 's/kos/sok/' | sed 's/soso/kk/'


Program, který jako svůj vstup vezme seznam „sedů“ a dvě slova („kokos“ a „kkkkk“) a v konečném čase vám řekne, jaké „sedy“ vybrat a jak je seřadit (můžou se opakovat) tak, aby echo „první slovo“ | sed | sed | sed | sed… vypsalo druhé slovo, nelze naprogramovat. No a já vám teď povím, proč tomu tak je.

Stroj Alana Turinga

Byl jednou jeden pán, jmenoval se Alan Turing a žil v letech 1912–1954. Tento pán byl velmi chytrý a jednoho dne vymyslel stroj a pojmenoval ho „Turinguv stroj“ (dale jen TS). TS však není stroj v pravém slova smyslu. S trochou nadsázky a představivosti by se dal TS přirovnat spíše k velmi nízkoúrovňovému programovacímu jazyku vzdáleně připomínajícímu assembler. Pro současné počítače je TS velmi nemotorný a nepraktický programovací jazyk a určitě ho nikdy žádný programátor nebude používat. Bez ohledu na všechny tyto nevýhody a nepraktičnost použití TS za účelem skutečného programování má TS stejnou sílu jako jakýkoli jiný programovací jazyk. Například překladač jazyka C do jazyka TS by samozřejmě šel naprogramovat.

TS se skládá z několika částí. Je to jednak Hardware – nekonečná páska s čtecí hlavou. Páska nemá konec ani na jedné straně a je zpočátku zaplněna samými nulami, hlava někam ukazuje (celkem je jedno kam, páska je nekonečná z obou stran, všude jsou nuly). Následující obrázek vše objasňuje:

   .......00000000000000000000.......
                   ^

Další částí TS je software, tedy program. Program pro TS se píše do tabulky (řádek je konečně mnoho, nekonečný program neexistuje!) a může vypadat třeba takto:

         0      1
      -------------
(S1): (S2)1R (S6)0L
(S2): (S3)0R (S4)0R
(S3): (S4)1L (S5)1R
(S4): (S5)0L (S4)0L
(S5): (S1)0R (S3)1R
(S6): (S1)1L (S7)1R
(S7):  Stop   Stop

Celá další konstrukce se ukazuje na příkladu, který mluví o tomto konkrétním TS.

Běh samotného programu je jednoduchý. Začínáme ve stavu (S1) – první řádek. TS se podívá, kam ukazuje hlava na pásce (na nulu), a podle toho vybere sloupec. V tabulce/programu je na průsečíku [(S1), 0] napsáno (S2)1R. To znamená, že TS přejde na řádek (S2), na pásku napíše 1 a čtecí/zapisovací hlavu posune R (Right/Doprava). Po tomto kroku bude páska vypadat takto:

    .......00000000010000000000.......
                     ^
(jsem na řádce S2)

Hlava ukazuje na 0, řádek S2, tedy (S3)0R – přejít na řádek S3, zapsat 0 a hlavu posunout doprava.

    .......00000000010000000000.......
                      ^
(jsem na řádce S3)

Hlava ukazuje na 0, řádek S3, tedy (S4)1L – přejít na řádek S4, zapsat 1 a hlavu posunout doleva.

    .......00000000010100000000.......
                     ^
(jsem na řádce S3)

Tak pokračujeme až do doby, kdy skočíme na řádek S7 a program se zastaví.
Kvíz:: Co udělá výše zmiňovaný TS? Zastaví? Jestliže ano, po kolika krocích? Odhadem, po 10 krocích? po 100? nebo snad po 1000? Co bude na pásce? Kdo na to přijde, má u mě pivo!

Vraťme se nyní k „sedovému“ problému a trochu si ho připodobníme k TS. Nejprve si čtecí/zapisovací hlavu TS pěkně zakódujeme do pásky. Nebudeme tedy psát:

    .......00000000010100000000.......
                     ^
(jsem na řádce S3)

Ale zjednodušeně (nebo snad složitě?):

  .......0000000001(S3)0100000000.......
(jsem na řádce S3)

Jako výchozí slovo sedového problému dáme slovo „X(S1)Y“ a ptám se, můžeme tyto sedy pospojovat tak, aby na výstupu daly „Stop“? „Sedový“ problém sestavím takto:

 1) sed 's/X/X0/'
 2) sed 's/Y/0Y/'

a vyzkoušejte si napsat:

echo "X(S1)Y" | sed 's/X/X0/' | sed 's/X/X0/' |
sed 's/X/X0/' | sed 's/X/X0/' | sed 's/X/X0/' |
sed 's/X/X0/' | sed 's/Y/0Y/' | sed 's/Y/0Y/' |
sed 's/Y/0Y/'| sed 's/Y/0Y/' | sed 's/Y/0Y/'

Jako výsledek tohoto příkazu dostanete : „X000000(S1)0­0000Y“. Správnou kombinací „sedů“ tak můžeme přidávat doleva i doprava libovolný počet nul. (všimněte si nápadné podobnosti s nekonečnou páskou TS!)

Dále pak přidám:

 3) sed 's/(S1)0/1(S2)/'
 4) sed 's/0(S1)1/(S6)00/'
 5) sed 's/1(S1)1/(S6)10/'
 6) sed 's/(S2)0/0(S3)/'
 7) sed 's/(S2)1/0(S4)/'
 8) sed 's/0(S3)0/(S4)01/'
 9) sed 's/1(S3)0/(S4)11/'
10) sed 's/(S5)1/1(S5)/'
11) sed 's/0(S4)0/(S5)00/'
12) sed 's/1(S4)0/(S5)10/'
13) sed 's/0(S4)1/(S4)00/'
14) sed 's/1(S4)1/(S4)10/'
15) sed 's/(S5)0/0(S1)/'
16) sed 's/(S5)1/1(S3)/'
17) sed 's/0(S6)0/(S1)01/'
18) sed 's/1(S6)0/(S1)11/'
19) sed 's/(S6)1/1(S7)/'

21) sed 's/.(S7)./(S7)/'
22) sed 's/(S7)/Stop/'

Takto jsem vlastně v „sedové“ notaci naprogramoval TS. Mějme například TS s páskou:

X0000001001(S1)0110000000Y

Které sedy budou mít na tento vstup nějaký účinek? Které ho změní? Jsou to samozřejmě 1 a 2 – můžete například udělat:

$ echo 'X0000001001(S1)0110000000Y' | sed 's/X/X0/' | sed 's/X/X0/' | sed 's/X/X0/'
X0000000001001(S1)0110000000Y


To ale můžu udělat pokaždé a vždy jen přidám vlevo nebo vpravo další nuly. Co ale třeba sed 10? Všiměte si, že tento sed nahrazuje (S5)1, to ale v řetězci není, tedy, tento sed nemá na řetězec žádný vliv. Jak můžete vidět:

$ echo 'X0000001001(S1)0110000000Y' | sed 's/(S5)1/1(S5)/'
X0000001001(S1)0110000000Y


Skutečně nemá :-)

Ale co sed ‚s/(S1)0/1(S2)/‘ (3)?

X00000010011(S2)110000000Y
           ^^^^^^

Provedlo se vlastně to samé, jako by byl TS na řádce S1. Přešlo se na řádku S2 a hlava se posunula vpravo. Všechny řádky 3–19 jsou pak vlastně jenom přepsaný program TS. Řádky 21 a 22 dokáží pak vymazat postupně celý vstup a nakonec dát za S7 „Stop“. Ovšem, řádek S7 je koncový, takže je možné dostat posloupností sedů na výstup slovo …S7… jen v tom případě, že TS skončí! Příklad:

$ echo 'X10(S7)00Y' | sed 's/.(S7)./(S7)/' |
sed 's/.(S7)./(S7)/' | sed 's/.(S7)./(S7)/' |
sed 's/(S7)/Stop/'
Stop
$

Tedy, ke každému TS dokážu vymyslet takové sedy, které spojením přes roury | dokáží nejaké slovo přepsat na „Stop“ jen v tom případě, že tento TS zastaví. Že by problém zastavení? :-)

Mám-li libovolný program, můžu ho zapsat do Turingova stroje. Mám-li Turingův stroj, mohu ho přepsat na sedový problém. No a kdybych byl schopen vyřešit sedový problém – jak jsem výše ukázal, má řešení jen v případě, že Turingův stroj, ze kterého jsem vycházel, zastaví, tak potom jsem schopen řešit i problém zastavení Turingova stroje, tedy problém zastavení, a to nejsem. Uf!

V tuto chvíli by se vám měla hlava zastavit anebo prasknout jako pumlíč. :-) Co vy na to?

Několik poznámek závěrem:

Věnováno Zuzance, která to nikdy nepochopí :-)
Autor není project-manager!