Jump to content

CS Logic Questions?

  • Please log in to reply
No replies to this topic

#1 Mercenary(FH)



  • Members
  • PipPipPipPipPip
  • 2979 posts
  • Interests:Obviously Dota ^_^<br />Anime<br />Manga<br />Computers (Building them and Fixing)<br />LoTR (Movies/Books)<br />Cars (Bmw's Especially)<br />Movies<br />Video games
  • Bnet Name:MercenaryFH
  • Bnet Realm:Azeroth

Posted 03 November 2009 - 07:05 PM

*  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 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users