Computers and Reality - Cognitive Science 110 - Spring 2007

1. What does Church's Thesis say? State as many known facts as you can that support Church's Thesis.
   
   In the following problems you may assume these functions are computable:
   Mult(x,y) = xy;
   Dec(x) = x-1 if x >0, undefined otherwise;
    
2. Use Church's Thesis to show that the following function is computable:
   Qt(x,y) = x/y if y|x, undefined otherwise.
3. Use Church's Thesis to show that the predicate "x divides y" is decidable.
4. Use Church's Thesis to show that the function Fac(x) = x!  is computable. (Recall that x! = (1)(2)(3)...(x-1)(x). )
5. Use Church's Thesis to show that the function gcd(x,y) = "greatest common divisor of x and y"  is computable.
   Examples: gcd(10,15)=5;  gcd(25,6)=1.
   By convention, every positive integer divides 0; so gcd(0,8)=8, and gcd(0,0)=0.
   You may assume that "x divides y" is decidable.