Category:Theory of computation

A

• ► Algorithmic information theory‎ (21 P)

C

• ► Computability theory‎ (10 C, 96 P)
• ► Computational complexity theory‎ (15 C, 97 P)
• ► Computer arithmetic‎ (5 C, 125 P)

H

• ► Hypercomputation‎ (6 P)

L

• ► Limits of computation‎ (12 P)
• ► Limits to computation‎ (empty)

M

• ► Models of computation‎ (17 C, 115 P)

T

• ► Theorems in theory of computation‎ (1 C, 4 P)

• Computability
• Theory of computation

*

• List of undecidable problems

A

• Ackermann function
• Admissible numbering
• Algorithmic game theory

B

• Blockhead (thought experiment)
• Andreas Brandstädt
• Bremermann's limit
• Brooks–Iyengar algorithm
• Busy beaver
• Byzantine fault

C

• Chain rule for Kolmogorov complexity
• Chaitin's constant
• Church–Turing thesis
• Church–Turing–Deutsch principle
• Circuit (computer science)
• Communicating X-Machine
• Computable function
• Computable number
• Computation history
• Computation in the limit
• Computational semiotics
• Cylindric numbering
• Cylindrification

D

• Description number
• Digital physics

E

• Effective method
• Entscheidungsproblem
• Enumerator (computer science)
• Extended finite-state machine

F

• First Draft of a Report on the EDVAC

G

• Gödel numbering

H

• Halting problem
• History of the Church–Turing thesis
• Hypercomputation

I

• Interactive computation
• Introduction to the Theory of Computation

L

• Limits of computation
• List of computability and complexity topics

M

• Markov algorithm
• Mortality (computability theory)
• Μ-recursive function
• Mutual recursion

N

• Nomogram
• Nondeterministic algorithm
• Numbering (computability theory)

O

• Omega language

P

• Parallel computation thesis
• Parallel terraced scan
• Post correspondence problem
• Primitive recursive function
• Primitive recursive set function

Q

• Quantum Byzantine agreement

R

• Reachability problem
• Real computation
• Recurrence relation
• Recursion
• Recursive language
• Recursive set
• Recursively enumerable language
• Recursively enumerable set
• Rounding

S

• Scale factor (computer science)
• Self-reference
• Semi-Thue system
• Semiotic engineering
• Shadow square
• Simply typed lambda calculus
• Size-change termination principle
• Ludwig Staiger
• Stream X-Machine
• Sudan function
• Super-recursive algorithm
• SXM (computational model)

T

• Tail recursion
• Tarski–Kuratowski algorithm
• Ten15
• Transcomputational problem
• Turing completeness
• Turing degree
• Turing machine equivalents
• Turing tarpit
• Turing's proof
• Two Generals' Problem
• Typed lambda calculus

U

• Undefined value
• Universality probability

W

• Wang tile
• Workshop on Reachability Problems

X

• X-machine
• X-Machine Testing

Y

• Yao's test