Tõestus selle kohta, et on olemas vähemalt üks triviaalne arvutiprogramm, mida ei saa eksisteerida

Kõige ilusamad matemaatilised tõendid, vol. 2, Maxime Coutte.

Eelmise nädala artikkel oli teemal “Kas mõned lõpmatused on suuremad kui teised?” ja Cantori diagonaali argument. Sel nädalal tahan jagada ühte oma lemmikteoreetilisest arvutiteaduse probleemist.

Mäletan juba keskkoolis, kui hakkasin arvutiteadust tegema, arvasin, et saaksin teoreetiliselt lahendada mis tahes arvutusliku probleemi õigete matemaatiliste tööriistade ja programmeerimisega. Ma eksisin. Mis tahes arvutusmasina jaoks on teoreetiline piirang ja siin näeme tõestust, et on olemas vähemalt üks loogikaprobleem, mida ükski arvutiprogramm ei suuda kunagi lahendada.

H, võimatu arvutiprogrammi määratlemine

Me määratleme arvutiprogrammi P (i) juhiste loendina P, mis sisendiga i täidetuna annavad väljundi o.

Näiteks,

on programm, mis summeerib kaks numbrit, mille olete sellele sisendina andnud, ja

on programm, mis kasutab sisendina teist programmi - P_add - ja edastab sellele programmile veel kaks sisendit. See teeb seda, mida P_add (a, b) teeb ja kahekordistab.

Kui programm on käivitatud, võib see takerduda, töötada igavesti ja mitte kunagi midagi välja anda, näiteks jätkab P_sum, mis liigub kõigi naturaalarvude summaga, naturaalarvude lisamist igavesti, ilma et see kunagi lõpetaks (st peatuks) ja tulemuse väljastamine.

Oletame nüüd, et eksisteerib programm H (P, i), mis võtab sisendina programmi P (i) ja i juhiste P loendi P (i) sisendi ning väljastab a 1, kui P (i) peatu mingil hetkel ja 0, kui P (i) takerdub ja jookseb igavesti. Lihtsamalt öeldes:

Miks ei saa loogiliste juhiste loetelu olla?

Tuginedes Alan Turingi tõendile artiklis 193 arvutatud numbrite kohta koos rakendusega Entscheidungsproblemile, tõestame, et H ei saa eksisteerida.

Lähtudes eeldusest, et H eksisteerib, konstrueerime programmi X (P), mis töötab igavesti ainult siis, kui H (P, P) = 1, ja peatub siis ja ainult siis, kui H (P, P) = 0. Teisisõnu,

Nüüd võime kaaluda X (i) sisendina oma juhiste X loendi andmist: X (X).

Seetõttu töötab X (X) igavesti ainult siis, kui H (X, X) = 1 ja X (X) peatub ainult siis, kui H (X, X) = 0. Teisisõnu,

Meil on vastuolu! Reductio ad absurdum näitas, et H ei saa eksisteerida, kuna selle olemasolu viib absurdsete järeldusteni.

Seetõttu pole arvutiprogramm, mis suudab kindlaks teha, kas mõni sisendiga arvutiprogramm jääb ummikusse ja töötab igavesti või lõpetada, on võimatu. Loogikaprobleemi lahendamiseks on olemas vähemalt üks arvutiprogramm, mida ei saa eksisteerida.

Viited, Alan Turing. “Arvutatavate numbrite korral rakendusega Entscheidungsproblemile”. 1937.

Olen Max Coutte, Relativty.com-i kaasasutaja, VR-peakomplekt, mille kujundasin nullist, millest ma Open-hankisin koodi ja riistvara. Jälgi mind Twitteris @maxcoutte.