qraymo Garden

Powered by 🌱Roam Garden

TCS Summary - English - Backup

computability theory

number functions

μ\mu-Recursion

register machine

WHILE-computable

simulation ->

word functions

word functions

simulation -> Turing-Maschine

Church-Turing Thesis

μ\mu-Recursion

register machine

WHILE-computable

Turing-Maschine

Undecidability of the Halting problem

problems/sets

computational complexity theory

Turing-Maschine

types

deterministic turing machine (DTM)

nondeterministic turing machine (NTM)

Church-Turing Thesis

Undecidability of the Halting problem

complexity classes

Recognized by Turing-Maschine (Turingmächtigkeit)

PP = Languages recognized by DTM

NPNP = Languages recognized by NTM

PP ⊆\subseteq NPNP

Divided by time complexity

Divided by space complexity

PSPACEPSPACE == NPSPACENPSPACE

problems/sets

recursive

recursively enumerable

complexity classes

PP ⊆\subseteq NPNP
⊆\subseteq
PSPACEPSPACE == NPSPACENPSPACE
⊆\subseteq EXPTIMEEXPTIME

formal languages wip

{{table}}

chomsky hierarchy

generator
/
formal grammars

acceptor
/
automaton

recursively enumerable

type 0

Turing-Maschine

context-sensitive

type 1

linear-bounded automata

context-free

type 2

non-deterministic push down automata

regular

type 3

finite state machines

chomsky hierarchy

recursively enumerable

context-sensitive

context-free

regular

generator

formal grammars

type 0

type 1

type 2

type 3

acceptor

automaton

Turing-Maschine

linear-bounded automata

non-deterministic push down automata

finite state machines

problems/sets

TCS Summary - English - Backup