Models of Computation - Mathematics 352 -
Fall 2009
For HW #11
In the following, N denotes the set of all natural numbers.
- Refer to Definitions 1.1(abc) on page 72 for these problems. In part
(c) of the definition, X is not necessarily a finite set.
- Is the set of natural numbers between 0 and 100 countable?
- Is the set of all natural numbers countable?
- What is the difference between "countable" and
"denumerable"?
- What is the difference between "denumerable" and
"effectively denumerable"?
- Let's say a set is enumerable if there exists an enumeration of
it. Then, is each of the following true or false? Explain your reasoning.
(1) Every enumerable
set is denumerable.
(2) Every enumerable set is effectively denumerable.
(3) Every denumerable set is enumerable.
- Explain in your own words the Note on top of page 73 and the footnote at
the bottom of the same page. In your explanation include answers to the
following questions: Why does the book use "the informal
notion of effectively computable" ? Why shouldn't we instead require
that f and f^(-1) be URM-computable?
- (Optional) Can you guess why in Theorem 1.4 the book uses the letter gamma for the bijection from
the set of all programs to N? Hint: Read the paragraph after the
proof of Theorem 1.4. If that hint didn't help, here's another one:
read footnote 2 at the bottom of the same page.
Okay, I guess the above were kind of unusual questions, at least for a math
course! Nevertheless, I and II are important (and III is amusing, I hope). Now here are some "real" math problems:
-
- (a) Give a "formula" for the bijection f: N x N -> N
given by the following "pattern":
f(0,0)=0, f(1,0)=1, f(0,1)=2, f(2,0)=3, f(1,1)=4, f(0,2)=5, f(3,0)=6,
f(2,1)=7, f(1,2)=8, f(0,3)=9, ...
Hint: If you group together the ordered pairs (a,b) that have the same
sum a+b, you'll notice that each group has one more ordered pair than the
previous group. For example, the first group contains only one ordered
pair: (0,0); the second group contains two ordered pairs (0,1) & (1,0),
the third group three, and so on. Conclude from this that f(a,0) =
a(a+1)/2. Then use this to figure out a formula for f(a,b).
- Prove, without using Church's Thesis, that f is computable. You may
use the "standard" computable functions of Chapter 2 (such as basic
functions, x+y, xy, |x-y|, sg(x), etc.) as well as substitution,
recursion, and minimalization.
(Hopefully, this will further convince you of Church's Thesis -- more
specifically, that when humans do something
algorithmically, a URM can do it too, even when the human algorithm involves
following a (pictorial) pattern!)
- Prove, using Church's Thesis, that f^(-1) is computable.
- Challenge problem (optional): Can you show, without using Church's
Thesis, that f^(-1) is computable?
-
- Give a bijection phi: N x N x N --> N such
that phi and phi^(-1) are both computable. Explain why your phi and
phi^(-1) are computable. Prove that your phi is a bijection. (Hint: use
the bijection f from the previous problem to construct phi.)
- Suppose g : N x N x N --> N is a total
computable function (not necessarily 1-1 or onto). Use Church's Thesis to
prove the predicate M(x) = "x is in the range of g " is decidable.
(Hint: use part a.)
- State whether or not (you think) each of the following functions is
computable. We have not yet proved any functions to be non-computable. We
will do so in the next chapter. For this problem, if you believe a function
is not computable, explain why you believe so; but no proof is necessary. If
you think a function is computable, give a proof by Church's Thesis.
- f(x) = 1 if x is in Dom(g), 0 otherwise, where g(x) is a computable
function.
- f(x) = 1 if px (the xth prime) is in Dom(g), undefined
otherwise, where g(x) is a computable function.
- f(x) = 1 if px (the xth prime) is not in Dom(g), undefined
otherwise, where g(x) is a computable function.
- f(x) = 1 if Dom(g) is nonempty, undefined otherwise, where g(x) is a
computable function.