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änkbar 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 Turingmaskinen. – 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ändighetssats. – Läs också om omega(Chaitins konstant).
studiet av styrsystem i maskiner, människor och levande varelser, särskilt kommunikation och återkoppling. – Cybernetik är nära besläktat med systemteori och informationsteori 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 kortformen cyber. Den franska vetenskapsmannen André Marie Ampère (1775—1836, se Wikipedia) myntade ordet redan 1831, men då i betydelsen 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 – styrman.
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 ätpinne 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†. – På engelska: the dining philosophers. – 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.
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 grannceller ä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 upprepas om och om igen). I sällsynta fall tycks mönstret förändras i oändlighet. – 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 uppvisar ett oväntat komplicerat beteende (emergent beteende). Det beror på vilka värden man har i utgångsläget och vilka regler cellautomaten följer. – Det har bevisats att cellautomater är ett slags datorer (universella Turingmaskiner) och kan i princip programmeras för att lösa alla problem som kan lösas med datorer. – 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. (Detta hade händelsevis koppling till DNA, som upptäcktes 1953.) – Idén med cellautomater har vidareutvecklats av datorpionjären Konrad Zuse† i bokenRechnender 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 av cellautomatens princip är John Horton Conways (1937–2020, se h2g2: länk) program Game of life (se Wikipedia) från 1970 (se artikel i Scientific American). – Läs också om ZigZag. – Mer i Wikipedia. – På engelska: cellular automaton, plural: cellular automata.
svenska för endian – syftar på de två skolorna för byteordning, nämligen big‑endian och little‑endian(tjockändare och smaländare). – Ändarna tvistar om ifall det är mest ändamålsenligt 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.
(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 byteordning innebä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;
– Omvänd byteordning innebär att talen lagras i omvänd ordning. När man menar trehundrafjorton skulle man alltså med vanliga siffror skriva ”413” (4+10+300). På engelska kallas det för little‑endian, smaländare;
– Öppen byteordning(open-endian) är när processorn kan hantera båda ordningarna.
– I själva verket lagras värdena i binär form, vanligtvis 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.
– Byteordningen har ingen betydelse för vanliga användare, men kan ställa till problem när data överförs mellan datorsystem av olika typ. Tekniskt finns det en långvarig diskussion om vilken byteordning som är mest ändamålsenlig. De vanligaste processorerna för persondatorer, Intels processorer, använder omvänd byteordning.
