Models of Computation - Mathematics 352 -
Fall 2009
For HW #6
These problems are optional.
- Without writing any programs, prove the function f(x)=x+3 is
computable. (You may assume the function "x+y" is computable, and
you may use Problem 1 on page 32.)
- Without writing any programs, prove the function f(x) = mx+n, where
m and n are fixed natural numbers, is computable. (You may assume the
functions "x+y" and "xy" are computable, and you may use Problem 1
on page 32.)
- Assuming that the function g(x,y) = xy is computable, prove that for
every computable function h(x) and for every natural number n, the
function (h(x))^n is computable.
- Assuming that the function g(x,y) = x^y is computable, prove that the
function h(x) = x^x^x is computable. (Note: a^b^c means a^(b^c), not
(a^b)^c. This is standard convention.)
- Assuming that the function g(x,y) = x^y is computable, prove that for
every natural number n, the function h(x_1, x_2, ..., x_n) =
x_1^x_2^...^x_n is computable. (Note: x_i means "x sub i".) Use
mathematical induction.