• Discussion on DFA and how it does not capture all computation
• Turing machine and its motivation: finite character set, finite states, infinite tape, head.
• Problem formulation of Program Equivalence, Halting Problem
• What if the tape was finite-size? Discuss brute-force algorithm
• Intuition on why infinite-tape halting/equivalence problem is undecidable. If a machine that determines whether a TM halts exists, then how many states should it have? What if the input TM to this machine has more states?
• Undecidability Proof (see below)
• Why the proof will fail on finite-tape machine? Cannot be sure if "g" will not have more states than the limit on the finite-tape machine.
• Reduction of the halting problem to program equivalence.
• Discussion on why the program equivalence problem discussed last time is undecidable. Small number of variables, then why do we need to model as infinite tape?
• Discuss brute-force algorithm based on finite bitvectors. How many states will the Turing machine of the brute-force algorithm have?

Undecidability

• let h(i, x) = 1 if i halts on input x, and 0 otherwise
• Assume that a turing machine exists that always terminates and correctly computes h
• Construct g(i) = 0 if if h(i,i) = 0, and spins forever otherwise. Notice that g(i) will probably have more states than h(i, i).
• What is the value of h(g, g)? Contradiction!