Berechenbarkeit und Komplexität - Zusammenfassung

Aus Infostudium Wiki

Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Computermodelle

Turingmaschine

  • Q endliche Zustandsmenge
  • \Sigma \supseteq \{0,1\} Eingabealphabet
  • \Gamma \subset \Sigma Bandalphabet
  • B \in \Gamma \setminus \Sigma Blank
  • q0 Startzustand
  • \bar{q} \in Q Endzustand
  • δ Übergangsfunktion (DTM), bzw. -relation (NTM)

Übergangsfunktionen

  • [DTM] \delta:(Q \setminus\{\bar{q}\})\times \Gamma\to Q\times\Gamma\times\{N,L,R\}
  • [k-Spur] \delta:(Q \setminus\{\bar{q}\})\times \Gamma^k\to Q\times\Gamma^k\times\{N,L,R\}
  • [k-Band] \delta:(Q \setminus\{\bar{q}\})\times \Gamma^k\to Q\times\Gamma^k\times\{N,L,R\}^k
  • [NTM] \delta\subseteq((Q \setminus\{\bar{q}\})\times \Gamma)\times (Q\times\Gamma\times\{N,L,R\})

RAM / Registermaschine

Mächtigkeit von Programmiersprachen

WHILE

LOOP

Komplexitätsklassen

Von „http://wiki.infostudium.de/wiki/Berechenbarkeit_und_Komplexit%C3%A4t_-_Zusammenfassung“