User:Valepert/Books/Theory of computation
 | The Wikimedia Foundation's book rendering service has been withdrawn. Please upload your Wikipedia book to one of the external rendering services. |
 | You can still create and edit a book design using the Book Creator and upload it to an external rendering service:
|
| 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 Order a printed copy from: 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