avgörbarhetsproblemet

das Entscheidungsproblem – frågan om det går att avgöra ifall ett matematiskt eller logiskt påstående är sant eller falskt på ett mekaniskt sätt (alltså med en algoritm) som ger rätt svar för alla mate­matiska och logiska påståenden. – Pro­blemet fick sitt namn av den tyska ma­te­ma­tik­ern David Hilbert (1862—1942, se Wikipedia – se också Hilberts paradox), men andra filosofer och matematiker hade tänkt i samma banor tidigare. Ett annat sätt att se på saken är att fråga ifall det finns ett logiskt‑matematiskt språk som kan användas för att formulera varje tänkbart problem, och som också kan användas för att räkna ut lösningen. Kurt Gödels† ofullständighets­sats från 1931 visade indirekt att det inte går att avgöra, och något senare visade Alan Turing† och Alonzo Church†, obe­ro­ende av varandra och på olika sätt, att svaret på frågan är nej. Turings bevis innehöll beskrivningen av det som numera kallas för Turingmaskiner. (Avgörbarhetsproblemet kallas också för avgörandeproblemet.)

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

Turing, Alan

Alan Turing.
Alan Turing.

engelsk matematiker och datorpionjär (19121954). – Alan Turing beskrev 1936 en teoretisk modell av ett datorprogram och en dator, det som numera kallas för en Turingmaskin. Det gjorde han i en matematisk-logisk uppsats om det så kallade stopproblemet. Artikeln har blivit en klassiker inom datorvetenskapen. (Läs också om Alonzo Church† och Church‑Turings hypotes.) – Under andra världskriget arbetade Turing på Bletchley Park med att knäcka tyskarnas kryptering. Han konstruerade där maskinen ”The Bombe”, som dechiffrerade meddelanden som hade krypterats med tyskarnas krypteringsapparat Enigma, men han var på sin höjd inspiratör till datorn Colossus†. – Efter kriget, 1946, konstruerade han datorn ACE†, och 1948 deltog han i konstruktionen av Manchester Mark I†. – 1950 beskrev han det som sedan dess kallas för Turingtestet i en artikel som blev banbrytande inom området artificiell intelligens. – I början av 1950‑talet studerade han också morfogenetik, det som nu kallas för fraktala former. Alan Turing var troligen också den första som programmerade en dator till att spela musik. Se denna artikel från British Museum med ljudfil (en bit ner på sidan). – 1952 dömdes Turing för homosexuella handlingar, och 1954 dog han i vad som då tolkades som själv­­mord. (Att det var själv­­mord ifråga­­sattes 2012 av professor Jack Copeland, se denna artikel.) – I september 2009 beklagade Stor­britanniens dåvarande premiärminister Gordon Brown officiellt hur Turing hade behandlats. Han er­kände att utan Turings insatser kunde andra världskrigets förlopp ha blivit mycket annorlunda. På jul­afton 2013 benådades Turing postumt. – Se här och här (pdf för nerladdning). – Turingpriset, A M Turing Award, är upp­kallat efter Alan Turing. – Standardbiografin om Alan Turing är Alan Turing: The Enigma (1983) av Andrew Hodges (länk). David Lagercrantz har skrivit en roman om Alan Turing, Synda­fall i Wilmslow (2009, se intervju i Computer Sweden). Filmen Breaking the code från 1996 handlar om Turings liv, liksom The imitation game från 2014 – se IMdB (länk). En musikal om Alan Turing visades i Edinburgh sommaren 2022 – se alanturing.biz. – Se också The Turing digital archive och Andrew Hodges webbplats Alan Turing: the enigma. – En av Turings anteckningsböcker såldes i april 2015 på auktion i New York för 1 025 000 dollar. – IDG:s artiklar om Alan Turing: länk.

[alan turing] [datorpionjärer] [datorvetenskap] [it-historia] [matematik och logik] [ändrad 6 augusti 2022]

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]

mekanisk

  1. – om matematisk problem­lösning: gjord utan insikt eller krea­ti­vitet, enbart genom tillämp­ning av givna regler. Att lösa ett ma­te­ma­tiskt problem mekaniskt är att följa en al­go­ritm steg för steg från början till slut. Antagandet att varje problem som en fanta­si­lös men nog­grann männi­ska kan lösa med papper och penna också kan lösas av en maskin kallas för Church‑Turings hypo­tes – se Alonzo Church† och Alan Turing†;
  2. – annars: om anordningar: bestående av delar av metall, plast eller annat fast material som kan röra sig och påverka varandra.

[datorvetenskap] [matematik och logik] [ändrad 29 september 2020]

Church, Alonzo

(19031995) – amerikansk matematiker. – Alonzo Church 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 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 (givet tillräckligt med tid) 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 missuppfattningar av Church‑Turings hypotes finns här.

[alonzo church] [datorvetenskap] [för- och bihistoria] [personer] [ändrad 17 oktober 2021]