Hlavní navigace

Co je to nenaprogramovatelné?

Ondřej Holeček

Ani ten nejlepší programátor to nenaprogramuje, co je to? Kdo si myslí, že to už ví, jistě se alespoň pozastaví nad netradiční implementací známých problémů pomocí sedu.

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)?

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

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! 

Našli jste v článku chybu?

9. 10. 2013 9:56

SuchSoft (neregistrovaný)

Skús otvoriť v notepade 4 GB súbor :-)

24. 10. 2009 0:12

estonto (neregistrovaný)

V případě programů se vstupem od uživatele přece musí být parametrem funkce zastavi() i množina vstupů.

DigiZone.cz: Placené VoD a obsah zdarma

Placené VoD a obsah zdarma

DigiZone.cz: Co chtějí operátoři při přechodu na DVB-T2?

Co chtějí operátoři při přechodu na DVB-T2?

Podnikatel.cz: Přehledná titulka, průvodci, responzivita

Přehledná titulka, průvodci, responzivita

Podnikatel.cz: EET: Totálně nezvládli metodologii projektu

EET: Totálně nezvládli metodologii projektu

Lupa.cz: Kdo pochopí vtip, může jít do ČT vyvíjet weby

Kdo pochopí vtip, může jít do ČT vyvíjet weby

Vitalia.cz: Paštiky plné masa ho zatím neuživí

Paštiky plné masa ho zatím neuživí

Vitalia.cz: Jsou čajové sáčky toxické?

Jsou čajové sáčky toxické?

Lupa.cz: Proč firmy málo chrání data? Chovají se logicky

Proč firmy málo chrání data? Chovají se logicky

Měšec.cz: Air Bank zruší TOP3 garanci a zdražuje kurzy

Air Bank zruší TOP3 garanci a zdražuje kurzy

Vitalia.cz: „Připluly“ z Německa a možná obsahují jed

„Připluly“ z Německa a možná obsahují jed

Měšec.cz: U levneELEKTRO.cz už reklamaci nevyřídíte

U levneELEKTRO.cz už reklamaci nevyřídíte

120na80.cz: Na ucho teplý, nebo studený obklad?

Na ucho teplý, nebo studený obklad?

Podnikatel.cz: Snížení DPH na 15 % se netýká všech

Snížení DPH na 15 % se netýká všech

Vitalia.cz: Proč vás každý zubař posílá na dentální hygienu

Proč vás každý zubař posílá na dentální hygienu

Měšec.cz: mBank cenzuruje, zrušila mFórum

mBank cenzuruje, zrušila mFórum

DigiZone.cz: Rádio Šlágr má licenci pro digi vysílání

Rádio Šlágr má licenci pro digi vysílání

Vitalia.cz: Mondelez stahuje rizikovou čokoládu Milka

Mondelez stahuje rizikovou čokoládu Milka

Root.cz: Certifikáty zadarmo jsou horší než za peníze?

Certifikáty zadarmo jsou horší než za peníze?

Lupa.cz: Insolvenční řízení kvůli cookies? Vítejte v ČR

Insolvenční řízení kvůli cookies? Vítejte v ČR

Vitalia.cz: Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky

Láska na vozíku: Přitažliví jsme pro tzv. pečovatelky