Beräkningsteori

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

Historia

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.

Universella modeller

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 hypotes. Ett känt problem som inte går att lösa med någon algoritm är stopproblemet: Det finns ingen algoritm som kan analysera alla andra algoritmer och avgöra huruvida de någonsin stannar.

Komplexitetsteori

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

• 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?
• Är det svårare att lösa ett visst problem än att hitta svar som ligger så nära den korrekta lösningen som vi vill?
• Kan vi med hjälp av slumptal effektivt hitta ett svar som är korrekt med en sannolikhet som är så nära 100% som vi vill?

Automatateori och formella språk

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

• reguljära uttryck, som används till att uttrycka mönstermatchningsvillkor
• ändliga tillståndsmaskiner som används vid kretsdesign och inom vissa domäner av problemlösning
• kontextfria grammatiker som används för att specificera programspråk

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.