Re: An uncomputability conjecture, corrected version
From: Antti Ylikoski (ajy_at_cc.hut.fi)
Date: 12/23/03
- Next message: Aatu Koskensilta: "Re: Help with undecidable problem"
- Previous message: Antti Ylikoski: "Re: An uncomputability conjecture"
- In reply to: Antti Ylikoski: "Re: An uncomputability conjecture"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Date: Tue, 23 Dec 2003 14:26:11 +0200
"Antti Ylikoski" <ajy@cc.hut.fi> kirjoitti
viestissä:bs8nor$ekm$1@phys-news1.kolumbus.fi...
>
> "Rick Decker" <rdecker@hamilton.edu> kirjoitti
> viestissä:3FE73397.8020201@hamilton.edu...
>
[snips]
> >
> > On the contrary, as I read you, it should indeed be
> > very difficult to discover a proof, since the result
> > is false. You surely must be aware of the proof that
> > every NTM has an equivalent DTM. The proof as usually
> > presented gives an explicit and computable construction
> > so your f above is indeed computable.
> >
> >
> > <snip>
> >
> >
> >
> >
> > Regards,
> >
> > Rick
>
>
> Oh, I was being silly!!!
>
> Thank you very much anyway!!
>
> Antti Ylikoski
>
I was a bit confused when I wrote the beforementioned "uncomputability
conjceture" which was trivially wrong. I checked my files, and the
corrected version of the conjecture is as follows.
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.
Let the problem P be in the problem class NP.
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 = NP-NDTM(R) is a nondeterministic Turing machine
which solves the problem and runs in a polynomial time.
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
in a polynomial time,
and it is the solution to the problem P.
Moreover, let M' = P-DTM(R) be a deterministic
Turing machine that corresponds to R and solves the
problem in a polynomial time.
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'
in a polynomial time,
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) in a polynomial time.
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 NP-Turing machine into
a deterministic P-TM which is equivalent, ie. solves the
same problem.
Antti Ylikoski
Helsinki Univ of Technology
antti.ylikoski@hut.fi
http://www.hut.fi/~ajy
- Next message: Aatu Koskensilta: "Re: Help with undecidable problem"
- Previous message: Antti Ylikoski: "Re: An uncomputability conjecture"
- In reply to: Antti Ylikoski: "Re: An uncomputability conjecture"
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
Relevant Pages
|
