Computability Theory
    Concerned with what can and cannot be computed
    How Hilbert kind of started this all off
    Wadler’s video on the history of computability
    Bernhardt's Book
    Equivalent models of computation
        Turing Machines
        Register Machines
        Lambda Calculus
        Recursive Functions
        Semi-Thue Systems
        Post’s Production Systems
    Church-Turing Thesis
    Why is there a limit to what can be computed?
        Counting argument
            # of possible programs is countable; # of possible functions is uncountable
        Diagonalization argument
            Works for both functions in N->N and N->B
    The first non-decidable function
        Halting Problem
        Demonstration in Python
        Setting up the contradiction
    Decidability
        Definition of decidable
            Decidability is a property of languages
    Recognizability
        Recognizable = algorithm must always halt and answer yes for utterances
        Decidable = algorithm must always halt and answer yes or no for utterances
        Recognizers may loop forever on rejections
        Deciders must always halt on all inputs
        Halting Language H is recognizable but not decidable
        Recognizable language == Recursively enumerable language
        Decidable language == Recursive language
    Nonrecognizability
        First nonrecognizable language is language of machines that don’t recognize themselves
            What does this really mean
            Diagonalization proof
    Reductions
        Reducing A to B
            means solving B to solve A
        If A is undecidable and A reduces to B, then B is undecidable
        Example with the empty language
    Rice’s Theorem
        Any nontrivial property of the language recognized by a Turing machine is undecidable
        Nontrivial means some machines have the property and some don’t
        Examples of properties that are undecidable
            Is the language empty?
            Is the language finite?
            Is the language regular?
            Is the language context-free?
            Does the language contain a particular string?
            Does the language contain all strings?
        Applications in real life (esp correctness and security)
    Busy Beavers
        Why Study
        Different definitions
            but we focus on the “number of steps” variety, originally S, now called BB
        Number of n-state Turing Machines
        A list of the first few champions
        BB is not computable (can show via reduction from the Halting Problem)
        Fun fact: BB grows faster than any computable function
    Computable numbers
    Oracles
    Connections to Complexity Theory
Complexity Theory
    Motivation
        Computability asks what can be computed; complexity asks what can be computed efficiently
        Classifies problems by the time and space resources needed to solve them
    Time and Space
        Traditional models: Turing Machines, Boolean Circuits, Interactive Proof Systems
        Variations: parallel, probabilistic, quantum
        TM time = number of steps (state transitions); space = tape cells used, not counting the input
        Models must be realistic: finite, operating on finite inputs, instructions take finite time
        T(n) = max steps over inputs of size n; S(n) = max non-input cells over inputs of size n
        Complexity measures are model-dependent, so always specify the model
    Computational Models
        Single-tape Turing Machines
            Worst case, best case, and average case
            Increment machine: T(n) = 2n + 2 worst case, S(n) = 1
            String reversal: T(n) = 2n^2 + 3n + 1 (quadratic)
        Multitape Turing Machines
            Two-tape reversal: T(n) = 2n (linear)
            Often more realistic, and polynomially related to single-tape machines
        Random access and register machines
            Count bits, not unbounded registers
            Bounded registers can be counted as units (constant factor difference)
        Nondeterministic machines
            Accept if some computation path accepts; measure time and space on accepting paths
            Model verification; deterministic machines simulate them by backtracking
        Probabilistic machines
            Coin-flip states; accept if acceptance probability exceeds a threshold (1/2 or 2/3)
        Parallel machines
            Sub-machines each perform their own steps independently
        Boolean circuits
            DAG of AND, OR, NOT gates; complexity by size, depth, and fan-in
            Families of circuits, one per input size
            4-bit adder example: size 17, depth 7, fan-in 3
        Quantum machines
        Interactive proof systems
            Prover and verifier exchange messages to decide a language
    Input Encoding
        Encoding can change complexity (sign bit vs. parity of a binary number)
        Constant-factor differences (decimal vs. binary) are insignificant
        Unary encoding is not appropriate: it makes complexities look far smaller than they are
    Asymptotic Complexity
        Drop lower-order terms and leading constants
        Big-O: asymptotic upper bound
        Big-Omega: asymptotic lower bound
        Big-Theta: tight bound (upper and lower bounds match)
        Little-o and little-omega
        Soft-O: ignores polylogarithmic factors
        Caveats: only meaningful for large n; large constants matter for small n; not absolute running times; an upper bound need not be tight
        Growth rates: constant, logarithmic, linear, linearithmic, quadratic, polynomial, quasipolynomial, exponential, factorial, n^n, and beyond
        Concrete running times at one million operations per second
        Polynomial = tractable (easy); exponential = intractable (hard)
        Polynomially related models can be varied freely
    Complexity Classes
        Recast problems as language membership questions
        Generic classes: DTIME(f), DSPACE(f), NTIME(f), NSPACE(f)
        Core classes: L, NL, P, NP, PSPACE, NPSPACE, EXP, NEXP, EXPSPACE, NEXPSPACE
        Known containments: L ⊆ NL ⊆ P ⊆ NP ⊆ PSPACE ⊆ EXP ⊆ NEXP ⊆ EXPSPACE
        PSPACE = NPSPACE and EXPSPACE = NEXPSPACE
        Known proper containments: P ⊊ EXP; L ⊊ PSPACE ⊊ EXPSPACE
        Unknown whether the other containments are proper
        Complexity Zoo: REG, CFL, R, RE, LIN, NLIN, QP, AC0, NC, P/poly, SZK, MA, AM, QMA, BPP, PP, RP, ZPP, BQP, and more
    Hardness and Completeness
        C-hard: every problem in C reduces to it; C-complete: C-hard and in C
        Reductions must be efficient for the context and come from a strictly smaller class
        Generalized Go is EXP-complete; Generalized Othello is PSPACE-complete
    P and NP
        P: problems solvable efficiently; NP: problems whose YES answers can be verified efficiently
        One NP-complete problem in P would prove P = NP; one not in P would prove P != NP
        NP-complete examples: SAT, Traveling Salesperson, Knapsack, Graph Coloring, Hamilton Cycle, Vertex Cover, Clique, Subset Sum, Sudoku
        Special cases in P: 2-SAT and Horn SAT, 2-coloring, vertex cover on bipartite graphs and trees, TSP on trees
        Mirror problems in P: Euler Tour vs. Hamilton Cycle, Edge Cover vs. Vertex Cover, Maximum Matching vs. Independent Set, Max Flow vs. Min Flow
        Proof barriers: relativization, natural proofs, algebrization
        If P = NP: galactic algorithms change nothing; practical algorithms would transform routing, drug design, and cryptography
        Dealing with NP-completeness today: intelligent backtracking, special cases, randomization and heuristics, approximation algorithms
    Open Problems
        P vs. NP and the other open containments
        Wikipedia's list of unsolved problems in computer science