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 datorprogram kommer till ett slut någon gång, eller om beräkningen fortsä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 uppgiften är olöslig. – Observera 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änkbara 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 information om ifall räknearbetet tar slut någon gång, eller aldrig tar slut. – I uppsatsen ”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. – Cybernetik är 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. – Benämningen cybernetik i denna betydelse infördes 1948 av Norbert Wiener, och den har gett oss kort­f­ormen cyber. Den franska vetenskapsmannen André Marie Ampère (1775—1836, se Wikipedia) myntade ordet redan 1831, men då i be­tydelsen vetenskapen om politisk ledning av människor. – Enligt vetenskapshistorikern David A Mindell (länk) var det som Wiener döpte till cybernetik en sammanställning av kunskaper och erfarenheter som redan var kända och tillämpade av praktiker – se hans bok Between human and machine från 2002 (länk). – Ordet cybernetik kommer av grekiska kybernetes – styr­man.

[cyber] [datorvetenskap] [ändrad 18 april 2020]

ätande filosoferna

(the dining philosophers) – ett klassiskt datorvetenskapligt problem om tillgång till gemensamma resurser: Fem filosofer sitter runt ett matbord och ska äta ris. Men det finns bara fem ätpinnar, placerade mellan filosoferna. Varje filosof har alltså en ätpinne 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 samtidigt. 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. – Utmaningen ä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 programmeringsexperten Edsger Dijkstra (se Wikipedia). – Mer om de ätande filosoferna 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 datorprogram, men de kan i princip köras med papper och penna. Man börjar med ett godtyckligt 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 granncell­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 upprepas 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 rutmönster eller på en obegränsad yta. Cellerna behöver inte vara rutor, utan kan ha andra former, och cellautomaten kan ha fler än två dimensioner. – Vissa enkla cellautomater 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 datorpionjä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 (1937–2020, se h2g2länk) program Game of life (se Wikipedia) från 1970 (se artikel i Scientific American). – Läs mer i Wikipedia.

[datorvetenskap] [programmering] [ändrad 25 augusti 2020]

 

ä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.

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

byteordning

(byte order) – siffrornas ordningsföljd i tal som behandlas i dator. – Enkelt uttryckt handlar det om ifall talet matas in i datorns processor 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 omvä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 processorn kan hantera båda ordningarna.

– I själva verket lagras värdena i binär form, vanligt­­vis grupperade i byte, men principen är samma: rak byteordning innebär att ett hexadecimalt 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 minnesplatsen, till exempel på plats nummer 1 000, och 9B (=155) lagras på den närmast högre minnesplatsen, alltså på plats 1 001. – Med omvänd byteordning 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 användare, men kan ställa till problem när data överförs mellan datorsystem av olika typ. Tek­niskt finns det en lång­­varig diskussion om vilken byteordning som är mest ändamålsenlig. De vanligaste processorerna för persondatorer, Intels processorer, använder omvänd byteordning.

[byteordning] [datorvetenskap] [ändrad 5 juni 2020]