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 Turingmaskin motsvarar ett modernt datorprogram, men när man talar om Turingmaskiner menar man ofta universella Turingmaskiner, som kan sägas motsvara 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 Turingmaskin 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. – Turingmaskinen har en pappersremsa som matas fram och tillbaka genom ett läs- och skrivhuvud enligt bestämda regler. Det finns flera uppsättningar regler som kallas för tillstånd, och i reglerna ingår övergångar från ett tillstånd till ett annat. Skrivhuvudet kan läsa, radera och skriva tecken på remsan. Man programmerar Turingmaskinen med tecken på remsan, och Turingmaskinen matar sedan, enligt reglerna, remsan fram och tillbaka, läser, raderar och skriver samt växlar tillstånd tills den kommer till en regel som säger ”stopp”. Då stannar maskinen och lösningen på problemet 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 problem som kan lösas med ett modernt datorprogram också lösas av en motsvarande Turingmaskin, men naturligtvis är det ogörligt att använda en maskin med pappersremsa. Man brukar därför simulera Turingmaskiner 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åndsmaskin. – Efter andra världskriget konstruerade Alan Turing en elektronisk 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 överskådlig, och blev allenarådande i datortekniken. – Professor Bernard Hodson(länk) i Kanada har utvecklat en modern programmeringsteknik baserad på Turings principer. – Matematikern 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.
– i programmering: ett logiskt villkor som betyder ”A eller B, men inte båda” – se exklusiv disjunktion;
– en enkel form av kryptering som bygger på det logiska villkoret XOR. Texten som ska kodas (klartexten) i binär form jämförs med en nyckel i binär form, bit för bit. Nyckeln är en serie ettor och nollor som vid behov repeteras tills den når slutet av texten. Om det finns samma tecken i klartexten och i nyckeln sätts en etta i kryptotexten, om det är olika tecken sätts en nolla. Detta räknas som en mycket enkel och riskabel form av kryptering.
multipelprefix för 1018, alltså en triljon – en miljon biljoner. En exabyte är tusen petabyte. Tusen exabyte blir en zetta-byte. – Ordet:Exa är ett påhittat ord som ska föra tankarna till latinets hexa för sex, därför att 1 följt av 18 nollor är lika med 1 0006.
uppdelning av en komplex signal (till exempel ljud eller video) i sinusvågor med olika frekvens. – Alla signaler som kan beskrivas som vågrörelser, hur oregelbundna de än är, kan nämligen delas upp i enkla, samtidiga sinusvågor. (En sinusvåg är den enklast tänkbara vågrörelsen.) Detta bevisades av den franske matematikern Joseph Fourier (1768—1830). Detta är bland annat användbart när man ska komprimera filer. En sådan operation kallas också för Fouriertransform. – Den äldsta metoden för Fourieranalys kallas för diskret Fourieranalys och är mycket tidskrävande. En snabbare metod är snabb Fourieranalys(fast Fourier transform, FFT), som bland annat används för komprimering av datafiler, i synnerhet av filer med musik och video. 2012 beskrev den amerikanska matematikern Dina Katabi(länk) med flera en ännu snabbare metod, sparse Fourier transform. En matematisk beskrivning finns här (pdf).
ett stort tal som skrivs som en etta följd av hundra nollor (med vanlig decimal notation). – Talet googol definierades av den amerikanska matematikern Edward Kasner runt 1920; namnet hittade hans systerson Milton Sirotta på. Talet blev känt 1940 genom Kasners populärvetenskapliga bok Mathematics and the imagination (svensk översättning Matematiken och fantasien, 1943). – Talet googolplex, även det definierat av Kasner, är 10 upphöjt till googol (alltså en etta följd av googol nollor). – Sökmotorn Google är uppkallad efter talet googol. – Fördjupning: Författaren och konstnären Vincent Carter Vickers gav 1913 ut barnboken The Google Book(länk). Där är Google en sagovarelse. Senare dök seriefiguren ”Barney Google” upp i serien Snuffy Smith (Tjalle Tvärvigg), och ordet google användes också i en populär sång på 1920‑talet. Så det antas att Milton Sirotta var påverkad av populärkulturen när han hittade på ordet googol. Sökmotorns stavning är alltså en omedveten återgång till ursprunget.
– i programmering: en serie tal i en bestämd ordning. (Ett slags datastruktur);
– i matematik: tecknad pil som beskriver en riktad kraft. Pilens längd visar kraftens belopp. – Ett mer abstrakt sätt att beskriva en vektor är att räkna upp koordinaterna för dess ändpunkter. Om vi ritar en vektor på rutat papper behöver vi två koordinater för startpunkten och två för slutpunkten, alltså fyra. Men man kan tänka sig vektorer som beskriver krafter i fler dimensioner, och då blir det fler siffror. Sådana sifferserier kan kallas för vektorer även om man inte ritar dem som en pil. Därav den datortekniska betydelsen, se ovan. – Man talar ibland om flerdimensionella vektorer, men då menar man att vektorn beskriver en kraft i en flerdimensionell rymd. Själva vektorn, alltså talserien, är alltid endimensionell (en rät linje). Därför är det skillnad mellan en vektor och en array: en array kan vara flerdimensionell, men det kan inte en vektor. – Se också tensor;
eller sanningsvärdestabell, på engelska truth table – tabell som åskådliggör vad som krävs för att ett logiskt uttryck ska anses som sant eller falskt. Sant och falskt kallas för sanningsvärden. – En sanningsvärdetabell för en logisk konjunktion(OCH) ser ut så här:
– Båda påståendena A och B är sanna, alltså A och B (A∧B):
A
B
A ∧ B
sant
sant
sant
sant
falskt
falskt
falskt
sant
falskt
falskt
falskt
falskt
– Tabellen åskådliggör att, till exempel, ett påstående som ”Sverige är en monarki och Norge är en monarki” är sant bara om det är sant att Sverige är en monarki och sant att Norge är en monarki. Om något (eller båda) av påståendena skulle vara falskt är det sammansatta påståendet också falskt. – En sanningsvärdetabell kan sammanfattas genom att man tar värdena i spalten längst till höger, uppifrån och ner, och markerar sant med 1 och falskt med 0. För tabellen här ovanför, konjunktion, blir det alltså 1000, och om man ser 1ooo som binär notation motsvarar det 8.
