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 |