U niektorých programov sa predpokladá dlhá doba výpočtu a tam je zistenie zložitejšie / nemožné a o takých programov nám ide.
Jako možná někde je, ale praktiky si to neumím moc dobře představit. Dlouhý výpočet se logicky vždycky skládá z nějakých iterací a měl by konvergovat nějakým směrem. Kontrolovat průběžně konvergenci bude v praxi nejspíš v 99.9% stačit...
A co ta ekvivalence programů?
A já si myslel, že jsme si složitě vysvětlili, že reálné počítače jsou FSM...
A pro některé programy je HP také trivka
Myslíš "pro všechny normální programy, se kterými se normální smrtelnk potká?"
Přitom Büchiho automat si v praxi jako HW nesestavíte
Mám takový matný pocit, že Zz-a by spíš zajímalo, co si díky znalosti TM
může sestrojit - což není nic, protože TM se hodí na důkaz toho, že něco nejde, ne naopak.
Možno nie až tak - akurát viem povedať, že to ušetrilo kopu peňazí na pokusy o implementáciu riešenia HP štýlom "skončí to do 25 dní, ale keď príde signál X, tak to skončí do 29 dní, inak to skončí do ...". Namiesto toho to aj po odstránení bugu môže riešiť pracovník pomerne úspešnou heurestikou ako "už druhý deň pravidelne bliká LED na zariadení a zdá sa, že sa to pomerne hreje, tak sa to asi zacyklilo".
No tak to je právě nesmysl. Víme, že pro FSM (kterému reálný HW odpovídá) je HP řešitelný, čili poznatek, že pro TM je neřešitelný, nám neušetřil ani halíř - protože prostě v praxi zjišťujeme, že něco, co by teoreticky mělo jít, nejde kvůli fyzickým omezením.
Takto teoreticky s tím nemám absolutně žádný problém. Jen bych to chtěl vidět na vlastní oči. I důsledky obecné teorie relativity se dají pozorovat v praxi, tak určitě půjde i tohle.
No dostal jsi tři případy něčeho, co nejde, a víme to díky TM. Nic víc čekat nemůžeš, TM je přesně na tohle - dokázat, že něco nejde ani na idealizovaném nekonečném počítači.
1675 Odpovědí
288428 Zhlédnutí