Aberații informatice
Mașini Turing cu bandă finită, compresie, etc (aberații informatice) Problema opririi mașinii Turing este nedecidabilă. Dacă nu știți despre ce vorbesc, atunci e bine să vă opriți aici. Vorbesc serios ! Tocmai când mă decisesem să scriu mai pe înțelesul oamenilor mi-a trăsnit o idee mult prea creață, poate și greșită (am cam uitat teoria de la Matematică - Informatică). Mașina Turing clasică operează cu un număr finit de stări și o bandă infinită. În realitate nu pot exista decât mașini (calculatoare) finite. Problema opririi unei mașini Turing cu bandă finită este însă decidabilă ! Demonstrația este simplă, mașina cu bandă finită are un număr finit de stări (chiar dacă foarte multe), iar după cel mult acest număr de tranziții va trebui să cicleze printr-o stare anterioară, deci va intra într-o buclă infinită. Dacă se oprește mai înainte, atunci ... se oprește, dacă nu atunci sigur nu se va opri niciodată.