bit string encoding encode a finite string in \Sigma^{*} as a bit string: encoding each character in \log | \Sigma | bits (by basically IDing each bit). For x \in \Sigma^{*}, define b_{\Sigma}(x) to be its binary encoding. For x,y \in \Sigma^{*}, to encode the pair of strings x and y, we can encode tuples by adding just a separate symbol \Sigma’ = \Sigma \cup \left\{,\right\}, and then we can write x,y. (if we want to know how long x is ahead of time we can encode it by show you how long it is through zeros early—0^{|b_{\Sigma} (x)|} 1 b_{\Sigma}(x) b_{\Sigma}(y). Turing Machine Encoding we can encode a turing machine just by writing out its each part. n state count, m tape symbol count (where the first k are input symbols), s start state id, t accept state id, r reject state id, u blank symbol ID, transitions (p,i), (q,j, D) (i.e. start state, start tape, next state, next tape, movement directions) the key is that this is constant size being able to encode computation means that we can have languages defined by computation— A_{DFA} = \{(B,w) \mid B encodes a DFA over some \Sigma, and B accepts w \in \Sigma^{*} \} A_{NFA} = \{(B,w) \mid B encodes a NFA over some \Sigma, and B accepts w \in \Sigma^{*} \} A_{TM} = \{(B,w) \mid B encodes a TM over some \Sigma, and B accepts w \in \Sigma^{*} \} (we will use a decoding such that any string decodes to a pair (A,b), no matter if its useful or not—so we don’t need to typecheck things; in particular, if there’s some x which doesn’t decode correctly, we just return (D, \varepsilon) where D accepts nothing and \varepsilon remains to be the empty string.) This means that:

Universal Turing Machine Theorem There exists a Turing machine U which takes as input: the code of an arbitrary Turing machine M an input string w such that U accepts (M,w) IFF M accepts w. That is, U recognizes A_{TM}. i.e.: U runs every Turing machine (think: programmable computers). Which, btw, isn’t true of DFA/NFAs—the languages A_{DFA} and A_{NFA} is not regular (in some sense, U is the “hardware” which drives the corresponding “software”) A_{DFA} is decidable Because a DFA is a special case of a Turing Machine. So we can run the Universal Turing machine on it and output its answer (we know DFAs terminate)—they always accept or reject. A_{NFA} is decidable perform subset construction, then do what’s above (i.e. treat the DFA as a TM) A_{TM} is recognizable but not decidable We want to show that A_{TM} is recognizable but not decidable; and \neg A_{TM} is not recognizable (since A_{TM} is only recognizable and not decidable, we know that \neg A_{TM} can’t even be recognizable; otherwise, we would satisfy L is decidable IFF L and not L are both recognizable and that would make A_{TM} decidable). A_{TM} is undecidable constructive proof Suppose we have a H that recognize A_{TM}.

let us define a new machine D which runs the encoding of M on M: which run H on (M,M) and output the opposite of H if it does halts; otherwise, D keeps looping.

plugging in D for M, note that the first two options are still impossible but the last option is possible (“D loop if D loops on D”). So D must loop on D. Hence, \left(D_{h}, D_{h}\right) is not in A_{TM} (it loops), yet H loops on it instead of rejecting it. So A_{TM} is undecidable. contradiction proof Suppose there is a machine H which decides A_{TM}. This means that:

let us define a new machine D which runs the encoding of M on M: which run H on (M,M) and output the opposite of H (exists since we assumed that A_{TM} is decidable (terminating)).

In particular, note that this has the same problem of there are non-recognizable languages — if we ran D(D), if D(D) accepts, we have the property that D didn’t accept D; if D(D) rejects, then have the property that D accepts D. This reaches a contradiction.