Beräkningsteori

Från Wikipedia
Hoppa till: navigering, sök

Beräkning (engelska: Computation) kan definieras som sökandet efter en lösning på ett problem från ett givet indata med hjälp av en algoritm. Beräkningsteori, som är en underdisciplin till matematik och datavetenskap, behandlar analys av problem, indata och algoritmer.

Historia[redigera | redigera wikitext]

I tusentals år gjordes beräkningar med papper och penna eller i huvudet. Beräkningsteorin uppstod i början av 1900-talet, innan moderna datorer gjorde sitt intåg. Vid den tiden arbetade matematiker med att försöka avgöra vilka problem som var lösbara med enkla metoder och vilka som inte var det. Det första steget i detta arbete var att definiera vad som var en ”enkel metod” för att lösa ett problem, vilket ledde till behovet av en formell modell för vad en beräkning egentligen är.

Tidiga modeller[redigera | redigera wikitext]

I dessa tidiga år föreslogs många olika modeller för beräkningar. En känd modell, Turingmaskinen, lagrar symboler på ett oändligt långt band, där en ruta i taget behandlas av maskinen genom att innehållet läses, en beräkning äger rum och resultatet skrivs tillbaka i samma ruta.

En annan modell, rekursiva funktioner, använder matematiska funktioner och funktionskomposition för att utföra sifferoperationer.

Lambdakalkyl fungerar på ungefär samma sätt. Ytterligare modeller, såsom Markov-algoritmer och Post-system, använder grammatikliknande regelsystem för att utföra operationer på strängar.

Alla dessa formaliseringar visade sig med tiden besitta samma beräkningskraft – dvs, en beräkning som kan utföras enligt en modell kan också utföras med vilken som helst av de andra. Detta gäller teoretiskt såväl som applicerat i samband med moderna datorer om man antar att en dator har oändligt minne.

Det är en mycket spridd uppfattning att alla väldefinierade formaliseringar av begreppet algoritm har samma beräkningskraft som en Turing-maskin, vilket är formulerat i Church-Turings sats.

Beräkningsteori[redigera | redigera wikitext]

Beräkningsteori behandlar modeller för generella beräkningar tillsammans med de begränsningar som dessa har när de implementeras med datorer:

  • Vilka problem är – säkert eller förmodat – olösliga för en dator?
  • Vilka problem kan lösas av en dator, men som kräver så långa beräkningstider att lösningen inte är användbar?
  • Kan det vara svårare att lösa problemet med en dator än att kontrollera en given lösning till problemet?

Frågor som dessa behandlas av komplexitetsanalys.

Andra användningsområden[redigera | redigera wikitext]

Utöver modeller för generella beräkningar studeras även några enklare beräkningsmodeller som är användbara för vissa speciella avgränsade användningsområden, såsom

Beräkningsteori och formella språk[redigera | redigera wikitext]

Olika beräkningsmodeller är lämpade för olika typer av problem. Ett sätt att mäta beräkningskraften i en viss modell är att studera den klass av formella språk (se formell grammatik) som modellen kan generera. Dessa klasser finns beskrivna i den så kallade Chomsky-hierarkin.