Please enable JavaScript.

Coggle requires JavaScript to display documents.

Theory Of Computing - Coggle Diagram

- - - - Lambda Calculus
        Alonzo Church
      - Turing Machines
        Alan Turing
      - Church-Turing Thesis
        Any real-world computation can be translated into an equivalent computation on a Turing Machine
  - - - Informal
        
        Machine
        
        Turing Machine, M
        
        Finite set of states, Q
        
        Semi-infinite tape delimited on the left by endmarker |-
        
        A head that moves left and right on the tape, reading and writing symbols
        
        Input string that is of finite length, written on contiguous cells starting with |-, followed by infinitely many cells on the right with blank symbol |_|
        
        Transitions
        
        M starts in initial state s, head scans endmarker |-
        
        At each step, M reads symbol on tape under head, and, depending on current symbol, writes a new symbol and moves either left or right
        
        Action taken at each step is determined by a transition function sigma
        
        Transition is deterministic
        
        M accepts input after entering accept state t
        
        M rejects input after entering reject state r
        
        M may loop and run indefinitely without even accepting or rejecting input
      - Formal
        
        Machine
        
        M = (Q, Σ, Γ, |-, |_|, δ, s, t, r)
        
        Q is a finite set of states
        
        Σ is a finite set (input alphabet)
        
        Γ is a finite set (tape alphabet) s.t. Σ ⊆ Γ
        
        |- ∈ Γ \ Σ is the left endmarker
        
        |_| ∈ Γ \ Σ is the blank symbol
        
        δ : Q x Γ -> Q x Γ x {L,R} is a transition functon
        
        s ∈ Q is the start state
        
        t ∈ Q is the accept state
        
        r ∈ Q is the reject state, with r /= t
        
        Transitions
        
        δ : Q x Γ -> Q x Γ x {L,R}
        
        δ(p, a) = (q, b, d)
        means when in state p scanning a on the tape, replace it with b, move head in direction d (left or right) and enter state q
        
        TM never modes off tape to left of endmarker, i.e. for all p ∈ Q there exists q ∈ Q such that δ(p, |-) = (q, |-, R)
        
        Once TM enters accept or reject state, it never leaves it, i.e. for all b ∈ Γ there exists c, c' ∈ Γ and d, d' ∈ {L,R} such that δ(t, b) = (t, c, d) and δ(r, b) = (r, c′, d′)
        
        State set and transition together are referred to as state control
    - - TM that accepts {a^n b^n c^n | n ≥ 0}
        
        TM starts in s, scans right to check if input string has form abc*
        
        Machine does not change anything (i.e. replaces each symbol with same symbol)
        
        TM replaces first blank symbol |_| with right endmarker -|
        
        TM scans left, erases first c, then first b, then first a until |-
        
        TM scans right, erases one a, one b, one c
        
        TM continues same process
        
        If TM sees one occurrence of a letter and no occurrence of another, it rejects
        
        If TM erases all letters, and only blanks between |- and -| remain, it accepts
    - - Total Turing Machines
        A TM that halts on every input
      - Recursive Languages
        A language is recursive if there exists a Turing Machine that accepts on all strings in the language and rejects on all strings (over the same alphabet) that are not in the language
      - Recursively Enumerable Languages
        A language is recursively enumerable if there exists a Turing Machine that accepts on all strings in the language and does not accept all strings (over the same alphabet) that are not in the language - can reject or loop.
      - Recursive ⊂ Recursively Enumerable
      - Rejecting =/= Not Accepting
      - Proofs
        
        Recursive sets are closed under complement
        
        Given a TM M that accepts A, construct a TM M' that accepts -A
        
        This can be done by swapping the accept and reject states
        
        Since A is recursive, all inputs either accept or reject so...
        
        M' accepts Σ* - A and rejects A
        
        Therefore, a Turing Machine exists that accepts exactly the complement of A and is still recursive as accept states and reject states = Σ*
        
        Lemma: If L and -L are r.e. then L is recursive
        
        Let's say there are two TMs M1 (which accepts L) and M2 (which accepts -L)
        
        Assume there is a TM N that simulates M1 and M2 such that when M1 accepts, N accepts and when M2 accepts, N rejects.
        
        This means that N accepts the same language as M1.
        
        Since M1 accepts everything in L, it never hangs for L
        
        Since M2 accepts everything in -L, it never hangs for -L
        
        This means that N will not hang on any string, making it total.
        
        Since the language of N is total and L is its language then L is recursive.
        
        This proof requires constructing the TM N. This can be done with a double-tape Turing Machine.
        
        Lemma: If L r.e. but not recursive, -L is not r.e.
        
        Assume there is a TM M1 that accepts L and TM M2 that accepts -L.
        
        If L is r.e. but not recursive then M1 must loop on some strings that are not in L, a.k.a -L
        
        If -L were r.e. then M2 would have to accept for all strings not in L.
        
        Since we know that some of these loop, M2 cannot accept on every string in -L.
        
        Therefore there is not TM for -L that accepts for every string in -L.
        
        Therefore, L is not r.e.
      - Decidable Properties
        
        Property
        A property of a string is a predicate that tells you something about the string. It is either true or false. For example:
        
        The string has length 2 : {w | #w = 2}
        
        There is a letter ‘g’ in the string : {w | ‘g’ ∈ w}
        
        Decidable Property
        A property is decidable if all strings with that property form a language that is recursive.
        
        For example: the property that the given string is equal to “duwang” (because all finite languages are recursive)
        
        Semi-decidable Property
        A property is semi-decidable if all strings with that property form a language that is recursively enumerable
        
        For example: the property that the given string is an encoding for a Turing Machine that halts (you can simulate the TM and accept if it halts, but if it loops, then your simulation will loop, making this recursively enumerable but not recursive).
    - - Single-tape TMs have the same power as multi-tape TMs as single tapes can be encoded to act like multi-tapes
      - Simulating Turing Machines
        
        Simulating a TM M on a TM U
        There exists a TM U s.t.
        L(U) = {M#x | x ∈ M}
        Where M#x is an encoding of input x on an encoding of M
      - Encoding Turing Machines
        The detailed process is not too important.
        The rough idea is to encode a turing machine by a bunch of numbers and represent the numbers as an amount of 0s separated by ones.
      - Constructing a UTM
        Rules for encoding could be almost anything, this is just one example.
        
        Step 1:
        Check if input string M#x is of the right encoding
        
        Step 2:
        Use three tapes to store:
        
        Description of M
        
        Contents of M's tape
        
        M's current state and position on tape
        
        Step 3:
        Loop through the following steps:
        
        Looks at M's current state and head position (tape 3)
        
        Reads the tape contents at the correct position (tape 2)
        
        Reads the relevant transition (tape 1)
        
        Simulates transition, updating tape, state and head position
        
        Accepts if M accepts; Rejects if M rejects
  - - - Informal
        Can you come up with a TM that takes M#x as input and accept if M halts on X and rejects if M loops on x
      - Formal
        Is the set HP = { M#x | M halts on x} recursive
    - - No
    - - Proof by contradiction
      - Proof by diagonalisation
  - - - State-Entry Problem (SEP)
        Decide whether a TM M’ enters a given state q on input x
      - Blank Tape Halting Problem (BTHP)
        Decide whether a TM M’ halts on the blank tape (no input).
        Decide whether a TM M’ halts on input epsilon.
      - Emptiness Problem (EP)
        Semi-decide whether the language of a TM M’ is the empty set
      - Same Language Problem (SLP)
        Decide whether TMs M1 and M2 accept the same language.
    - - If A reduces to B and B is r.e then A also r.e.
        If A ≤ B and B r.e. then A r.e
      - If A reduces to B and A not r.e. then B is not r.e either
        If A ≤ B and A r.e. then B r.e.
      - If A ≤ B then there is a reduction function f : A -> B
      - If A reduces to B and B is recursive then so is A
        If A ≤ B and B recursive then A also recursive
      - If A reduces to B and A is not recursive then neither is B
        If A ≤ B and A not recursive then neither is B
  - - - Informal
        Can you come up with a TM that decides whether another TM will accept an input x
- - - - Final State
      - Empty stack
  - - - Chomsky Normal
      - Greibach Normal
- - - - Informally
        If an algorithm f(n) is ϴ(g(n)) where g(n) is an equation, then the algorithm's complexity scales with g(n) and can do no better or worse
        If an algorithm f(n) if ϴ(g(n)) then g(n) is the asymptotic upper and lower bound of f(n)
      - Formally
        For c>0, d>0, integer M>0
        dg(n) ≤ f(n) ≤ cg(n)
        For all n >= M
        f(n) and g(n) have the same rate of growth
    - - Informally
        If an algorithm f(n) is O(g(n)) then g(n) is the asymptotic upper bound on the complexity of f(n)
        f(n) cannot scale worse than g(n)
      - Formally
        For c>0, integer M>0
        f(n) ≤ cg(n)
        For all n >= M
        g(n) is the asymptotic upper bound for f(n)
  - - - Decision Problem
        For all inputs we receive a yes or no answer
      - Deterministic Turing Machine
        A Turing machine that cannot make any choices in terms of the next move
      - Solved in polynomial time
        -> The problem is feasible
    - - In P
        
        Searching an ordered list
        Use binary search, which is O(logn)
        
        Testing whether a list is sorted
        Go through the list sequentially and compare every element with the element before, which is O(n)
        
        Searching an unordered list
        Use sequential search, which is O(n)
      - Not in P
        
        Given a first-order statement about non-negative integer variables (with only symbols 0, 1, +, = and logical operators allowed), is it true?
        
        Decidable but infeasible
        
        Cannot be done in polynomial time with a deterministic machine
    - - Feasible
        A problem that has an algorithm with time complexity <= f(n)
        Where f(n) is some polynomial
      - Infeasible
        A problem that can be solved in finite time but has no polynomial time algorithm
    - - Problem Statement
        Given a directed graph, does there exist a directed path connecting two given nodes?
      - Solution Algorithm
        Mark the start node and mark all nodes it connects to and all the nodes they connect to.
        If end node is marked at the end then a solution exists.
        This runs in O(n*m) where n is number of nodes and m is number of edges
      - Complexity
        Polynomial
    - - Problem Statement
        Given a directed graph, does there exist a directed path connecting two given nodes that goes through each node exactly once?
      - Properties
        
        Verifiable in polynomial time
        
        The best solution is exponential, whether a better one exists is unknown
    - - Every regular language is in P
        O(n) so polynomial
        proof exists, learn it
      - Every context-free language is in P
        Can be converted to Chomsky Normal Form
        Then parsed with CYK algorithm in cubic time
        Accepts in cubic time
        O(n^3) so polynomial
  - - - Definition
        
        Formally
        Exactly the same as a TM but with a different transition function
        TM Transition Function:
        δ:(Q − {t, r}) × Γ →Q × Γ × {L, R}
        NTM Transition Function:
        δ:(Q − {t, r}) × Γ →P(Q × Γ × {L, R})
        Here you can see that the range of the transition function is now the powerset of possible configurations rather than just one.
        
        Informally
        At each configuration, a NTM has one or more possible subsequent possible configurations. It can be thought of as a TM that makes all possible transitions from a configuration in parallel
        Therefore, the computation of an NTM is a branch where all its branches are traversed in parallel
      - Simulating an NTM on a TM
        
        NTMs have the same expressibility as deterministic TMs
        
        NTMs can be simulated with a multi-tape deterministic TM
        
        The deterministic TM has four tapes
        
        One to remember the input
        
        One to remember the current state of the branch
        
        One to remember the branch being simulated on
        
        One to remember the branches simulated
        
        The deterministic TM accepts when one of the branches accepts and rejects otherwise
      - An NTM is a decider when all its branches halt on all inputs, similar to a total TM
    - - Definitions
        
        Size of the problem instance
        Number of symbols on the input tape
        
        The algorithm cost
        The number of steps the Turing machine takes
      - Time complexity of a decider
        A function f(n) where f(n) is the maximum number of steps the machine takes on any of its branches of computation, on any input of length n
      - Every t(n) time multi-tape deterministic TM has an equivalent O(t^2(n)) time single-tape deterministic TM
        There are t(n) steps to simulate, and for each we can find the heads in O(t(n)) time so for the whole simulation we require O(t^2(n)) time
      - Every t(n) time non-deterministic TM has an equivalent 2^( O(t(n)) ) time deterministic TM
        The time complexity of an NTM is the depth of the deepest leaf so each path we will stimulate will take no longer than t(n) time.
        Since the computation structure is a tree, there are b^(t(n)) path that we will need to simulate where b is the branching factor and t(n) = d (the depth the of the tree).
        Therefore, the simulation will take no longer than t(n) b^(t(n)) which is 2^( O(t(n)) ).
        We are essentially doing the time to simulate each path the number of paths
    - - SAT Problem
        
        Problem Statement
        Given a boolean expression, does there exist an assignment of true and false values such that the formula is satisfied
        
        Best Known Complexity
        NP
        
        Proof
        We can non-deterministically generate all possible assignments to the variables and then check if the formula is satisfied. Since an NTM always picks the correct assignment, it can solve the problem in linear time (the number of variables).
        However, a deterministic variable would require 2^n time where n in the number of variable at it would have to exhaust all possible branches to prove it is unsatisfiable.
      - HAMPATH Problem
        
        Problem Statement
        Given a directed graph, does there exist a directed path connecting two given nodes that goes through each node exactly once
        
        Best Known Complexity
        NP
        
        Proof
        We can non-deterministically generate all sequences of nodes of equal length to the size of the graph and then check the following
        
        No repetitions are found in the sequence
        
        The start and end of the sequence coincide with the required nodes
        
        The sequences define a directed path through the graph
      - TSP(D) Problem
        
        Problem Statement
        Given a graph with weighted edges and an input D, is there a route that goes through every node and ends back at the start with at most distance D
        
        Best Known Complexity
        NP
        
        Proof
        Non-deterministically guess the order of cities to check in, then add up the distances to see if its at most D
      - 3COL Problem
        
        Problem Statement
        Given a graph G, is it possible to colour all the nodes of G from one of three colours such that no two adjacent nodes share the same colour.
        
        Best Known Complexity
        NP
        
        Proof
        Non-deterministically guess the colour of each vertex; our computation at each step branches into each of the three colours
    - - We don't know
      - Consequences if it is
        
        P=NP=NP-COMPLETE
        
        proof exists, learn it
        
        P is a strict subset of NP-HARD
        
        proof exists, learn it
    - - A problem so hard to solve that it is not even in NP
      - It is decidable
      - It is a set of variables, each with either a for all or there exists.
        This is combined with an equation that contains the variables from the set.
      - Question is do these formulae hold?
      - Complexity
        At least doubly exponential
  - - - Informally
        If a problem A can be reduced to a polynomial problem B in polynomial time, then A is also polynomial.
      - Means that A reduces to B in polynomial time
      - Formally
        A function f : Sigma -> Delta is polynomial time computable if there exists a polynomial time deterministic Turing machine
      - Conclusions
        
        If A reduces to B in polynomial time and B is in P, A is also in P
        
        If A reduces to B in polynomial time and A in not in P, neither is B
    - - 3COL can be reduced to SAT in polynomial time
      - This can be done by creating a boolean formula with 3 variables for each node x is the graph: rx, gx, bx for is node x red etc.. These variables can be combined in three formulas:
        
        Union them all to say each node must have a colour
        
        Negate the ands of each length 2 subset of the variables to say each node must only have ONE colour
        
        Negate the AND of the same colour of x and y where x -> y to say that adjacent nodes cannot share the same colour.
    - - Theorem
        There exists a polynomial time reduction from any problem in NP to SAT.
      - Corollary
        If SAT in P, P=NP
  - - - SPACE(f(n))
        The collection of all languages that can be decided by an O(f(n)) space deterministic Turing machine.
      - NSPACE(f(n))
        The collection of all languages that can be decided by an O(f(n)) space non-deterministic Turing machine
    - - For each assignment of variables x0..xn, check if assignment satisfies formula. Accept if it does.
      - At any one time, only the following need to be stored:
        
        The current assignment, O(n)
        
        The evaluation of the formula, O(m) where m is the length of the formula
    - - Theorem
        If a decider runs in f(n) space then it also runs in 2^(O(f(n))) time
      - Proof
        There are at most |Q| * f(n) * 2^(O(f(n))) possible configurations
        
        |Q| is the number of configurations
        
        f(n) is the number of possible head positions
        
        2^(O(f(n))) is the number of possible tape configurations
        A decider will not repeat configurations (on any branch)
        So the longest the decider can run is |Q| * f(n) * 2^(O(f(n))) steps.
        This is equivalent to 2^(O(f(n)))
    - - PSPACE
        The set of all languages that can be decided by a deterministic Turing machine in polynomial space
      - NPSPACE
        The set of all languages that can be determined by a non-deterministic Turing machine in polynomial space
      - PSPACE is a subset of NPSPACE
      - Savitch's Theorem
        
        Theorem
        Every f(n) space non-deterministic TM, has an equivalent f(n)^2 space deterministic TM
        
        Corollary
        PSPACE = NPSPACE
      - PSPACE-Completeness
        
        PSPACE-Hard
        A language X is PSPACE-Hard if every language in PSPACE is polynomial-time reducible to X
        
        PSPACE-Complete
        A language X is PSPACE-Complete if it is in PSPACE and is PSPACE-Hard
        
        Why do these definitions use polynomial-time reductions rather than polynomial-space reductions?
        Completeness is only meaningful if you use reductions from a potentially smaller class. Every non-trivial problem in PSPACE is PSPACE-complete under PSPACE reductions. However, this is potentially not the case under PTIME reductions as it is a potentially smaller class.
        
        TQBF Problem
        
        Problem Statement
        Decide whether a fully quantified boolean formula is true
        
        Theorem
        TQBF is PSPACE-Complete
        
        Proof TQBF ∈ PSPACE
        
        Any tqbf can be rewritten to include quantifiers at the start in linear space
        
        Recursive algorithm for t.q.b.f on input <φ>:
        
        If φ of the form ∃x.ψ then call the algorithm on ψ[0/x] and ψ[1/x]. Accept if either accept
        
        If φ of the form ∀x.ψ then call the algorithm on ψ[0/x] and ψ[1/x]. Accept if both accept
        
        If φ contains no quantifiers, evaluate it. If true then accept
        
        This process uses O(n+m) space (where n is the number of variables and m is the size of φ)
    - - P ⊆ PSPACE
        Trivial, as it can never use more cells than it interacts with
      - NP ⊆ NPSPACE
        Similar to above
      - Savitch's Theorem => NP ⊆ PSPACE
      - PSPACE ⊆ EXPTIME
        Since if a decider runs in f(n) space then it runs in 2^O(f(n)) time
      - EXPTIME ⊆ EXPSPACE
      - All we know for sure is that P ⊂ EXPTIME
        (strict subset of)
- - - - Language
        The set of strings that can be made with an alphabet
      - Alphabet
        A set of symbols
    - - Deterministic Finite Automata (DFAs)
      - Non-deterministic Finite Automata (NFAs)
      - Regular Expressions (Regex)
      - Epsilon NFAs (eNFAs)
    - - A language is regular
        Construct a DFA / NFA / regex
      - A language is not regular
        Use the pumping lemma