Category:Theory of computation

A

• [+] Automata theory (1 C, 31 P)

C

• [+] Computational models (10 C, 88 P, 9 F)
• [+] Computer arithmetic (2 C, 126 P)

R

• [+] Recursion (3 P)
• [+] Reduction systems (empty)
• [+] Rewriting systems (2 C, 17 P)

T

• [+] Turing machine (28 P)

*

• Theory of computation
• Computability
• List of undecidable problems

A

• Acceptable programming system
• Ackermann function

B

• Big step semantics
• Blockhead (computer system)
• Bremermann's limit
• Busy beaver
• Byzantine fault tolerance

C

• Chain rule for Kolmogorov complexity
• Chaitin's constant
• Church–Turing thesis
• Church–Turing–Deutsch principle
• 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 number

H

• Halting problem
• History of the Church–Turing thesis

H cont.

• Hypercomputation

I

• Introduction to the Theory of Computation

K

• Kolakoski sequence

L

• Limiting recursive
• Limits to computation
• List of computability and complexity topics

M

• Markov algorithm
• Model of computation
• Mortality (computability theory)
• Mutual recursion

N

• Nomogram
• Nondeterministic algorithm
• Numbering (computability theory)

O

• Object-capability model
• Omega language

P

• Parallel computation thesis
• Parallel terraced scan
• Post correspondence problem
• Powerset construction
• Primitive recursive function
• Property testing

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
• Rice's theorem

R cont.

• Rice–Shapiro theorem
• Rogers' equivalence theorem

S

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

T

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

U

• Unsolved problems in computer science
• Utm theorem

W

• Wang tile

X

• X-Machine Testing
• X-machine

Y

• Yao's test

Μ

• Μ-recursive function