Theory of Computation: HIERARCHY

• TOC subfields

  • Theory of computation (general)

  • Automata theory

  • Formal languages

  • Computability theory, Recursion theory

  • Complexity theory

• TOC: general

  • limits of computation

  • efficiency of algorithms

  • efficient computing method

  • Turing thesis

  • Church thesis

  • Church-Turing thesis

  • abstract machine

  • virtual machine

• Automata theory

  • automata and recognized language correspondance

  • finite state machines (FSM)

    • finite automata (FA)

    • deterministic finite automata (DFA)

    • nondeterministic finite automata (NDFA)

    • NFA to DFA conversion

    • NFA to DFA equivalence

    • Mealy Machine

    • Moore Machine

  • Pushdown automata

  • Pushdown automata (with extras)

  • Turing machine

• Turing machines

  • Turing machine (TM)

  • Universal Turing machine (UTM)

• Formal languages

  • formal language

    • symbols

    • alphabet

    • strings

    • well-formed strings

    • grammar

    • rewrite rules

  • regular expression

  • context free language (CFL)

  • context free grammar (CFG)

  • context dependent language

• Computability Theory, Recursion theory

  • Models of computation

  • Primitive Recursion theory

  • Computation by abstract devices

  • Halting Problem

  • Decidability

  • Tractability

• Complexity Theory

  • Analysis of algorithms

  • Numerical algorithms

  • Non-numerical algorithms

  • Complexity of algorithms

  • Tradeoffs between complexity measures

• Models of computation

  • Turing machine

  • Lambda calculus

  • Combinatory logic

  • SKI calculus

  • Post-Turing machine