CS 375 HW 4

• Show that the language Fin = {x: M_x accepts only finitely many inputs} is not decidable.
• Show that Fin is not enumerable (in the sense of "not semi-decidable").
• Is the following graph theory problem decidable? If so, give an algorithm; if not, give a reduction from some other undecidable language.
  GraphIso = {(G,H): G and H are isomorphic graphs} .
  Remember that G = (V, E) and H = (U, F) (vertices, edges) are isomorphic iff there is an isomorphism h from V to U such that (vi, vj) is an edge in E iff (h(vi), h(vj)) is an edge in F, and (ui, uj) is an edge in F iff (h^{-1}(ui), h^{-1}(uj)) is an edge in E. (h^{-1} is the inverse function for h.)