Berechenbarkeit

Komplexität von Algorithmen und Problemen
Grenzen Aufzeigen
Berechnungsmodelle

Problemkategorien

O(1) - Lookup
O(log n) - Binärsuche in einer Sortierten Liste
O(n) - majority, max, …
O(n log n) - sortieren z.b. heap sort
O(n^x) - Polynomiell → P
O(x^n) - Exponentiell z.B. TSP → NP

Aber es hängt von Modell ab. Die Muster in erweiterten MA sind mächtig und weisen versteckte laufzeitkosten auf. → Reduktion auf das einfachste mögliche Modell - ohne prinzipiell etwas zu verlieren. bei den MA → einzige Textliterale sind zulässig.

Primfaktorzerlegung

Siehe Serie X

Reduktion auf Suchliterale

Bespiel: Eingabe Verdoppeln /(.*)/$1$1/ ! wird über ein Alphabet {0, 1} zu

/ασ/0α/
/ατ/1α/
/0σ/σ0/
/1σ/σ1/
/0τ/τ0/
/1τ/τ1/
/β1/τ1β/
/β0/σ0β/
/α//
/β// !
//αβ/

Universeller Markov-Algorithmus

Ist ein MA der als Eingabe I = (ma, i) einen MA m und eine Eingabe i entgegen nimmt und die MA m auf die Eingabe i anwendet (simuliert).

Problem: Hört die Ausführung von ma auf i irgend einmal ab → Halteproblem.

Interessante Frage Stellung: Gibt es einen Algorithmus der Entscheiden kann ob eine MA m für die Eingabe i haltet?

→ wird