Computers and Reality - Cognitive Science 110 - Spring 2007

1. Decide whether or not each of the following functions is computable, and explain your reasoning as clearly as you can.
   1.  

      f(x,y) = {

      1                 if  Px(y) does not stop undefined    otherwise

   2.  

      g(a,b,c,d) = {

      1                 if  Pa(b) and Pc(d) both stop undefined    otherwise

   3.  

      h(a,b,c,d) = {

      1                 if  Pa(b) stops or Pc(d) stops (or both stop) undefined    otherwise