Nepravda. Ten zmíněný důkaz něco říká o neomezeném stroji, který nemáme a nikdy mít nebudeme. Pokud je stroj jakýmkoli způsobem omezený, např. počtem atomů ve vesmíru, neříká o něm zmíněný Turingův objev vůbec nic. Protože o takovém stroji prostě a jednoduše nehovoří, stejně jako nehovoří třeba o maximálním možném množství žab v jihočeských rybnících. Že je Java turingovsky kompletní s tím souvisí jenom víceméně okrajově.
Čili argumentuješ chybně: z toho, co víme o halting problému pro TM, neplyne vůbec nic pro konkrétní algoritmus v javě běžící na nějakém reálném (nebo realisticky myslitelném) počítači.
Na reálném počítači to teoreticky řešitelné je, prakticky ale ne:
The halting problem is theoretically decidable for linear bounded automata (LBAs) or deterministic machines with finite memory. A machine with finite memory has a finite number of states, and thus any deterministic program on it must eventually either halt or repeat a previous state:
...any finite-state machine, if left completely to itself, will fall eventually into a perfectly periodic repetitive pattern. The duration of this repeating pattern cannot exceed the number of internal states of the machine... (italics in original, Minsky 1967, p. 24)
Minsky warns us, however, that machines such as computers with e.g., a million small parts, each with two states, will have at least 21,000,000 possible states:
This is a 1 followed by about three hundred thousand zeroes ... Even if such a machine were to operate at the frequencies of cosmic rays, the aeons of galactic evolution would be as nothing compared to the time of a journey through such a cycle (Minsky 1967 p. 25)
Což samozřejmě nevylučuje, že někdy někdo přijde s lepším řešením, jak to v rozumném čase rozhodnout, zatím se to ale nikomu nepovedlo.
998 Odpovědí
233668 Zhlédnutí