Home

Homework   Index   Syllabus   URM Simulator


Extra Homework Problems

Models of Computation - Mathematics 450 - Spring 2005


For HW #20

  1. Let f be a unary computable function. Let A = {x | x is an index of f}. Is A recursive? Prove your answer.
  2.  
    1. Is "Ex is infinite" partially decidable? Prove your answer.
    2. How about "Ex is finite"? Prove your answer.
    3. How about "Wx is infinite" and "Wx is finite"? Prove your answers.
  3.  
    1. Is "jx = jy" partially decidable? Prove your answer.
    2. Is "jx ¹ jy" partially decidable? Prove your answer.

Updated: 31 August, 2009 17:44:19