===========================================================================
CSC 363H                        Exercise 3                        Fall 2007
===========================================================================

A.  A partial function is a function that can be undefined for some inputs
    (e.g., 1/x is a partial function over the rational numbers because it
    is undefined at x = 0).
    We say that a partial function f : S* -> S* is "computable" if there
    exists a TM M_f such that for all strings w in S*, M accepts w with
    final configuration  q_accept f(w)  when f(w) is defined, and M_f
    either rejects or loops on w when f(w) is undefined.  In other words,
    when M_f is started with w on its tape, if f(w) is defined, then M_f
    eventually enters its accepting state with only f(w) on the tape and
    its head on the leftmost symbol of f(w); and if f(w) is undefined, M_f
    either loops or eventually enters its rejecting state (in which case
    the final tape content and head position are unimportant).

    Show that a partial function f is computable (as defined above) iff the
    language L_f = { w#f(w) : w in S* and f(w) is defined } is recognizable
    (where # is a symbol that does not belong to S).

    (You will have noticed that this is very similar to Question B in
    Exercise 2, so you should answer it in a similar manner.  However,
    there are some important, but subtle, differences in the kinds of
    functions we are considering, which will affect the solution.)

B.  Show that decidable languages are closed under the concatenation and
    intersection operations, i.e., if L_1 and L_2 are any two decidable
    languages, then L_1 . L_2 is decidable and L_1 intersect L_2 is
    decidable.  (Recall that L_1 . L_2 = { xy : x in L_1, y in L_2 }.)

C.  Show that regognizable languages are closed under the contatenation and
    union operations.