function: set of ordered pairs, no two of which have the same first member
and different second members
a function relates two sets: it is from a set A to a set B. (So each of
the ordered pairs "in" the function has a first member from A and
a second member from B.) We say f: A -> B to indicate that the function f
is from A to B.
domain, range
one-to-one/not one-to-one, onto/not onto, total/partial (given two sets,
should be able to construct functions that have any combination of one
property from each pair)
inverse function
composite function (given functions f, g you should be able to say what
the composite function fg is)
know what the characteristic function of a set is
Enumerability
a set A is enumerable iff there is a total or partial function from the
positive integers to a that is one-to-one and onto.
two sets A and B are equinumerous iff there is a function from A to B that
is total, one-to-one, and onto. (We can also express this by saying there is
a correspondence between A and B.) (You should be able to explain why it's
OK to say "from A to B" without specifying that there is also a
one-to-one, total, onto function from B to A.)
you should be able to give intuitive proofs that the following sets are
enumerable: the positive integers; all the integers; the positive rational
numbers; the set of all the ordered pairs of positive integers
Suppose A and B are enumerable sets. Show that their union is enumerable.
(An informal argument in terms of constructing lists is OK.)
Diagonalization (Nonenumerability)
be able to show that the real numbers between 0 and 1 are not enumerable
(by means of a diagonalization argument)
be able to show that the set of all sets of positive integers is not
enumerable (again, by using a diagonalization argument; the easiest way is
to make use of the idea of the characteristic function of a set)
Computability
be able to give a precise definition of a Turing machine
be able to explain the relation between TMs and the functions they compute
(for example, if I describe what a particular TM does, you should be able to
say what function from positive integers to positive integers it computes)
be able to write Turing machines to perform simple tasks (e.g. start on
the leftmost of a block of n strokes; end on the leftmost of a string of n +
2 strokes)
be able to write Turing machines to compute simple functions (e.g. f(n) =
n + 2)
be able to write a Turing machine that computes the function f(x,y) = x *
y. (NO, JUST KIDDING!)
Turing's Thesis
Uncomputability
what is the halting problem?
be able to give an informal proof that the halting problem is unsolvable
by a Turing machine (and hence, if Turing's Thesis is true, unsolvable
period). (suppose it were solvable by a TM. Then there is a TM H that
computes, given two arguments: the positive integer that maps to any given
TM in some enumeration of all the TMs, and another positive integer n,
whether the TM will halt when started on input n. --for instance, by halting
on a single stroke if the TM would halt, and halting on the leftmost of two
strokes if it would not halt. But then we could sandwich H in between the
copying machine C and the dithering machine D, which we know we can
construct. This leads to a contradiction. Why?)
Recursive Functions
know the basic functions: the zero function z, the successor function s,
and the identity (projection) functions id.
how many projection functions are there for an n-place function?
know the basic techniques for building other primitive recursive functions
out of the basic functions: composition and primitive recursion (If I give
you two functions, you should be able to say what the result of composing
them in a given order is. If I give you a primitive recursive definition of
a function, you should be able to say what the function does. for example,
consider this definition of a function h: h(x,0) = id(x) and h(x, y') =
s(h(x,y)). What function is h?)
know the difference between recursive and primitive recursive functions.
are there any primitive recursive functions that aren't total? why?
understand the function-building technique that allows us to get recursive
functions that aren't primitive recursive, namely minimization.
are all recursive functions total? if so, why? if not, give an example of
one that isn't.
if I give you a function, you should be able to tell me what the
minimization of that function is for a given set of arguments. (Example: let
f(x,y) be the addition function, i.e. f(x,y) = x + y. What is the value of
Mn[f](0)? What about Mn[f](5)?)
Church's Thesis: all computable functions are recursive.
Recursive Sets and Relations
a set is recursive iff its characteristic function is recursive.
a set is effectively decidable iff its characteristic function is
effectively computable.
if Church's Thesis is true, then a set is effectively decidable iff it is
recursive.
if Turing's Thesis is true, a set is effectively decidable iff its
characteristic function is computable by a TM.
relations also have characteristic functions. (The characteristic function
of a k-place relation is a function of k arguments.)
a relation is recursive iff its characteristic function is recursive.
a relation is effectively decidable iff its characteristic function is
effectively computable.