Teorema lui Turing
Această intrare sau secțiune despre subiecte de matematică și algoritmi nu citează sursele necesare sau cei prezenți sunt insuficienți . |
Teorema lui Turing afirmă existența unor probleme indecidabile, adică pentru care nu există un algoritm capabil să ofere un răspuns în timp finit în toate cazurile problemei. Dovada acestui rezultat se datorează Alan Turing , care a dovedit într - un articol din 1937. Turing Teorema este într - un anumit sens , „versiunea de calculator“ a impreciziei lui Gödel teorema .
Demonstrație
Un indiciu de dovadă este dat mai jos.
Să presupunem că avem unele programe care imprimă întotdeauna fie "da", fie "nu" în ieșire, indiferent de intrarea lor. Problema noastră va fi definită după cum urmează:
- Dat în formă de cod un program P care imprimă întotdeauna „da” sau „nu” și o intrare I, stabiliți ieșirea P (I).
Vom arăta absurd că nu există un algoritm capabil să ofere un răspuns pentru toate perechile posibile (P, I) de programe și intrări. Să presupunem deci absurditatea existenței unui program care, luând codul unui alt program P, ne spune dacă tipărește „da” sau „nu” când primește o anumită intrare I; intrarea programului nostru ipotetic este deci o pereche (P, I), în timp ce ieșirea este P (I). Noi numim acest program . Acum să modificăm ușor programul crearea unui nou program care ia ca intrare codul unui program P și apoi calculează ; acest nou program determină ce imprimă P atunci când primește propriul cod ca intrare. În acest moment, să îl modificăm din nou ușor astfel încât să tipărească „nu” când programul analizat tipărește „da” și invers; numim acest program N (inexistent); observăm că acesta este un program care imprimă întotdeauna fie „da”, fie „nu”. În acest moment, să ne întrebăm în mod legitim:
- Ce tipărește N când primește N ca intrare?
Practic, oferim lui N ca intrare pentru sine, cerându-i astfel să ne spună ce ar face el însuși primindu-se ca intrare. Acum, dacă copia lui N care este analizată imprimă „da” când primește N ca intrare, atunci programul analizor N, care tocmai a primit N ca intrare, ar imprima „nu”; dar acest lucru este absurd. În schimb, dacă N-ul analizat ar tipări „nu”, atunci N ar imprima „da”; dar și asta este absurd. Prin urmare, un astfel de program nu poate exista.
Versiunea originală a dovezii lui Turing se bazează de fapt pe problema opririi , numită și problema opririi ; adică arată că nu poate exista un program care să poată decide dacă vreun program se oprește sau continuă să continue la nesfârșit.
O demonstrație mai formală necesită unele noțiuni de informatică teoretică, cum ar fi cunoașterea limbajelor formale și a mașinilor Turing .
