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 Wikipedialänk – 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 Turing­maskiner. (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 (1912——1954). –– Alan Turing beskrev 1936 en teoretisk modell av ett dator­­program och en dator, det som numera kallas för en Turingmaskin. Det gjorde han i en matematisk-logisk upp­sats om det så kallade stopproblemet. Artikeln har blivit en klassiker inom dator­veten­skapen. (Läs också om Alonzo Church och Church-Turings hypotes.) – Under andra världs­­kriget arbetade Turing på Bletchley Park med att knäcka tyskarnas kryptering. Han konstru­erade där maskinen ”The Bombe,” som de­­chiff­re­rade meddelanden som hade krypterats med tyskarnas krypteringsapparat Enigma, men han var på sin höjd in­­spira­tör till datorn Colossus. –– Efter kriget, 1946, konstruerade han datorn ACE, och 1948 deltog han i konstruktionen av Man­chester Mark I. – 1950 beskrev han det som sedan dess kallas för Turingtestet i en artikel som blev en ban­­brytare inom området arti­ficiell 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 be­klagade 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 annor­­lunda. På jul­afton 2013 benådades Turing postumt. –– Se här och här (pdf för ner­laddning). –– Turingpriset, A M Turing Award, är upp­kallat efter Alan Turing. –– Standard­­biografin över Alan Turing är Alan Turing: The Enigma (1983) av Andrew Hodges (länk). David Lager­­crantz 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 (länk). –– Se också The Turing digital archive och Andrew Hodges webb­plats 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.

[alan turing] [datorvetenskap] [it-historia] [matematik och logik] [personer] [ändrad 6 juni 2017]

Turingtest

föreslaget sätt att avgöra ifall en dator kan anses ha intelligens jämförbar med människans. – Testet beskrevs 1950 av Alan Turing i artikeln Computing machinery and intelligence (länk). Den artikeln anses ha inlett diskussionen om artificiell intelligens. – Turingtestet går till så att en person via teleprinter (numera med e‑post eller chatt) ställer frågor till en dold dator och till en dold människa utan att veta vem som är vad. Syftet med frågorna är att avslöja datorn. Datorn är pro­gram­merad så att den försöker övertyga testpersonen om att den är människa. Människan försöker också övertyga testpersonen om att hon är en människa. Om datorn lyckas lura test­personen en längre tid så bör man, enligt Alan Turing, anse att datorn äger intelligens av samma slag som en människa. – Turing ansåg inte att det fanns någon grundläggande skillnad mellan datorernas beräkningsförmåga och människans intelligens, utan att skillnaden berodde på människo­hjärnans komplexitet. – Jämför med Lady Lovelaces invändning. – Det hålls årliga tävlingar om att klara Turingtest, se Loebnerpriset, och en del dator­program klarar sig riktigt bra. – Se också Eugene Goostman och SH-testet (the PHB test 😉 ). – Ett mer krävande alternativ är Lovelacetestet.

[ai] [kognition] [ändrad 18 september 2018]

stopproblemet

Tecknad bild av superdatorn Deep Thought från Liftarens guide till galaxen.
Datorn Deep Thought som behövde 7,5 mil­joner å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 själv 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. –– Stoppro­blemet är besläktat med avgörbarhetsproblemet (das Entscheidungsproblem), men också med Kurt Gödels ofull­ständig­hets­sats. – Läs också om omega (Chaitins konstant).

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

Turingmaskin

En riktig Turingmaskin, byggd av amerikanen Mike Davis.
En riktig Turingmaskin, byggd av amerikanen Mike Davey.

en teoretisk dator som beskrevs 1936 av Alan Turing. Det var en ren tankekonstruktion. (1936 fanns inga datorer.) – En Turing­maskin mot­svarar ett modernt datorprogram, men när man talar om Turingmaskiner menar man ofta universella Turingmaskiner, som mot­svarar datorer. – Alan Turing beskrev maskinen i artikeln ”On computable numbers with an application to the Entscheidungsproblem” (länk). Artikeln handlade om ett matematiskt problem, stopproblemet, inte om datorer. Turing beskrev det som senare fick heta Turingmaskinen enbart för att göra ett matematiskt bevis åskådligt. Det var inte en beskrivning av något som Turing verkligen tänkte bygga. – Turing­­maskinen har en pappers­remsa som matas fram och tillbaka genom ett läs- och skrivhuvud enligt bestämda regler. Det finns flera upp­­sätt­ningar regler som kallas för tillstånd, och i reglerna ingår över­gångar från ett tillstånd till ett annat. Skriv­huvudet kan läsa, radera och skriva tecken på remsan. Man programmerar Turing­maskinen med tecken på remsan, och Turingmaskinen matar sedan, enligt reglerna, remsan fram och tillbaka, läser, raderar och skriver samt växlar till­stånd tills den kommer till en regel som säger ”stopp”. Då stannar maskinen och lösningen på pro­blemet kan avläsas på remsan. Detta är helt genomförbart, bortsett från de praktiska problemen med pappersremsan, pennan och radergummit. – I princip kan varje pro­blem som kan lösas med ett modernt dator­program också lösas av en mot­svarande Turing­maskin, men naturligt­vis är det ogörligt att använda en maskin med pappers­remsa. Man brukar därför simulera Turing­maskiner i datorer. (Se här.) Det är nämligen bra att öva sig på program för Turingmaskiner när man ska lära sig programmera. –– Se också finit tillstånds­maskin. –– Efter andra världskriget konstruerade Alan Turing en dator, ACE som till stor del baserades på de principer som Turing beskrev i sin artikel. – Turingmaskinen införde idén om lagrade program i datortekniken. Idén togs upp av John von Neumann i hans arkitektur för datorer, von Neumann-arkitekturen. Den är mindre sofistikerad än Turings modell, men mer över­skådlig, och blev allenarådande i dator­tekniken. –– Pro­fessor Bernard Hodson (länk) i Kanada har ut­vecklat en modern programmerings­teknik baserad på Turings principer. –Mate­matikern Stephen Wolfram arrangerade 2007 en tävling om Turingmaskiner, se här. – Mike Davey beskriver hur han byggde en riktig Turingmaskin (se bilden) i denna artikel. – Richard Ridel har byggt en Turingmaskin av trä, se denna video.

[it-historia] [matematik och logik] [ändrad 12 mars 2018]

mekanisk

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 me­ka­niskt är att följa en al­go­ritm steg för steg från början till slut. –An­tag­andet 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.

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

Manchester Mark I

en av de första helt elektroniska datorerna, byggd 1949 vid Manchesteruniversitetet i England. Det var en av de första datorerna som kunde lagra program i minnet. In­mat­nings- och pro­gram­merings­systemet kon­stru­e­ra­des av Alan Turing. –Maskinen var en vidare­ut­veck­ling av SSEM (””Baby””). – Bland de som arbetade med Manchester Mark I fanns Conway Berners‑Lee och Mary Lee Woods, föräldrar till Tim Berners-Lee. –– Manchester Mark I var före­bild till Ferrantis första dator. – I USA fanns en annan dator med namnet Mark I. – Se historik från Manchesteruniversitetet (arkiverad).

[datorer] [it-historia] [ändrad 5 juni 2017]

ACE

  1. Foto av räksmörgås.
    xn--rksmrgs-5waolo

    ASCII compatible encoding –– metod att använda icke‑engelska tecken, som åäö, i domän­­namn. Det är egent­ligen omöj­ligt. Därför an­vänder ACE fortfarande bara bok­stä­verna i det engelska alfa­betet, alltså a‑—z, samt siff­rorna 09 och bindestreck. Problemet löses genom att andra tecken kodas som teckenkombi­­na­tioner. De byts auto­matiskt ut i webbläsare som klarar ACE. Med ACE kodas domännamnet www.räksmörgås.se som www.xn--rksmrgs-5waolo.se. Kodningen och avkodningen sköts normalt av ett pro­gram i webb­­läsaren, omärk­ligt för användaren, som bara skriver och läser namnet som räksmörgås. Liknande förvand­lingar kan göras i nästan alla skrift­­system, in­klu­sive ki­nesiska och japanska. – Observera att ACE bara är avsett för webben. Det fungerar inte för e‑postadresser. ”Åsa Häggström” på företaget ”Räksmörgås” bör ha e‑postadressen asa.haggstrom@raksmorgas.se, alternativt asa.haggstrom@xn--rksmrgs‑5waolo.se om företaget har registrerat den domänen. Det går inte att internationalisera första delen av e‑postadressen (personnamnet). – ACE är en övergripande beteckning på metoden för att göra andra teckensystem än det engelska alfabetet användbara på internet. Själva konverteringen görs med programmet ToASCII, som upptäcker de etiketter som innehåller tecken som behöver konverteras, och Punycode, som utför konverteringen. Efter konverteringen läggs prefixet xn-- till. – ACE ingår i systemet IDN, se Internationaliserade domän­­namn. – Läs också om internationalized resource identifier (IRI);

  2. – ACE –– Automatic computing engine – dator kon­stru­erad 1946 av Alan Turing. – En för­­enklad version av Turings kon­struk­tion, Pilot Model ACE, var klar 1950. Den var då världens snabbaste dator med en klockfrekvens på en mega­­hertz. Flera andra 1950‑tals­­datorer byggdes med ACE som före­bild, bland annat Deuce, som till­­verkades i 31 exemplar 1955——1963. – Se Wikipedia.

[datorer] [domäner] [förkortningar på A] [it-historia] [tecken] [ändrad 28 november 2018]

Gödel, Kurt

Porträtt av Kurt Gödel.
Kurt Gödel. Foto: IAS.

österrikisk-amerikansk matematiker och logiker (1906–—1978). – Kurt Gödels ofull­ständig­hets­sats från 1931 inspirerade Alan Turing till analysen av stoppro­blemet. – Ofull­ständig­hets­satsen visar att det inte kan finnas logiska och/eller matematiska system som på samma gång är hel­täckande och motsägelsefria. Med hel­täckande menas att regelsystemet kan tillämpas på alla påståenden som kan for­mu­le­ras inom systemet. I varje system av lagar, regler och symboler –– till exempel matematik –– kan man, visade Gödel, alltid hitta påstå­enden som uppenbarligen är sanna, men som inte kan bevisas inom ramen för systemet. Det går kanske att bevisa påstå­endet om man lägger till nya regler – men om man gör det så går det ofelbart att, med användning även av de nya reglerna, formulera nya påstå­enden som i sin tur inte kan bevisas, men som ändå uppen­bar­ligen är sanna. Detta bevisades i artikeln ””Über formal unentscheidbare Sätze der Principia Mathematica und Ver­wandte System”” (engelsk översätt­ning här). – I själva verket finns det två ofullständighetssatser, som hör ihop:

  • – Den första är den som beskrivs ovan;
  • – Den andra satsen säger att ett sådant system som beskrivs i den första satsen inte kan bevisa att det är mot­sägelse­fritt.

– Se också Ent­scheidungs­problem.– – Gödel lämnade Österrike efter den tyska ockupationen 1938 och fick då en tjänst på Institute of advanced study (ias.edu) i Princeton, New Jersey, där han blev god vän med Albert Einstein. – Gödelpriset är uppkallat efter Kurt Gödel. – En biografi över Kurt Gödel är Ofull­ständig­het: Kurt Gödels bevis och paradox (Incomp­lete­ness: The proof and paradox of Kurt Gödel, 2005) av Rebecca Gold­stein (webbplats).

[för- och bihistoria] [kurt gödel] [matematik och logik] [personer] [ändrad 23 april 2018]