6/3     Ok, who wants to share my recursion theory pain?  I just spent a really
        long time on a problem, and I want to make some volunteer suffer like
        I did.  If there's any interest, I ll post the problem. -- ilyas
        \_ Hah!  You want us to do your homework, huh?  The problem is
           trivial.  Check the man pages or look it up on Sun's website.
           \_ It's true that this is my homework, but I did make sure to do
              it first, before posting. -- ilyas
              \_ The answer must be in the man pages somewhere.
        \_ go ahead, i'm game
           \_ seconded
              \_ Ok.  For the purposes of this problem, we are dealing with
                 functions which accept a set of bitstrings as input, and
                 output bitstrings.  The problem is to construct two
                 (computable) functions f and g with the following properties:
                 (a) f and g take two arguments each
                 (b) for any two inputs, f returns a turing machine (TM)
                     where the language it accepts is decidable and disjoint
                     from the language accepted by a TM returned by g.
                     (g must also return a decidable TM).
                 (c) if f is given as input any two TMs (in your favorite
                     bitstring encoding) that accept complementary languages,
                     f returns an encoding for a TM which accepts the same
                     language as argument 1, and if g is given same, it
                     returns an encoding for a TM which accepts the same
                     language as argument 2.
                 Note: if f or g return a 'malformed' bitstring, which does
                 not code a TM, the accepted language is considered to be
                 empty (hence decidable).  Note 2: all finite sets are
                 decidable.  This problem is very hard.  I posted it
                 because I am a sadist. -- ilyas
                 \_ My guess is that you first make f do something
                    reasonable.  Then you make g have a copy of f inside
                    it so that g can do the opposite.  You said that the
                    problem was very hard, though, so perhaps this
                    strategy runs into decidability problems.
                    \_ Sure, this works fine.  You do have to figure out how
                       to make f do something reasonable, though.  --mconst