Category:Theory of computation

A

• ► Algorithmic information theory‎ (17 P)
• ► Automata theory‎ (1 C, 86 P)

C

• ► Computability theory‎ (6 C, 95 P)

C cont.

• ► Computer arithmetic‎ (4 C, 98 P)

H

• ► Hypercomputation‎ (6 P)

M

• ► Models of computation‎ (13 C, 98 P, 1 F)

R

• ► Recursion‎ (4 C, 20 P)

T

• ► Turing machine‎ (27 P)

• Computability
• History of theory of computation
• Theory of computation

*

• List of undecidable problems

A

• Acceptable programming system
• Ackermann function
• Algorithmic game theory

B

• Blockhead (computer system)
• Bremermann's limit
• Brooks–Iyengar algorithm
• Busy beaver
• Byzantine fault tolerance

C

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

D

• Description number
• Digital physics

E

• Effective method
• Entscheidungsproblem
• 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 to computation
• List of computability and complexity topics

M

• Markov algorithm
• Model of computation
• 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
• Powerset construction
• Primitive recursive function

Q

• Quantum Byzantine agreement

R

• Range problem
• Real computation
• Recurrence relation
• Recursion
• Recursive language
• Recursive languages and sets
• Recursive set
• Recursively enumerable language
• Recursively enumerable set

R cont.

• Rice's theorem
• Rice–Shapiro theorem
• Rogers' equivalence theorem

S

• Scale factor (computer science)
• Self-reference
• Semi-Thue system
• Shadow square
• Simply typed lambda calculus
• Smn theorem
• Stream X-Machine
• Structured program theorem
• Sudan function
• Super-recursive algorithm
• SXM (computational model)

T

• Table-maker's dilemma
• Tail recursion
• Tarski–Kuratowski algorithm
• Ten15
• Transcomputational problem
• Turing completeness
• Turing degree
• Turing's proof
• Two Generals' Problem
• Two-way deterministic finite automaton
• Typed lambda calculus

U

• Undefined value
• Utm theorem

W

• Wang tile

X

• X-machine
• X-Machine Testing

Y

• Yao's test

Ω

• Ω-language