Dokaz da postoji barem jedan trivijalni računalni program koji ne može postojati

Najljepši matematički dokazi, god. 2, Maxime Coutte.

Prošlog tjedna članak je bio o "Jesu li neke beskonačnosti veće od drugih?" I argumentu dijagonale Cantor. Ovog tjedna želim podijeliti jedan od mojih najdražih problema teorijske informatike.

„Dijelovi sa četiri rana računala, 1962. S lijeva na desno: ENIAC ploča, EDVAC ploča, ORDVAC ploča i BRLESC-I ploča, pokazuju trend prema minijaturizaciji.“

Sjećam se još u srednjoj školi kad sam se počeo baviti informatikom, mislio sam da mogu teoretski riješiti bilo koji računski problem s pravim matematičkim alatima i programiranjem. Bio sam u krivu. Postoji teoretsko ograničenje za bilo koji računski stroj i ovdje ćemo vidjeti dokaz da postoji barem jedan logički problem koji niti jedan računalni program nikada neće moći riješiti.

Definiranje H, nemogućeg računalnog programa

Računalni program P (i) definiramo kao popis uputa P koji, kada se izvodi s ulazom i, daje izlaz o.

Na primjer,

je program koji zbroji dva broja koja dajete kao unose i,

je program koji koristi drugi program - P_add - kao ulaz i koji prolazi ovom programu dva druga ulaza. Čini ono što P_add (a, b) čini i udvostručuje.

Kada se program izvrši, može se zaglaviti, pokrenuti zauvijek i nikada ništa ne ispisati, na primjer, program P_sum koji nastavi do zbroja svih prirodnih brojeva nastavit će dodavati prirodne brojeve zauvijek, a da se ikada ne završi (tj. Zaustavi) i ispis rezultata.

Pretpostavimo da postoji program H (P, i) koji kao ulaz uzima popis uputa P programa P (i) i i ulaz P (i), a izlaz 1 ako P (i) zaustavi se u nekom trenutku i 0 ako se P (i) zaglavi i pokrene zauvijek. Jednostavno rečeno,

Zašto popis logičkih uputa ne može postojati

Na temelju dokaza Alana Turinga u radu "Na računarnim brojevima, s aplikacijom na Entscheidungsproblem" -1937, dokazat ćemo da H ne može postojati.

Na temelju pretpostavke da H postoji konstruiramo program X (P) koji se izvodi zauvijek ako i samo ako je H (P, P) = 1 i zaustaviti ako i samo ako je H (P, P) = 0. Drugim riječima,

Sada dajemo X (i) vlastiti popis uputa X kao ulaz: X (X).

Stoga se X (X) pokreće zauvijek ako i samo ako H (X, X) = 1 i X (X) prestanu ako i samo ako je H (X, X) = 0. Drugim riječima,

Imamo kontradikciju! Reductio ad absurdum je pokazao da H ne može postojati jer njegovo postojanje dovodi do apsurdnih zaključaka.

Stoga je računalni program koji može utvrditi hoće li se neki računalni program s bilo kojim ulazom zaglaviti i zauvijek pokrenuti ili završiti s pokretanjem. Postoji barem jedan računalni program koji rješava logički problem koji ne može postojati.

Upućivanje, Alan Turing. "Na računarnim brojevima, s aplikacijom na Entscheidungsproblem". 1937.

Ja sam Maxime Coutte, suosnivač Relativty.com-a, VR slušalice koju sam dizajnirao od početka, od čega sam otvorio izvorni kod i hardver. Obožavam učiti i zanima me veliki broj predmeta.
Možete me pratiti na Twitteru @maximecoutte.