Re: An uncomputability conjecture

From: Rick Decker (rdecker_at_hamilton.edu)
Date: 12/22/03 

Date: Mon, 22 Dec 2003 13:10:31 -0500

Antti Ylikoski wrote:

> 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.
>

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

Relevant Pages

  • An uncomputability conjecture
    ... ie. in the objective reality, ... Turing machine that corresponds to R. ... let be the set of input words to ... we consider the possible uncomputability ...
    (comp.theory)
  • OT: Church-Turing thesis (was Re: TCL cant do as much as Perl)
    ... Well, there's always the technical, trivial proof from Computer Science: either language can be used to simulate a Turing Machine, thus they are equally powerful, and no language can exist that is more powerful. ... the thesis states that a universal Turing machine (UTM) is able to compute any function which can be computed by an "effective method". ... An effective method is defined as being those tasks which an unaided human could in principle achieve, using just pencil and paper, following a finite number of instructions, in a finite number of steps, without using intuition etc. ...
    (comp.lang.tcl)
  • Re: Recursive language which is not context-sensitive
    ... language which is not context-sensitive: ... sensitive Grammar G and build up a turing machine T which accepts the ... down the 37th context sensitive grammar. ... is just a garbage string? ...
    (sci.math)
  • Re: Raatikainens Paper on Chaitin
    ... >> just be equal to e, with a corresponding Turing machine M_e. ... it established, instead, that the powers of human reason could not be ... I repeat Penrose and compate it to * immediately above: ... Leibniz dream of universal language formally mathematically expressed. ...
    (sci.logic)
  • Re: Arthur ODwyer on the feasibility of simulating a Turing Machine
    ... > equivalent to Church's thesis re the Turing machine. ... that Marxists would attempt to get involved in mathematical philosophy. ... Initially writing represents speech, and it is very unusual to know how to ... However written language has its own ...
    (comp.programming)