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;
(Boolean) – boolesk logik, boolesk algebra – ett sätt att uttrycka logiska problem som matematik. – Boolesk algebra är uppkallad efter George Boole (mer om honom längre ner). – Två saker gör att boolesk logik passar för datorteknik:
– boolesk algebra löser logiska problem med matematiska metoder. Om du kan beskriva ett problem med den booleska algebrans termer så kan du sedan lösa det mekaniskt, vilket innebär att du kan programmera en dator att lösa problemet;
– boolesk algebra representerar logikens två sanningsvärdensant och falskt med den binära matematikens två siffror 1 och 0. Det passar bra för datorer, eftersom datorernas logiska kretsar (processorerna) också arbetar med två lägen, på och av. Datorernas kretsar är komplicerade tillämpningar av boolesk algebra.
– Boolesk algebra är inget konstigt: det är ett sätt att beskriva vanlig matematik och logik som råkar passa in på hur datorer är konstruerade. I boolesk algebra används villkoren AND (konjunktion), OR (disjunktion) och NOT (negation). Det finns fler logiska villkor än AND, OR och NOT, till exempel IF THEN (implikation) och XOR (exklusiv disjunktion). Men de tre booleska termerna räcker. Alla andra logiska villkor kan nämligen uttryckas med kombinationer av AND, OR och NOT samt parenteser. – Boolesk algebra är uppkallad efter logikern George Boole (1815—1864). Han strävade efter att förena formell logik och matematik i ett gemensamt symbolspråk. Booles principer kom till användning när de första datorerna konstruerades. – Boolesk uttalas ”bolsk” med O som i sol. – Mer i Wikipedia.) – Det engelska ordet Boolean används ibland i betydelsen binär, alltså när svaret på en fråga är ja eller nej, sant eller falskt, ett eller noll – inga mellanvärden. – Språkligt: Benämningen booleansk förekommer också på svenska, men den är onödig, eftersom det inte finns något som heter booleanism.
logikens term för eller. – Eller har två betydelser, nämligen ”A eller B eller båda” och ”A eller B men inte båda”. I det vanliga språket brukar det vara uppenbart vilket man menar. ”De tänker semestra i Kroatien eller i Costa Rica” betyder troligen inte att de tänker åka till båda länderna. Men i programmering måste man vara tydlig, så man skiljer mellan inklusiv disjunktion (A eller B eller båda) och exklusiv disjunktion (A eller B men inte båda). Om det bara står disjunktion betyder det inklusiv disjunktion. – I programmering står förkortningen OR för inklusiv disjunktion och förkortningen XOR för exklusiv disjunktion. I formell logik skriver man A∨B eller A∥B (två vertikala streck) för inklusiv disjunktion. – Läs också om NOR.
