User:Valepert/Books/Theory of computation

From Wikipedia, the free encyclopedia
Jump to: navigation, search
Theory of computation
State diagram 3 state busy beaver 2B.svg
This user book is a user-generated collection of Wikipedia articles that can be easily saved, rendered electronically, and ordered as a printed book. If you are the creator of this book and need help, see Help:Books (general tips) and WikiProject Wikipedia-Books (questions and assistance).

Edit this book: Book Creator · Wikitext
Select format to download:

PDF (A4) · PDF (Letter)

Order a printed copy from these publishers: PediaPress
About ] [ Advanced ] [ FAQ ] [ Feedback ] [ Help ] [ WikiProject ] Recent Changes ]


Theory of computation[edit]

Introduction
Turing machine
Universal Turing machine
Church–Turing thesis
Von Neumann architecture
Entscheidungsproblem
Neural network
Finite-state automata
Abstract machine
Automata theory
Linear bounded automaton
Pushdown automaton
Finite-state machine
Deterministic finite-state machine
DFA minimization
Nondeterministic finite-state machine
Alphabet
String
Formal language
Powerset construction
Myhill–Nerode theorem
Two-way deterministic finite automaton
Regular expressions & languages
Kleene star
De Morgan's laws
Pumping lemma
Pumping lemma for regular languages
Regular expression
Regular language
Star-free language
Decision problem
Decision problem
Halting problem
Grammars
Formal grammar
Terminal and nonterminal symbols
Chomsky hierarchy
Context-sensitive grammar
Context-free grammar
Concrete syntax tree
Backus–Naur Form
Chomsky normal form
Greibach normal form
Pumping lemma for context-free languages
CYK algorithm
Parsing
Parsing
Top-down parsing
Bottom-up parsing
Polish notation
Computability Theory
Computability
Turing completeness
Busy beaver
Recursive & nonrecursive functions
Primitive recursive function
Partial function
Μ operator
Quantification
Pairing function
Gödel numbering
Ackermann function
Sudan function
Recursive & r.e sets
Recursive set
Recursively enumerable set
Smn theorem
Rice's theorem
Kleene's T predicate
Post-Turing
Post–Turing machine
Non-deterministic Turing machine
Semi-Thue systems & word problem
Semi-Thue system
Post canonical system
Phrase structure grammar
Production
Post correspondence problem
Diophantine equations & lamdba calculus
Hilbert's tenth problem
Diophantine equation
Diophantine set
Lambda calculus
Complexity
Blum axioms
Gap theorem
Blum's speedup theorem
P versus NP problem
P
NP
Cobham's thesis
Polynomial-time reduction
Cook–Levin theorem