Aprilsnar: Et af verdens vigtigste programmeringssprog, C, er alligevel ikke et ægte programmeringssprog. Det konkluderer en gruppe amerikanske forskere efter at have gennemgået et mere end 40 år gammelt bevis.
»Vi har i årevis skudt genvej, når vi har bevist, at C var Turing-komplet. De antagelser, der ligger til grund for beviset, har vi ikke været tilstrækkeligt kritiske over for,« udtaler lektor Dennis Ritchie fra det datalogiske institut ved University of California i Davis ifølge en pressemeddelelse.
Sammen med kolleger fra University of South Florida har han gennemgået beviset for, at C er Turing-komplet.
For at være Turing-komplet skal et programmeringssprog populært sagt fungere ligesom en Turing-maskine, opkaldt efter datalogen Alan Turing. Men det har hidtil været antaget, at man kan nøjes med at bevise Turing-komplethed for en delmængde af funktioner, men det har forskerne nu vist er en fejlagtig antagelse.
Problemet med, om C teknisk set er Turing-komplet eller ej, har været bragt på banen før, idet en ægte Turing-maskine har ubegrænset hukommelse. Det er af gode grunde ikke tilfældet i praksis, men det har hidtil været praksis se bort fra det i beviser for Turing-komplethed.
Det er imidlertid ikke denne antagelse, som forskerne har fundet problemer med i C. Konkret handler det derimod om, at der er en familie af algoritmer, som C ikke altid håndterer korrekt, nemlig såkaldte Erlang-træer, der er opkaldt efter den danske matematiker Agner Krarup Erlang.
Og det er mere end blot et teoretisk problem, lyder det fra forskerne:
»Træerne bruges i firmwaren i eksempelvis telekommunikationsudstyr og i visse typer maskinoversættelse, men ingen har hidtil opdaget problemet. Sandsynligvis fordi, der har været mange andre potentielle fejlkilder,« udtaler Dennis Ritchie.
Konkret vil fejlene i, hvordan C gennemløber disse algoritmer, eksempelvis kunne udmønte sig i mobilopkald, der går tabt, eller forkert sammensætning af ord i maskinoversættelser.
Da C blev udviklet i begyndelsen af 1970'erne, var antagelserne for beviset for Turing-komplethed tilstrækkeligt, ikke mindst fordi fejlene først bliver relevante, når algoritmerne skal gennemløbes et meget højt antal gange.
Det kan være forklaringen på, at ingen har anfægtet antagelserne før nu.
»Det her er noget, hvor man måske vil se en fejl én ud af en trillion gange. Men kombinationen af Moores Lov og antallet af computere betyder, at dét, der var helt usandsynligt i 1970, i dag vil kunne ske hundredvis af gange hvert minut et sted i verden,« forklarer professor i datalogi Børge R. Christensen fra Syddansk Universitet til Version2.
Programmeringssprog behøver ikke være Turing-komplette, men ifølge Børge R. Christensen er det et problem, hvis man antager Turing-komplethed, hvor det reelt ikke er tilfældet.
De amerikanske forskere opfordrer nu til en gennemgang af andre programmeringssprog for samme fejl i Turing-beviset. Det kan nemlig meget vel vise sig, at den samme genvej, der blev skudt i beviset for Turing-komplethed i C, også er taget i beviserne for andre sprog.
»Vi kan risikere, at når vi går sprogene igennem med nye briller, så vil kun FORTRAN og måske COMAL være ægte Turing-komplette, fordi vi har gjort nogle antagelser, der ikke tog hensyn til Moores Lov og alle typer algoritmer,« siger Børge R. Christensen.
Han tilføjer, at det meget vel kan vise sig at være i sidste øjeblik, at problemet i C er opdaget.
»Med Internet of Things og computeres voksende rolle inden for eksempelvis medicinsk behandling og diagnosticering, så er der en reel risiko for, at denne smutter fra 1970'erne kunne koste menneskeliv. Hvis den viser sig at være skyld i Blue Screen of Death i Windows, så har den måske allerede gjort det,« slutter Børge R. Christensen.
