Vlákno názorů k článku Nechte Go plavat, teď sviští Java od Cikáda - Neprogramuji dobrovolně ani v jednom. Ale kdybych si...
-
Neprogramuji dobrovolně ani v jednom. Ale kdybych si musel vybrat, tak sáhnu po Go, už jen kvůli neskutečné ukecanosti Javy.
K obsahu:
"...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í)"
Opravdu musí *Turingovsky* úplný jazyk podporovat tohle? If napíšu pomocí while, nebo naopak; tudíž stačí jedno z toho. Alokace na haldě a její čištění je podmínkou odkud? Necucá si tu autor trochu z prstu?
-
Jaroslav Tulach (neregistrovaný)
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 tenforz Céčka, Javy, a jiných odvozenin kde seforcyklus ambivalentně swhilecyklem). Na zacyklení potřebuje cyklus s dopředu neznámým počtem opakování. Tedy v nám vcelku známých jazycíchwhile.A co Haskell? Jasně, Haskell žádné
whilecykly 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í,
whilecykly, 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. -
No, raději bych operoval s pojem "se stejnou výpočetní silou jako Turingův stroj" (či něco takového), ale prosím. Turingův stroj může potřebovat měnit i stavy, ale prosím. Jenže
- if není potřeba, pokud mám while
- while nebo rekurze, to je vcelku jedno (ona by ta rekurze šla najít i v TS, pakliže bychom pracovali s "výpočtem" - ale ano, toto už je jedno)
- ano, obecně má Turingův stroj nekonečnou pásku, ale pro Turingovskou úplnost stačí dvě "políčka", na která mohu zapisovat neomezeně velká (řekněme třeba přirozená) čísla - takže ani ta "halda" není třeba (čištění už vůbec ne, prostě to přepíšu)
- mimochodem je to Turingovsky úplný, ne Turingově úplný (výjimečně je to i na odkazované wiki správně)Každopádně děkuji za odpověď. Upřímně jsem ji nečekal. :)
