Názor k článku Nechte Go plavat, teď sviští Java od Jaroslav Tulach - Otálel jsem jak jsem mohl, ale nechci vypadat,...

Otálel jsem jak jsem mohl, ale nechci vypadat, že se vyhýbám odpovědi. Přesto si myslím, že tohle by bylo lepší na diskuzi u piva. Zkusím něco napsat, ale obávám se, že to povede spíš na babylon neporozumění...

Podle základní informatické teze ze třicátých let minulého století má být Univerzální Turingův stroj schopen simulovat jakýkoliv počítač či jazyk. Neboť Turingův stroj je svého druhu počítač, tak jazyk jenž se zve Turingovsky úplným musí být schopný simulovat Turingův stroj. Tak a co teď z toho vyvodit?

Turingův stroj musí být schopen rozhodnout jestli posune pásku doleva či doprava. Na to potřebujete něco, co se v běžných jazycích jmenuje if.

Turingův stroj má nekonečnou pásku. Dopředu nejde odhadnout jak velkou pásku budete potřebovat. To znamená, že v Céčku, Javě a podobných jazycích je potřeba postupně alokovat paměť. Máte pravdu, čištění potřeba není. Stačí mít té paměti dost a nebo ji čistit automaticky a nebo ji znovu využívat.

A nakonec cykly: jak moc mocné musí být? Asi nejznámější důsledek Turingovy formalizace počítacího stroje je takzvaný "halting problém". Tedy neschopnost strojově (Turingovsky) analyzovat kód a rozhodnout jestli něco vypočítá a nebo se zacyklí. Což znamená, že Turingovsky úplný jazyk se musí umět zacyklit. Ač se nám to často stává, tak to zase není tak jednoduché. Nestačí if, nestačí for (cyklus s pevným počtem opakování jako v Pascalu, ne ten for z Céčka, Javy, a jiných odvozenin kde se for cyklus ambivalentně s while cyklem). Na zacyklení potřebuje cyklus s dopředu neznámým počtem opakování. Tedy v nám vcelku známých jazycích while.

A co Haskell? Jasně, Haskell žádné while cykly nemá. Je Turingovsky úplný? Ano, je. Jak to dělá? Rekurzí. Turingův stroj rekurze nemá (vše se píše do jedné funkce - žádná volání tam nejsou). Ale už od třicátých let minulého století se ví, že to je výpočetně stejně silné.

Tolik k vysvětlení, proč jsem si dovolil napsat, že "...každý Turingově úplný jazyk musí podporovat (if větvení, while cykly, přístup do paměti, alokaci na haldě či její čištění)". Zbytek bych raději řešil si dostatečným alkoholem v krvi.