* 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.)

So I have these 3 problems. there is no book for the class. any direction to point in any of them would be AMAZING

**0**

# CS Logic Questions?

Started by Mercenary(FH), Nov 03 2009 07:05 PM

No replies to this topic

#### 0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users