Category:Theory of computation

A

• Algorithmic information theory (22 P)

C

• Computability theory (10 C, 102 P)
• Computational complexity theory (14 C, 114 P)
• Computer arithmetic (5 C, 136 P)

H

• Hypercomputation (6 P)

L

• Limits of computation (12 P)

M

• Models of computation (19 C, 126 P)

T

• Theorems in theory of computation (1 C, 5 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
• List of computability and complexity topics
• Computable function
• Computable number
• Computable set
• Computably enumerable set
• 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
• International Conference on Reachability Problems
• Intersection type discipline
• Introduction to the Theory of Computation

L

• Limits of computation

M

• Markov algorithm
• Mortality (computability theory)
• General 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 analysis
• Reachability problem
• Recursion
• Recursive language
• Recursively enumerable language
• 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
• 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

X

• X-machine
• X-Machine Testing

Y

• Yao's test