Aprilsnar: Datalogisk brøler - C er alligevel ikke Turing-komplet

Beviset for, at C er et Turing-komplet programmeringssprog, indeholder en lille, men afgørende fejl, lyder det fra amerikansk forskerhold. Det kan være kritisk i moderne computere, vurderer professor.

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.

Tips og korrekturforslag til denne historie sendes til tip@version2.dk
Kommentarer (50)
sortSortér kommentarer
  • Ældste først
  • Nyeste først
  • Bedste først
Jacob Christian Munch-Andersen

Kender I det når man diskuterer programmeringssprog og påpeger at C++ ikke har en bestemt feature? Så kommer der altid nogen og fortæller hvordan man på en smart måde kan implementere den feature, så C++ har den alligevel, hvis man lige bruger sproget rigtigt.

Det virker bare aldrig særlig godt i praksis, hvilket er totalt uforståeligt, men med den her opdagelse giver det pludselig mening, så jeg tror godt vi kan konkludere at fejlen ikke kun findes i C.

Troels Henriksen

Tak; det er sgu godt at vi har nogen til at redde os når vi er lige ved at falde i.

Jeg har dog hørt det anfægtet, helt alvorligt, at C faktisk ikke er Turing-komplet. Det er baseret på at enhver peger kan konverteres til en void-peger (eller en uintptr_t) og tilbage igen, og disse har kun en endelig størrelse. Korrolaret er at der i et givet C-program kun kan eksistere et begrænset antal objekter, da de skal kunne tælles med en uintptr_t, der er et heltal bestående af et fast antal bit. Idet en forudsætning for Turing-komplethed er evnen til at håndtere vilkårlig meget data, er C følgeligt ikke Turing-komplet.

Jeg er ikke nok af en sprogjurist til at kunne afgøre om det passer. Mig bekendt siger C-specifikationen ikke noget om at stakken skulle være begrænset i størrelse, og måske ville det være en gyldig implementering at lade stakken vokse uden grænse, så længe man ikke tager addressen på nogen stak-erklæret variabel. Spørgsmålet er så, om man med denne begrænsning på anden vis har givet tab på Turing-komplethed, men jeg tvivler: Hvis blot man har rekursion og en eller anden form for betinget afvikling, så plejer Turing-komplethed at dukke op ret hurtigt.

Mikkel Lauritsen

Jeg har dog hørt det anfægtet, helt alvorligt, at C faktisk ikke er Turing-komplet. Det er baseret på at enhver peger kan konverteres til en void-peger (eller en uintptr_t) og tilbage igen, og disse har kun en endelig størrelse.

Well, i og med at en turingmaskine har en uendelig lang papirstrimmel til rådighed er der ingen programmeringssprog i den virkelige verden, som er helt stringent turingkomplette - de må nøjes med at køre på maskiner, som har endelig hukommelse. I praksis ser man dog nok bort fra den restriktion, hvis man vil gøre begrebet "turingkomplet" praktisk anvendeligt...

Troels Henriksen

Well, i og med at en turingmaskine har en uendelig lang papirstrimmel til rådighed er der ingen programmeringssprog i den virkelige verden, som er helt stringent turingkomplette - de må nøjes med at køre på maskiner, som har endelig hukommelse. I praksis ser man dog nok bort fra den restriktion, hvis man vil gøre begrebet "turingkomplet" praktisk anvendeligt...

Det er irrelevant - det er fuldt ud muligt at lave (f.eks.) en Haskell-maskine, der blot beder operatøren om at gå ud og købe mere papirstrimmel hvis der løbes tør, og holder pause indtil den ekstra strimmel klistres på. Langt de fleste højniveauprogrammeringssprog kan implementeres sådan, da der i selve sproget ikke er nogen begrænsning på mængden af data der kan behandles. Det er her jeg mener C er lidt usædvanligt, idet der er en grænse for antallet af objekter der kan optælles i sproget.

Grænsen er naturligvis stadigvæk så høj at det ikke har nogen som helst praktisk konsekvens - det er mest bare teoretisk tankespind. Men for enhver konkret C-implementering, vil der findes et program der kan afvikles på en Turing-maskine, men som ikke kan afvikles på denne implementering: et program der kræver mere end 2**(sizeof(void*)) byte lager. I praksis ville man også kunne udnytte filsystemet til ekstra lagerplads, men her er også en grænse, tror jeg: Der findes kun en endelig mængde filer, idet der er en maksimal længde på filstier (om ikke andet, så den maksimale længde på et array), og hver fils maksimale størrelse er begrænset af den endelige størrelse på fil-offset-typen. Der er selvfølgeligt tale om en fuldstændigt astronomisk mængde lager man kan tilgå, selvom den er endelig, så igen er det kun en teoretisk overvejelse.

Per Erik Rønne

Skal vi ikke diskriminere mellem programmeringssprog - og så implementeringer af programmeringssprog?

I et programmeringssprog kan man da godt regne med et vilkårligt stort lager. I en implementering derimod vil der altid være en grænse.

Også i en Turingmaskine-implementering ...

Mikkel Lauritsen

Grænsen er naturligvis stadigvæk så høj at det ikke har nogen som helst praktisk konsekvens - det er mest bare teoretisk tankespind.

My point exactly. Det er lidt noget sofisteri at hævde, at C grundet pointere med fast størrelse ikke er turing-komplet, fordi alle i praksis forekommende programmer skrevet i andre sprog har en tilsvarende udfordring - at maskinen, som programmet eksekveres på, er endelig.

Og ja; programmer skrevet i sprog, som ikke har pointere, kan i princippet overføres i kørende udgave til en maskine med en bredere adressebus, hvis man løber tør for hukommelse.

Ivo Santos

Nu er det jo således at C er i stand til at udnytte al den ram der findes i en pc, i øvrigt er det således at nu hvor de fleste cpu'er og operativ systemer er overgået til 64 bit, så er størrelsen på en pointer i C og vel også i C++ på 64 bit, s intet nyte under solen der.

Ellers en sjov aprilsnar.

Jens Henrik Sandell

ikke mindst fordi fejlene først bliver relevante, når algoritmerne skal gennemløbes et meget højt antal gange.

Et proof kan aldrig være betinget af antallet af gennemløb.

Nu er spørgsmålet egentlig: Kan Jesper tage æren for den dybsindige og meget lange forklaring, eller er det noget der er sakset fra et andet medie.
Jeg synes at denne artikel fortjener anerkendelse; 8 point for det kunstneriske udtryk!

Baldur Norddahl

Min pointe er netop at C-sproget er specificeret således at dette ikke er tilfældet. Eller har du gennemskuet en spidsfindighed der gør det muligt?

Ja det er dybest set noget vrøvl. Du behøver ikke bruge pointere til at referere til data. Du kan eksempelvis også bruge heltal. Og du behøver ikke bruge de indbyggede heltalstyper, man kan bruge arbitrær størrelse heltal typer. Hvis du ikke selv kan finde ud af at implementere en sådan type, så kan du bare bruge et bibliotek til det.

Du er ikke begrænset af RAM da data kan være på en harddisk. Og filsystemet er dybt irrelevant da det dels ikke er en del af sproget C og dels kan du bare tilgå det rå blok device og dermed arbejde uden et filsystem. Hvis du løber tør for harddisk kan du bede operatøren om at skifte harddisk undervejs.

Men det endelige bevis er ganske simpelt. Det er ligetil at skrive en turingmaskine simulator i C. Derfor er C turing komplet. En turingmaskine arbejder med et bånd der kan spoles et trin frem eller et trin tilbage ad gangen. C har derfor ikke brug for at kunne tælle til mere end 1 for at kunne simulere en turingmaskine med uendeligt stort lager. Programmet kan bruge fseek() funktionen til at skifte position 1 frem eller 1 tilbage i en fil uden at programmet behøver vide noget som helst om hvor stor denne fil er.

Troels Henriksen

Jeg tror du misforstår min oprindelige problemstilling: Jeg kigger kun på C som specificeret som sprog. Det er et intellektuelt puslespil, ikke en reel kritik eller ingeniørmæssig udfordring, eller noget i den stil. Det vil jeg gerne understreje, for det lader til at mange synes at tage mit tanke-eksperiment som en fornærmelse eller kritik af C, hvilket det ingenlunde er tiltænkt som. Jeg tænkte blot vi kunne få noget sjov ud af tråden efter aprilsnaren blev afsløret lidt tidligt.

Det handler mest om at finde et "hul" i standarden der tillader Turing-komplethed, til trods for at C ser ud som om det har en (omend astronomisk høj) grænse for hvor meget lager et program har adgang til. Jeg snakker på ingen måde om RAM - det er en implementeringsdetalje, og jeg tror slet ikke den virtuelle maskine, som sproget C er defineret i forhold til, har det begreb. (Men igen, jeg er ingen stor sprogjurist.)

Du behøver ikke bruge pointere til at referere til data.

Er vi enige om at man i C kan tage addressen på ethvert objekt/værdi, og at denne addresse skal kunne konverteres til og fra uintptr_t uden tab af information, og at uintptr_t er defineret som havende en statisk størrelse jvf. at sizeof(uintptr_t) er defineret og at CHAR_BITS er endelig? Hvis jeg har ret i denne analyse, så har man nødvendigvis en grænse for hvor mange C-objekter/værdier (det er måske lidt forvirrende at C-specifikationen faktisk definerer "objekt", selvom det ikke er OOP-konceptet) man kan have i lager samtidigt, da hvert skal have et unikt "tal".

Du er ikke begrænset af RAM da data kan være på en harddisk. Og filsystemet er dybt irrelevant da det dels ikke er en del af sproget C og dels kan du bare tilgå det rå blok device og dermed arbejde uden et filsystem. Hvis du løber tør for harddisk kan du bede operatøren om at skifte harddisk undervejs.

Jeg skrev jo netop også at filsystemsfunktionerne måske var udvejen, men jeg var usikker, idét filer jo skal identificeres ved et filnavn, og hvis C kun kan repræsentere et endeligt antal af disse (idet filnavnene også skal lagres et sted), så ved jeg ikke om det er nok. Måske hvis man kan udnytte undermapper på en snedig måde...

Men det endelige bevis er ganske simpelt. Det er ligetil at skrive en turingmaskine simulator i C. Derfor er C turing komplet. En turingmaskine arbejder med et bånd der kan spoles et trin frem eller et trin tilbage ad gangen. C har derfor ikke brug for at kunne tælle til mere end 1 for at kunne simulere en turingmaskine med uendeligt stort lager. Programmet kan bruge fseek() funktionen til at skifte position 1 frem eller 1 tilbage i en fil uden at programmet behøver vide noget som helst om hvor stor denne fil er.

Jeg er enig! Konstruktionen af et sådan program er det bedste bevis. Min tese er at det ikke er nemt at konstruere et sådan program hvis man går i ekstremer. Dit forslag om at bruge én fil fejler, da C har en implicit grænse for hvor store filer der kan tilgås, idet typen der bruges til at repræsentere filoffset (long int, så vidt jeg kan se) har en endelig størrelse. Fil-offsets i C er nemlig ikke helt relative, da man altid skal kunne bede om et "absolut" offset via ftell().

Baldur Norddahl

Er vi enige om at man i C kan tage addressen på ethvert objekt/værdi,

Nej det er vi ikke enige om. Du kan naturligvis få adressen på ting der måtte ligge i RAM i den aktuelle process, men der er ingen der siger at data skal være i RAM. Det kan eksempelvis være i en fil. Funktionen fseek kan navigere rundt i arbitrære store filer da den kan navigere relativt (1 byte frem eller 1 byte tilbage).

Gamle 16 bit DOS programmer er eksempler på programmer der kan tilgå filer der er større end pointerstørrelsen.

Troels Henriksen

Nej det er vi ikke enige om. Du kan naturligvis få adressen på ting der måtte ligge i RAM i den aktuelle process, men der er ingen der siger at data skal være i RAM. Det kan eksempelvis være i en fil. Funktionen fseek kan navigere rundt i arbitrære store filer da den kan navigere relativt (1 byte frem eller 1 byte tilbage).

Som jeg skrev ovenfor, så er fseek()-søgninger i virkeligheden ikke relative, men absolutte, idet det kræves at man for enhver filposition skal kunne få et gyldigt absolut offset tilbage med ftell(), og ftell() returnerer et tal med begrænset størrelse.

Min mistanke er også at vejen ud af lager-"manglen" ligger i filsystemet (som du selv siger er det trick blevet brugt før), men jeg er endnu ikke sikker på hvordan. Jeg er dog sikker på at brugen af én fil ikke er tilstrækkeligt hvis man vil tilgå vilkårligt meget data. Jeg er helt med på at én fil er nok til enhver praktisk brug (og et 64-bit addresserum er sikkert også nok i praksis, for den sags skyld), men nu er det et teoretisk tanke-eksperiment der handler om at fluekneppe C-standarden. :-)

Baldur Norddahl

Fil-offsets i C er nemlig ikke helt relative, da man altid skal kunne bede om et "absolut" offset via ftell().

Kan du komme med en henvisning til C specifikationen hvor der står at man altid skal kunne bruge ftell? Det er som udgangspunkt noget vrøvl:

1) C er ikke operativsystemet eller standard biblioteket.
2) Alle unix programmer kommer med 3 filhandles som ikke har en størrelse eller position: standard input, standard output og standard error.
3) Hvis fseek forvirrer dig, så lad os gemme data med en socket til en cloud server hos Google og vi ved alle hvor meget plads de har...

Baldur Norddahl

Jeg arbejdede i øvrigt en gang med en tapestreamer hvor det kun var muligt at bruge relative seeks. Tingsten anede simpelthen ikke hvor den var på båndet, så absolute seeks var ikke muligt andet end at man kunne bede den om at spole til starten af bånden. Men spørge om hvor den var? Du fik bare -1 tilbage.

Har du set billeder af de gamle båndstationer hvor de fylder bånd på manuelt? Der er ingen grænse hvor mange gange operatøren kan skifte bånd. Enten løber venstre båndkassette tør eller også er det højre side der løber tør og så er det tid for en operatør at skifte til næste eller forrige bånd - set fra programmet er det et ægte uendeligt bånd - og det program kunne meget vel være programmeret i C.

Troels Henriksen

Du har ret med ftell() - den må faktisk godt fejle med en eller anden system-specifik fejlkode, som velsagtens kunne være "desværre makker, filer på det her system er mærkelige så vi kan være Turing-komplette".

Jeg har ikke råd til C-specifikationen, så jeg har til at forsøge at gennemskue hvad man kan slippe afsted med kigget her: http://www.cplusplus.com/reference/cstdio/ftell/

Her kan man læse: "For text streams, the numerical value may not be meaningful but can still be used to restore the position to the same position later using fseek (if there are characters put back using ungetc still pending of being read, the behavior is undefined)." Den sætning står dog ikke i manualsiden på mit GNU/Linux-system, så hvem ved.

Jeg tror at biblioteksfunktionerne i standardbiblioteket er at opfatte som en del af C, men jeg er faktisk ikke helt sikker på hvordan standarden specificerer den detalje.

Jeg tror i øvrigt jeg har fundet en mere elegant løsning end filsystemer. Jeg synes den lugter lidt fordi det er utroligt implementeringsspecifikt, og hvis man udnytter den slags, så kan man bare definere den implementeringsdetalje at hvis man åbner filen "token-turing" starter en fortolker for et kendt Turing-komplet sprog. Det virker lidt dovent...

Nå, men min nye idé: Mange højniveausprog understøtter vilkårligt store heltal, og i disse kan man nemt påvise Turing-komplethed ved argumentere for at man blot kan Gödel-indkode al sin data i et gigantisk heltal. Det er smart! Den går ikke i C, da jeg mener C kræver endelige størrelser for alle heltal (dvs. der skal være et "største heltal", omend det kan være meget stort). Dog tror jeg ikke C stiller det krav til float/double-typerne, og de behøver ikke engang overholde IEEE-standarden. Hvis min mistanke er sand (er der nogen her der har råd til C-specifikationen og kan tjekke efter?), så kunne man lave en C-implementering hvor en 'float' er repræsenteret som et par af to heltal der kan være vilkårligt store (altså, som en brøk). Således ville man kunne indkode vilkårligt meget data ved at Gödel-nummere det på venstresiden af decimaltegnet i en enkelt 'float'-variabel! En sådan implementering synes både at overholde sprogets ånd, og er samtidigt triviel Turing-komplet.

Jeg synes dog også din idé med at udnytte de prædefinerede stdin/stdout-strømme er interessant. Gad vide om man kunne definere de to som værende asynkront forbundne, således at man kunne bruge dem som en vilkårligt stor buffer. Det ville være en ret sjov løsning.

Troels Henriksen

Kan nogen hos Version2 i øvrigt forklare hvorfor serveren afviser min kommentar, hvis den indeholder navnet på den funktion i C man bruger til at åbne en fil? Altså, den funktion hvis navn starter med "f" og som derefter har "open"? Når jeg prøver, så får jeg denne fejl:

The requested URL was rejected. Please consult with your administrator.

Your support ID is: 3167237961768388151

Er det et vulgaritets-filter der forsøger at beskytte os mod beskidte funktionskald?

Morten Faurholt

Troels ang. 2(sizeof(void*)) så mener du vel 2(8*sizeof(void*)) bytes lager :-)

Anyway, jeg sidder og tænker på om der er smuthul. Forestil dig en C fortolker(der måske er et program der afvikles på en "ægte Turing-maskine" d.v.s. med uendelig meget plads) der afvikler det givne C program. Til at starte med lægger fortolkeren sig fast på én bestemt endelig værdi af sizeof(void*) og iøvrigt størrelsen af andre typer, og oplyser disse værdier til programmet på forlangende. Hvis det på noget tidspunkt sker at programmet allokerer så meget data, at størrelsen på adresserummet ikke er tilstrækkelig, så vil C fortolkeren stoppe programmet, og oprette et nyt adresse-rum med endnu større-pointere (f.eks. dobbelt så lange) og passende justering i typer. Den vil herefter simulere afviklingen af det oprindelige program igen og vil nu oplyse de nye størrelser til programmet. På et tidspunkt når simuleringen til punktet hvor programmet tidligere blev stoppet og afviklingen vil herefter kunne fortsætte idet der nu er mere plads. Det kan selvfølgelig tage lang tid, men kun endelig tid. Proceduren gentages hvis man igen løber tør for lager. Dette kan endda lade sig gøre i en model med simpel I/O (f.eks. kommunikation med brugeren via en konsol) idet C fortolkeren blot skal genspille alt input fra slutbrugeren overfor programmet. Fortolkeren skal også gemme alt tidligere output så den på passende vis kan "undertrykke" det initielle output så det ikke vises for slutbrugeren igen. Da fortolkeren jo selv har uendelig meget plads til rådighed, er det ikke noget problem at gemme alt det foregående input. Fra brugerens synspunkt vil alt se ud som om programmet virkelig har uendelig meget plads til rådighed, pånær at der er nogle pauser ind imellem, men det kender man jo også fra andre programmeringssprog med garbage collection og dynamiske arrays.

Man kunne nu have den indvending, at dette kan give problemer for programmer hvor de konkrete størrelser af pointere m.m. påvirker programmets opførsel, og som derved vil opføre sig anderledes under de efterfølgende gennemløb og evt. ikke printe samme output ud - hvorved det bliver umuligt for fortolkeren at finde ud af hvad der er nyt/gammelt output. Det kan jo også være programmet går helt ind i helt andre forløb. Disse programmer vil ikke kunne afvikles korrekt, så opførslen må være udefineret. Det er derimod ikke noget problem at programmet aktivt bruger sizeof f.eks. til at allokere storage med malloc() eller implicit ved erklæring af structs osv. idet det hele jo justeres med ved de efterfølgende afviklinger. Så man er blot nødt til at lave den restriktion at programmet skal fungere ens uafhængigt af størrelsen af de forskellige typer og blot "samarbejde med systemet" d.v.s. allokere plads ud fra hvad den får oplyst af sizeof() m.m. Men det virker som en rimelig restriktion når man stiller krav om Turing-komplethed. Og under alle omstændigheder vil det være muligt at skrive et C program der overholder denne restriktion, og som samtidigt implementerer en universel Turing-maskine (inkl. uendeligt bånd) :-) F.eks. en UTM der indlæser specifikationen for en anden maskine fra standard input, simulerer afviklingen heraf, og printer slut-tilstanden ud (hvis ellers den indlæste Turing-maskine terminerer). Dermed er det vist at C er Turing-komplet, idet det er muligt at implementere en Turing-maskine i sproget (forudsat at implementationen af C understøtter uendelig storage, f.eks. via algoritmen ovenfor).

Morten Faurholt

Man kan selvfølgelig også forlænge lageret til uendelig via de principper som Baldur/Troels diskuterer, men her kan man dog sige det er snyd, idet det ikke er sproget i sig selv, men blot hjælpebiblioteker, som mit forslag ikke betjener sig af. Man behøver ikke engang malloc for mit forslag idet man kan lade programmet anvende rekusion m.m. til at allokere dynamiske mængder af lager (som så i praksis er implementeret ved re-gennemløbs-strategien nævnt ovenfor).

Finn Glamhøj

Hvis man har en computer med et RAM lager der overstiger det maksimale der kan adresseres med en C-pointer må man formode at man har adgang til et "segmentregister" som kan anvendes til at tilgå den del af RAM-hukommelsen som man ikke kan tilgå direkte – er resten så ikke et spørgsmål om at alt kan gøres med endnu et niveau af indirektion?

Troels Henriksen

Morten, det er en virkelig sjov løsning det med at genstarte programmet med en ny pegerstørrelse! Jeg tror dog der er for mange praktiske(!) problemer mht. håndtering af IO, der skal rulles tilbage. Dine krav til programmet (at det ikke bruger sizeof(void*) til noget kreativt) er også rimelige, men desværre udgør de en de-facto restriktion af C-sproget, så det ikke længere er rigtig C. Hvis man går med på det, så kan man også bare fjerne de dele af definitionen der gør at heltal skal have en maksimumværdi, og derved tillade vilkårligt store heltal. Men hvis jeg skal være ærlig, så er jeg ikke sikker på at begrebet "Turing-komplethed" er specielt veldefineret for interaktive programmer (eller IO udover lager-manipulation i det hele taget), så jeg synes dit forslag indtil videre er det mest interessante!

Troels Henriksen

Hvis man har en computer med et RAM lager der overstiger det maksimale der kan adresseres med en C-pointer må man formode at man har adgang til et "segmentregister" som kan anvendes til at tilgå den del af RAM-hukommelsen som man ikke kan tilgå direkte – er resten så ikke et spørgsmål om at alt kan gøres med endnu et niveau af indirektion?

Segmentregisteret kan også kun have et endeligt antal værdier, så selvom det forøger mængden af lager der kan addresseres, så gør det den ikke "vilkårligt stor". Desuden har C ikke noget koncept om segmentregistrere, hukommelsesrum eller deslige - uintptr_t er så vidt jeg kan se defineret således, at der i praksis kun er ét sådan rum. Eller i hvert fald, at summen af størrelsen på alle hukommelsesrum ikke kan overstige mængden af forskellige værdier for uintptr_t (grundet pigeonhole-princippet).

Hans Dybkjær

Jeg fik samme problem i går. På forespørgsel har deres websupport svaret at deres firewall blokerer, at de vil rette det, men at der "godt kan gå lidt tid". Det var i morges. I skrivende stund virker det stadig ikke. Og ja, hvis jeg tester med f efterfulgt af open i et ord, som du beskriver, får jeg præcis den samme fejl.
Den er nok en anelse hidsig, den firewall. Ikke mindst for et kommentarspor i en blog med tags til kode :-)

Morten Faurholt

Hej Troels

Enig i at generel I/O nok kan udgøre et problem, men tror egentlig det kan løses for hver enkelt forelagt API. Sålænge man ser på deterministiske programmer (og Turing-modellen er deterministisk) så må programmet jo gøre alt ens sålænge alt input er ens, og man skal derfor blot replaye alt input og ignorere alt "gammelt" output ;)

Mht. begrænsningen om at programmet ikke må være følsomt overfor ændringer i størrelser, så er det rigtigt at dette definerer et subset af C-programmer, men omvendt kan man sige at det allerede i dag er et krav at et C-program ikke er følsomt overfor størrelse hvis opførslen skal være veldefineret ift. sprog-definitionen (dvs. afvikles ens på alle C-implementationer) så på den måde er det ikke et nyt krav :-)

Finn Glamhøj

Nu er det jo en meget teoretisk diskussion da ingen computer kan håndtere et vilkårligt (stort) antal variable indenfor en afgrænset mængde hukommelse som jo er hvad der er tilgængeligt i praksis.
Men ideen med mit "segmentregister" og indirektion var at man med tilstrækkelige niveauer af indirektion kan "konstruere" værdien af "segmentregisteret" og dermed håndtere et vilkårligt antal variable selv med C's begrænsning i maksimal interger/pointer værdi som du så som et problem.
Ok, jeg har nok bare ikke forstået præcist, hvad det vil sige at være Turing complete.

Troels Henriksen

Nu er det jo en meget teoretisk diskussion da ingen computer kan håndtere et vilkårligt (stort) antal variable indenfor en afgrænset mængde hukommelse som jo er hvad der er tilgængeligt i praksis.

Nej, i et endeligt univers som vores(?) kan man aldrig konstruere en Turing-komplet maskine i sin fulde udstrækning. Det handler mest om hvorvidt C, forstået som en abstrakt maskine, kan siges at være Turing-komplet. En vigtig pointe er at Turing-komplethed er en egenskab ved maskiner, ikke ved sprog, og at når man snakker om at et sprog er "Turing-komplet", så mener man i virkeligheden at den "abstrakte maskine" et sprog implicit definerer er Turing-komplet. Det er vigtigt at holde sig for øje at Turing-komplethed er en matematisk definition indenfor kompleksitetsteori, og der sker mærkelige ting hvis man prøver at anvende den på en egentlig fysisk maskine.

Virkelige maskiner er typisk hvad man kalder "Linear Bounded Automata" (LBAer) - Turing-maskiner med afgrænset lagerplads. Jeg ved dog ikke hvor interessante de rent teoretisk er ift. Turing-maskiner når man studerer kompleksitet. Det kan være de kun er defineret så man har et svar når mormor peger på ens datamat og spørger hvad dét dog er for en.

Morten Faurholt

Finn: Det er korrekt at man ekstra niveauer af indirection kan man opnå ubegrænset plads. Men C har jo netop ikke disse levels af indirection - når man f.eks. foretager indirection i.f.t. en pointer, *p, for at tilgå det den peger på, så kan man kun specificere selve pointeren, p, man kan ikke specificere et segment-register eller lign. Så det du foreslår er en udvidelse af sproget C, og der vil man selvfølgelig godt kunne opnå ubegrænset lagerplads. F.eks. Java tillader ubegrænset lagerplads idet pointer-størrelsen ikke er synlig for programmet, og programmet ikke kan se selve pointer-værdierne. En pointer er abstraheret væk fra programmet. Bemærk at JAva har en begrænsning på array-længder, men det er ikke i sig selv et problem. F.eks. kan man jo stadig lave hægtede lister m.m. af ubegrænset længde. C's problem kommer af at pointer-værdierne og størrelsen af typen er direkte synlig for programmet.

Hvis C skulle udvides ville en segment-register mekanisme i sig selv ikke være nok, da det kun udvider adresserummet med en endelige faktor (ved effektivt at gå fra én pointer af endelig størrelse til en sammensætning af to pointere af endelig størrelse). Så for at gå den vej ville man være nødt til at indføre en form for "pointer-array" d.v.s. at man ville kunne adressere i.f.t. et "array af pointere" i stedet for bare "pointere" hvor adressen så findes ved sammensætning. Der må ikke være nogen begrænsning på længden af sådanne pointer-arrays for ellers komme vi ikke ud af den endelige suppedas. Så man kunne definere et pointer-array ved, at være en følge af normale pointere hvor øverste bit i hver pointer angiver om det er den sidste eller der kommer yderligere pointere (ligesom i UTF-8 enkodning). Den effektive adresse er da sammensætning af disse pointere strippet for deres første bit. Der skal som minimum tilføjes specielle alloc/free funktioner der kan returnere sådanne pointere på forlangende- de funktioner skal returnere en pointer til pointer-arrayet som så i sidste ende udpeger arealet der blev allokeret osv. Ideelt set burde man også indføre en ubegrænset heltalstype der kan bruges som argument til allco/free, men det er jo næsten snyd. Og det vil være muligt et program at humpe sig igennem og få adgang til uendelig meget lager via disse begrænsede faciliteter, f.eks. via hægtede-lister, men det vil være ganske svært at programmere i dette sprog, bl.a. fordi pointerne jo bliver længere og længere og man ikke nødvendigvis kan forudse hvor lang en pointer malloc() vil returnere næste gang, hvilket besværliggøre allokering af plads til liste-elementerne da de jo skal rumme referencer til nsæte element i listen.

Finn Glamhøj

@Morten
Som jeg tidligere har nævnt er det nok et spørgsmål om hvorvidt jeg har forstået præcist, hvad det vil sige at være Turing complete.
Min opfattelse var, at kan man skrive legal C-kode som ville kunne løse opgaven vil det være Turing complete, hvilket jeg så må forstå ikke er nok.
At C ikke har denne indirektion indbygget betyder vel ikke, at man ikke er i stand til at skrive et program der facilitere indirektion? men jeg medgiver at det bestemt ikke vil være et kønt program der kommer ud af det og at det også vil give en masse andre udfordringer er jeg ikke i tvivl om.
I øvrigt, i den abstrakte maskine er "segmentregisteret" så ikke altid tilstrækkelige stort? men ok, jeg kan godt se at "segmentregisteret" ikke er en facilitet ved den abstrakte C-maskine, men ved implementeringen af en maskine og at det gør en forskel.
Men for at vende tilbage til udgangspunktet for Troels indvending.
Er begrænsningen i integer/pointer størrelse i C ikke knyttet til den virkelige maskine og altså ikke en begrænsning ved den abstrakte maskine? jeg mener siger C-standarden andet end hvordan relationerne er mellem typerne? det vil sige, siger den noget om størrelsen? når vi nu taler om den abstrakte maskine.
Under alle omstændigheder så har jeg da fået vendt og drejet nogle tanker og som følge af det også lært noget - tak for det :-)

Kjeld Flarup Christensen

Well, i og med at en turingmaskine har en uendelig lang papirstrimmel til rådighed er der ingen programmeringssprog i den virkelige verden, som er helt stringent turingkomplette - de må nøjes med at køre på maskiner, som har endelig hukommelse. I praksis ser man dog nok bort fra den restriktion, hvis man vil gøre begrebet "turingkomplet" praktisk anvendeligt...


Der er ikke noget som er uendeligt langt. Turing maskinen er derfor en model.
Og for mig at C levet C fuldt op til det.
Husk lige på at C definitionen er uafhængig af pointer størrelsen. Jeg har faktisk arbejdet med 16 bit maskiner. Så kom 32 bit wow. Nu er 64 bit standard.
Men man kan teoretisk altid bygge en C compiler med n+1 bits pointere.

Derfor er C for mig at se lige så Turing komplet som en Turing maskine har en uendelig strimmel.

PS: Jeg havde lugtet lunten allerede inden jeg klikkede på artiklen. Og Dennis Ritchie var da også det første jeg bemærkede.

Torben Mogensen Blogger

Husk lige på at C definitionen er uafhængig af pointer størrelsen. Jeg har faktisk arbejdet med 16 bit maskiner. Så kom 32 bit wow. Nu er 64 bit standard.
Men man kan teoretisk altid bygge en C compiler med n+1 bits pointere.

Derfor er C for mig at se lige så Turing komplet som en Turing maskine har en uendelig strimmel.

Den holder ikke. Størrelsen af pointere (og dermed adresserbart lager) vil være begrænset i det øjeblik, du oversætter dit program (eller senest, når du starter det). Du kan ikke på køretid ændre størrelsen af pointere.

For at være turingfuldstændig, skal en maskine på køretid kunne udvide sin lagerplads uden begrænsninger. Hvis du altid skal kunne tage adressen på en værdi, kræver det en ubegrænset størrelse af pointere. Alternativet er ikke at have numeriske adresser på værdier. F.eks. er to stakke, hvor du kun kan se begrænset mange elementer ned fra toppen, rigeligt til at sikre turingfuldstændighed.

Jeg vil ikke afvise, at man ved hjælp af i/o i C kan emulere et ubegrænset bånd, men uden i/o vil enhver instans af Cs specifikation have begrænset lager.

I praksis har det betydet, at ældre C-programmer ikke kan håndtere de datamængder, der findes i dag, da de er skrevet under antagelse af, at pointere er 32 bit. Generelt er det god kodestandard at undgå a priori maksimalstørrelser på datastrukturer. Det gælder også pointere.

Morten Faurholt

Hej Torben, jeg er enig i dit svar i.f.t. Kjelds indvending. Den uendelige lagerplads for en enkelt maskine er det centrale, ikke blot muligheden for at maskinen kan have en vilkårlig stor, men endelig, lagerplads. F.eks. er stop-problemet løseligt hvis pladsen er endelig, da programmer der ikke stopper, vil være nødt til før eller siden (i endelig og endda på forhånd opad begrænset tid) at gå ind i en tidligere tilstand, hvilket kan bruges til at genkende den slags progarmmer.

Når det er sagt, så mener jeg faktisk, jf. mit tidligere indlæg, at C som programmerings-sprog er Turing-komplet, idet det er muligt at implementere en C-fortolker der vil tilbyde programmer at bruge uendelig plads, sålænge programmernes output (hvad enten det er I/O eller baseret på returværdien af main-funktionen) ikke afhænger af den konkrete størrelse af typer, og det er en riemlig antagelse idet output'et ellers alligevel ikke er definerbart ud fra C-standarden alene :)

David Kjær

Skønt det var en rigtig sjov aprilsnar - så længe den fik lov at vare - så synes jeg den tekniske diskussion bagefter har været mindst ligeså interessant.

Jeg hørte engang, at man ofte tyr til lambda calculus, den del af Church-Turing tesen som "Church" står for, for at bevise at et sprog er Turingfuldstændigt. Simpelthen fordi det er nemmere rent teknisk og man slipper for mange af de her ingeniørmæssige overvejelser.

Nu hvor der er adgang til folk der forsker i disse ting til daglig.... Har dette sin rigtighed? Kan I umiddelbart komme på en teknisk ting i C der gør det ligeså kompliceret at implementere lambda calculus som det tilsyneladende er at implementere Turingmaskinen?

Troels Henriksen

Kan I umiddelbart komme på en teknisk ting i C der gør det ligeså kompliceret at implementere lambda calculus som det tilsyneladende er at implementere Turingmaskinen?

Det afhænger mest af hvilken type sprog du forsøger at vise Turing-komplethed for. Hvis det er et "maskin-lignende" sprog hvor du med rimelig enkelthed kan indkode en tabel, så er det ofte ligetil at vise Turing-fuldstændighed ved at lave en fortolker til et kendt Turing-komplet sprog (jeg bruger selv Brainfuck).

Hvis du derimod har et mere matematisk orienteret sprog, f.eks. et funktionssprog, er det ofte ikke ligetil at indkode tabeller på den måde.

Men i virkeligheden, så er det meget sjældent man har behov for (eller interesse i) at vise at et sprog er Turing-komplet. Langt de fleste sprog er det, for der skal meget lidt til (i hvert fald hvis man ikke tager kravet om ubegrænset lagerkapacitet alt for alvorligt).

Baldur Norddahl

For at være turingfuldstændig, skal en maskine på køretid kunne udvide sin lagerplads uden begrænsninger.

Der findes maskiner, som kan køre C programmer, hvor hukommelsen kan udskiftes undervejs med "bank switching". Eksempel gamle DOS maskiner med EMS: https://en.wikipedia.org/wiki/Expanded_memory

Nu giver EMS naturligvis ikke uendeligt hukommelse, da hukommelsessiderne er nummeret og dermed endelige i antal. Men det vil være trivielt at lave en EMS variant hvor man kun kan bede om næste eller forrige side. Eller hvis det kun er sproget man vil vise noget om, så kan vi lave et interface i software, der kun eksponerer en relativ switching mekanisme til resten af programmet.

C er et af relativt få sprog der kan arbejde effektivt med EMS på grund af den manuelle hukommelsestilgang.

Morten Faurholt

Har ikke arbejdet med EMS i C (men har i assembler, men går ud fra man kunne få en pointer til EMS vindues-bufferen, og der var et API der kunne bruges til at ændre hvad vinduet skal pege på det større EMS-lager. Og ja, med frem/tilbage funktioner vil det give mulighed for ubegrænset hukommelse (svarende til Turing-maskinens køren frem og tilbage på båndet). Men det er jo ikke standard C, men et bibliotek ovenpå der giver disse muligheder, så det svarer for mig at se lidt til at bruge filer eller I/O til at omgå begrænsningen, og det er jo åbenlyst muligt men ikke en del af sproget. Med EMS i C vil man have pointere "som ikke virker" når vinduet ikke peger på det rigtige, idet mange af pointerne fra C sprogets synspunkt jo overlapper. Så jeg synes egentlig ikke EMS spiller specielt godt sammen med C, det er mere en "kludge" ovenpå. Ved ikke om visse C compilere tilbød specialsupport, så f.eks. den selv kunne indsætte kode til at flytte vinduet når nødvendigt. Det ville i så fald have spillet dårligt samme med multitrådet programmering, men det gør EMS nok i det hele taget.
Desuden kunne jeg forestille mig pointere til buffer-vinduet skal angives som "volatile" og man må så håbe det afholder compileren fra at lave numre med at ombytte operationer m.m. (så f.eks. en skrivning til hukommelsen blev udskudt til efter vinduet var flyttet, så skrivningen sker til det forkerte sted!).
Dette koster så tilgengæld på ydelsen, da visse optimeringer ikke længere er mulige). Men måske compilerne ikke lavede så mange julelege dengang.

Kjeld Flarup Christensen

Den holder ikke. Størrelsen af pointere (og dermed adresserbart lager) vil være begrænset i det øjeblik, du oversætter dit program (eller senest, når du starter det). Du kan ikke på køretid ændre størrelsen af pointere.


Ud fra den logik er Turingmaskinen jo heller ikke Turingkomplet, da enhver implementationen af den vil være begrænset af antallet af atomer i universerset.

Jeg har så lige læst lidt op på lektien. Det giver ingen mening at implementere en turing maskine med uendeligt bånd.

Det interessante med en Turingmaskine er om den givet et problem stopper igen. Hvis den ikke gør det, så kan problemet ikke løses. Og det kan man afgøre med matematik, ikke ved at sætte en "computer" i gang.

Når man så har konstateret at Turingmaskinen vil stoppe. Så kan ethvert Turingkomplet system også løse problemet. Og der behøves ikke et uendeligt bånd.

Hvis Turingmaskinen stopper, så behøver båndet ikke være uendeligt. Årsagen er jo den simple, at maskinen aldrig kan nå enden af et uendeligt bånd, og derfor ikke kan standse. D.v.s. at man i det matematiske bevis finder en ligning a.la. n= n+1

Det er jo meget praktisk at vide om det problem man vil fodre sin computer med kan løses indenfor endelig tid, så man ikke sidder foran skærmen i årevis og venter på om den bliver færdig. Afbryder man den beviser der jo ikke at problemet ikke kan løses, da det jo kunne være at løsningen kom et sekund efter man stoppede.
På samme måde, hvis pointeren får overflow, så beviser det heller ikke, at problemet ikke kan løses.

Kan det matemastisk vises at en Turingmaskine ville stoppe, er det blot et spørgsmål om at bygge computeren stor nok. Derfor er pointerens størrelse ikke afgørende for om en computer er Turingkomplet. Kommer der overflow, så er maskinen bare for lille og man må bygge en større, for man har matematisk bevist at det kan lade sig gøre.

Troels Henriksen

Ud fra den logik er Turingmaskinen jo heller ikke Turingkomplet, da enhver implementationen af den vil være begrænset af antallet af atomer i universerset.

Korrekt! En Turing-maskine er en matematisk model der på ingen måde kan implementeres nøjagtigt i et endeligt univers. Jeg sidder dog selv og skriver denne besked på en ret god approksimation af en Turing-maskine, så det er ikke noget man behøver bekymret sig så meget om, med mindre man godt kan lide kompleksitetsteoretiske tanke-eksperimenter.

Det er også derfor vi snakker om hvorvidt C, som abstrakt defineret maskine i sin specifikation er Turing-komplet, uden at bekymre os for meget om hvordan en Turing-komplet implementering ville se ud (en sådan kan alligevel ikke lade sig gøre). Her er C så noget særligt, da det for at mindre om verdens virkelige maskine, indeholder nogle indrømmelser såsom "pegere er af endelig størrelse". Dette er en god og rimelig indrømme at gøre for et sprog som C, da en af C's vigtigste fordele jo netop er den korte afstand mellem den abstrakte C-maskine og en (typisk) fysisk datamat.

Log ind eller Opret konto for at kommentere