Et bevis på, at der mindst er et trivielt computerprogram, der ikke kan findes

De smukkeste matematiske bevis, vol. 2, Maxime Coutte.

Sidste uges artikel handlede om ”Er nogle infiniteter større end andre?” og Cantor Diagonal-argumentet. Denne uge vil jeg dele et af mine foretrukne teoretiske computervidenskabsproblemer.

”Dele fra fire tidlige computere, 1962. Fra venstre mod højre: ENIAC-kort, EDVAC-kort, ORDVAC-kort og BRLESC-I-kort, der viser tendensen mod miniaturisering.”

Jeg kan huske tilbage i gymnasiet, da jeg begyndte at lave datalogi, jeg tænkte, at jeg teoretisk kunne løse ethvert computerstatisk problem med de rigtige matematiske værktøjer og programmering. Jeg tog fejl. Der er teoretisk begrænsning for enhver computermaskine, og her vil vi se beviset på, at der er mindst et logikproblem, som intet computerprogram nogensinde vil være i stand til at løse.

Definition af H, det umulige computerprogram

Vi definerer et computerprogram P (i) som en liste over instruktioner P, der giver et output o, når det udføres med en input i.

For eksempel,

er et program, der summerer de to numre, du giver det som input, og

er et program, der bruger et andet program - P_add - som input, og videregiver dette program de to andre input. Det gør hvad P_add (a, b) gør og fordobler det.

Når et program udføres, kan det sidde fast, køre for evigt og aldrig udsende noget, for eksempel et program P_sum, som fortsætter til summen af ​​alle naturlige numre, fortsætter med at tilføje naturlige tal for evigt uden nogensinde at afslutte kørsel (dvs. stoppe) og viser resultatet.

Lad os nu antage, at det findes et program H (P, i), der tager en input som listen over instruktioner P i programmet P (i) og i input fra P (i), og udsender en 1, hvis P (i) standse på et tidspunkt og 0, hvis P (i) sidder fast og løber for evigt. For at sige det enkelt,

Hvorfor listen over logiske instruktioner H muligvis ikke findes

Baseret på Alan Turing's bevis i papiret ”On computable numbers, with a application to Entscheidungsproblem” -1937, vil vi bevise, at H ikke kan eksistere.

Baseret på antagelsen om, at H eksisterer, konstruerer vi et program X (P), der kører for evigt, hvis og kun hvis H (P, P) = 1 og standser hvis og kun hvis H (P, P) = 0. Med andre ord,

Vi kan nu overveje at give X (i) sin egen liste over instruktioner X som input: X (X).

Derfor kører X (X) for evigt, hvis og kun hvis H (X, X) = 1 og X (X) standser hvis og kun hvis H (X, X) = 0. Med andre ord,

Vi har en modsætning! Vi har vist af Reductio ad absurdum, at H ikke kan eksistere, da dens eksistens fører til absurde konklusioner.

Derfor er et computerprogram, der kan bestemme, om et hvilket som helst computerprogram, der får noget input, sidder fast og kørt for evigt eller færdig med at køre, er umuligt. Der er mindst et computerprogram, der løser et logikproblem, der umuligt kan eksistere.

Referencer, Alan Turing. “På computbare numre, med en applikation til Entscheidungsproblemet”. 1937.

Jeg er Max Coutte, medstifter af Relativty.com, et VR-headset, jeg designede fra bunden, hvoraf jeg åbnede koden og hardware. Følg mig på Twitter @maxcoutte.