stopproblemet

Tecknad bild av superdatorn Deep Thought från Liftarens guide till galaxen.
Datorn Deep Thought som behövde 7,5 miljoner år för att räkna ut svaret.

(the halting problem) – frågan om det på förhand går att räkna ut ifall en körning av ett dator­­­program kommer till ett slut någon gång, eller om beräkningen fort­sätter i all evighet. – Alan Turing bevisade i sin berömda artikel ”On computable numbers with an application to the Entscheidungsproblem” (länk) från 1936 att upp­giften är olöslig. – Ob­servera att detta gäller när frågan ska besvaras enbart med mekaniska metoder och för varje tänk­bar beräkning. En matematiskt kunnig mänsklig bedömare kan ofta avgöra ifall en beräkning kommer att fortsätta i evighet eller om den tar slut någon gång, men stopproblemet gäller ifall man kan programmera en dator så att den avgör saken i alla tänk­bara fall och utan mänsklig hjälp. – Vi vet till exempel att om vi sätter en dator att räkna ut det exakta värdet på pi så kommer den aldrig att bli klar, men det ”vet” inte datorn. Att det är så har mänskliga matematiker räknat ut, och det har de inte gjort genom att räkna på pi oändligt länge. Hur länge man än räknar på värdet av pi så får man nämligen inte, enbart genom att fortsätta räkna, någon in­for­ma­tion om ifall räkne­arbetet tar slut någon gång, eller aldrig tar slut. – I upp­­satsen ”On computable numbers…” beskrev Turing också det som senare blev känt som Turing­maskinen. – Några månader före Turing hade Alonzo Church bevisat samma sak, fast utan att beskriva en maskin. – Stopproblemet är besläktat med avgörbarhetsproblemet (das Entscheidungsproblem), men också med Kurt Gödels ofullständig­hets­sats. – Läs också om omega (Chaitins konstant).

[datorvetenskap] [matematik och logik] [ändrad 6 juni 2017]

cybernetik

studiet av styrsystem i maskiner, människor och levande varelser, sär­skilt kommu­nika­tion och återkoppling. Nära besläktat med system­­teori och informations­teori samt datorvetenskap. Ordet används numera sällan som benämning på en vetenskaplig disciplin. – Termen cybernetik i denna betydelse infördes 1948 av Norbert Wiener, och har gett oss kort­f­ormen cyber. Den franska veten­­skaps­mannen André Marie Ampère (1775—1836, se Wikipedia) myntade ordet redan 1831 i be­tydelsen veten­­skapen om politisk ledning av människor. – Ordet kommer av grekiska kyber­netes – styr­man.

[datorvetenskap] [ändrad 2 augusti 2017]

ätande filosoferna

(the dining philosophers) – ett klassiskt datorvetenskapligt problem om tillgång till gemen­­samma resurser: Fem filosofer sitter runt ett mat­bord och ska äta ris. Men det finns bara fem ät­­pinnar, placerade mellan filosoferna. Varje filosof har alltså en ät­pinne till vänster och en till höger, så varje pinne ligger mellan två filosofer. Och för att äta behöver man ju två pinnar, så alla kan inte äta sam­­tidigt. Man får inte ta två pinnar på en gång, utan man måste först ta en, sedan (utan att man behöver släppa den första) den andra. Risken är att alla blir sittande med var sin ät­pinne och väntar. – Utman­ingen är att hitta ett regelsystem som gör att alla med minsta möjliga väntetid får disponera två pinnar så att de kan äta. Problemet formulerades av programme­rings­­experten Edsger Dijkstra (se Wikipedia). – Mer om de ätande filo­­soferna i Wikipedia. – Läs också om aktivt dödläge och contention samt om det spelteoretiska problemet middagsätarens dilemma.

[datorvetenskap] [programmering] [ändrad 18 december 2019]

cellautomat

(cellular automaton, plural cellular automata) – mönster av rutor (celler) som förändras genom att varje ruta påverkar sina närmaste grannar. Cellautomater realiseras oftast som dator­­program, men de kan i princip köras med papper och penna. Man börjar med ett god­tyckligt valt mönster – man fyller i siffror eller andra värden i några av cellerna – och ett antal regler. En regel kan till exempel säga att om summan av värdena i en cells grann­cell­er är över 10, ändra värdet i cellen till 1. Man tillämpar reglerna på alla rutor, och börjar sedan om på nytt med samma regler, så att nya mönster uppstår. Detta upp­­repas tills mönstret inte förändras längre. Det kan också sluta med en slinga (ett antal mönster upp­repas om och om igen). I sällsynta fall tycks mönstret förändras i oänd­lig­het. – Cellautomater kan köras i ett begränsat rut­mönster eller på en obegränsad yta. Cellerna behöver inte vara rutor, utan kan ha andra former, och cell­auto­maten kan ha fler än två dimensioner. – Vissa enkla cell­automater upp­visar ett oväntat komplicerat beteende (emergent beteende). Det beror på vilka värden man har i utgångs­läget och vilka regler cellautomaten följer. – En cell­automat är ett slags dator (en universell Turingmaskin) och kan i princip programmeras för att lösa alla problem som kan lösas med en dator. – John von Neumann hittade på cellautomater på 1940‑talet. Hans mål var att hitta en mekanism för att bygga strukturer som kan göra kopior av sig själva. Idén med cellautomater har vidareutvecklats av dator­pionjären Konrad Zuse i boken Rechnender Raum (Calculating space), från 1969 och av matematikern Stephen Wolfram i boken A new kind of science från 2002. Den mest kända tillämpningen är John Horton Conways (se h2g2) program Game of life (se Wikipedia) från 1970 (se artikel i Scientific American). – Läs mer i Wikipedia.

[datorvetenskap] [programmering] [ändrad 7 juni 2017]

 

ändare

svenska för endian – syftar på de två skolorna för byte­ordning, nämligen big‑endian och little‑endian (tjock­ändare och smal­ändare). – Det handlar om ifall det är mest ända­­måls­­enligt att lagra tal i datorns minne i rak ordning, big‑endian, (som när ett tusen skrivs 1 000, alltså största värdet först) eller i omvänd ordning, little‑endian (som om ett tusen skulle skrivas ”0001”, största värdet sist). – Ordet: Benämningarna big‑endian och little‑endian är hämtade från Jonathan Swifts satir Gullivers resor från 1726. I landet Lilliput pågår politiska strider mellan de som knäcker ägg i den smala änden och de som knäcker ägg i den tjocka änden.

[datorvetenskap] [processorer] [ändrad 13 juni 2018]

byteordning

(byte order) – siffrornas ordningsföljd i tal som lagras i dator. – Enkelt ut­tryckt handlar det om ifall talet lagras i datorns minne med början vid de största värdena eller de minsta värdena:

  • – Rak byte­ordning inne­bär att talen lagras som när man skriver tal på papper med siffror: alltså med det högsta värdet först och det lägsta sist. (När vi skriver 314 menar vi ju 300+10+4.) På engelska kallas det för big-endian, tjock­­ändare – se ändare;
  • – Om­vänd byte­ordning inne­bär att talen lagras i om­vänd ordning. När man menar tre­hundra­fjorton skulle man alltså med vanliga siffror skriva ”413” (4+10+300). På engelska kallas det för little-endian, smal­­ändare;

– Öppen byte­ordning (open-endian) är när pro­­ces­sorn kan hantera båda ord­­ning­ar­na.

– I själva verket lagras värdena i binär form, vanligt­­vis grupperade i byte, men principen är samma: rak byte­­ordning innebär att ett hexa­decimalt tal som 8A9B (=35 483) lagras så här: 8A (den del av talet som står för 8A00, alltså för 35 328) lagras på den första minnes­­platsen, till exempel på plats nummer 1 000, och 9B (=155) lagras på den närmast högre minnes­­platsen, alltså på plats 1 001. – Med om­vänd byte­­ordning lagras talet i exemplet, 8A9B, med 9B på plats 1 000 och 8A på plats 1 001. Det har den fördelen att om talet blir större kan man lägga ökningen på plats 1 002 utan att behöva flytta något.

– Byte­ordningen har ingen be­tydelse för vanliga an­vändare, men kan ställa till problem när data överförs mellan data­­system av olika typ. Tek­niskt finns det en lång­­varig diskussion om vilken byte­ordning som är mest ända­­måls­­enlig. De vanligaste pro­cessorerna för person­­­datorer, Intels pro­cessorer, an­vänder om­vänd byte­ordning.

[datorvetenskap] [ändrad 24 september 2017]

Church, Alonzo

(1903—1995) – amerikansk matematiker. Han bevisade 1936 i artikeln ”A note on the Entscheidungsproblem” (se avgörbarhetsproblemet) att det finns mate­matiska problem som det inte går att lösa på med mekaniska metoder. Det var samma sak som Churchs studie­­kamrat Alan Turing bevisade senare samma år i sin upp­sats om stopproblemet. Turing visade senare att de två bevisen var likvärdiga. Båda bevisen byggde på Kurt Gödels ofullständighetssats. – Church‑Turings hypotes säger att alla matematiska beräkningar som kan beskrivas i ett ändligt antal steg (med en algoritm) kan lösas av en maskin. Om en nog­­grann men fantasi­lös människa med papper och penna kan räkna ut lösningen (lösa problemet mekaniskt) kan en maskin också göra det. Men: beräkningen kan pågå i all evighet. Till exempel är det lätt att beskriva divisionen 2 delat med 3, men det tar en evig­het att räkna ut svaret med decimala siffror (0,6666666……) om man inte sätter stopp. För att inte tala om sådant som att räkna ut värdet på pi. – Det som både Church och Turing bevisade var att även om en maskin kan utföra alla beräkningar som kan uttryckas som algoritmer, så kan maskinen inte avgöra ifall beräkningen tar slut någon gång, eller om den fort­sätter i all evighet. – En artikel på engelska om vanliga missuppfatt­ningar av Church‑Turings hypotes finns här.

[alonzo church] [datorvetenskap] [för- och bihistoria] [personer] [ändrad 6 november 2019]

Acreo

RISE Acreo – ett svenskt forskningsinstitut med inriktning på bland annat kommu­nika­tions­teknik, nano­teknik och tryckt elektronik. Finns i Kista, Göteborg, Lund, Norrköping och Hudiksvall. Grundades 1996 och ingår sedan 2002 i paraply­orga­nisa­tionen Swedish ICT som i sin tur sedan 2016 ingår i RISE. – Se ri.se.

[datorvetenskap] [forskningsinstitut] [ändrad 13 november 2019]