An uncomputability conjecture

From: Antti Ylikoski (ajy_at_cc.hut.fi)
Date: 12/22/03 

Date: Mon, 22 Dec 2003 18:56:36 +0200

Let P be a problem. P is an object in the real world,
ie. in the objective reality, I'm not giving any definition
for it, it is a fundamental concept.

Then, let R = R(P) be a formal symbolical representation
of the problem. R may be written as pseudocode;
it may exist as a formal definition using English,
formulas and figures;
it might be written down in a symbolic programming
language such as LISP or Prolog.

Then, M = NDTM(R) is a nondeterministic Turing machine
which solves the problem.

Let {w} = {w | w = w(R, i), i in N}
be the set of input words for M. Then,
L = M({w}) is the language that M accepts,
and it is the solution to the problem P.

Moreover, let M' = DTM(R) be a deterministic
Turing machine that corresponds to R.
Similarly, let {w'} be the set of input words to
M', corresponding to the representation R.
Then, L' = M'{w'} is the language accepted by M',
and it is the solution to P.
Here it may or may not be the case that L' = L,
they are equivalent in the sense that the both of them
solve the problem R = R(P).

An interesting question is:
Is it the case that the function

    f: f(M) = M'

is uncomputable?

In other words, we consider the possible uncomputability
of transforming a nondeterministic Turing machine into
a deterministic TM which is equivalent, ie. solves the
same problem.

It would seem to me that this is uncomputable, and
it should not be very difficult to discover the proof.

I'm wondering if it might be possible to infer this
result from Rice's theorem according to which all
nontrivial properties of programs are undecidable?

    Antti Ylikoski
    Helsinki Univ of Technology
    antti.ylikoski@hut.fi
    http://www.hut.fi/~ajy