====== 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 <code>/ασ/0α/
/ατ/1α/
/0σ/σ0/
/1σ/σ1/
/0τ/τ0/
/1τ/τ1/
/β1/τ1β/
/β0/σ0β/
/α//
/β// !
//αβ/
</code>

===== 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