Re: Partial recursive functions and minimization

On Dec 23, 4:02 pm, glenn <glenn...@xxxxxxxxx> wrote:
O/H John Coleman ??????:





On Dec 23, 9:23 am, glenn <glenn...@xxxxxxxxx> wrote:
O/H John Coleman ??????:

On Dec 22, 5:29 am, Twoflower <standa.ku...@xxxxxxxxx> wrote:
Hi all,
let's have partial recursive function F, which is not recursive. I
don't understand, why
G(x) = Min(y) (F(x,y) = 0)
(where Min(y) is just minimization operator or unrestricted mu-
recursion)
is not partial recursive function.
Could someone please explain this to me?
Thank you very much.
Here is another approach:
Suppose that T is a Turing Machine. Define a function F via
F(x,0) = 0 if and only if T halts on input x. Otherwise, F(x,0) is
undefined
F(x,y) = 0 for all y > 0
F is clearly partial recursive. G as defined is a total function with
G(x) = 0 if T halts on x
G(x) = 1 if T does not halt on x
Then G is partial recursive if and only if the halting problem for T
is decidable. Since the halting problem is in general undecidable,
such G are in general nonrecursive. (Possible objection: the Halting
Problem is usually stated to the effect that there is no single
algorithm which can tell for all possible Turing machine/input pairs
(T,x) whether or not T halts on x. Stated this way, it seems possible
that nevertheless for an specific Turing machine T there exists an
algorithm specific to T which can decide if T halts on x - but the
existence of univeral Turing machines rules this out.)
Your function G is clearly parametrized over the Turing Machines. What
you have proved is that the set of T.M.'s is not recursive. You can see
this by repeating your argument putting an index T, thus indicating the
explicit dependence from the particular T.M., e.g.:
Suppose that T is a Turing Machine. Define a function F_T via
F_T(x,0) = 0 if and only if T halts on input x. Otherwise, F_T(x,0) is
undefined.
F_T(x,y) = 0 for all y > 0 etc. The OP's original G, has only one
variable. Yours has two:

Mine has one - I *started* with a Turing machine T ("suppose that T is
a Turing machine") and defined a partial recusive 2-variable F based
on that, which leads to a 1-variable G via the OP's construction.
Different T lead to different G (in general).

Exactly. This is a schema. Your G has two variables: G_T(x) = Min(y)
(F_T(x,y) = 0)

You might as well say that the OP's G has 2 variables since it depends
on F. You might as well say that p(x) = ax^2 + bx + c is not a
quadratic because a,b,c are parameters. For any fixed T, G is a
function of one variable, which fails to be partial recursive for
appropriate choice of T - thus answering the OP's original question.
Why do you think that a 1-parameter family of counterexamples is
inferior to a single counterexample? Pick your favorite universal
Turing machine (suitably encoded) if you have don't like parameters.
You seem to think that F partial recursive implies that G(x) = min{y|
F(x,y)=0} is partial recursive. That implication is in fact false
since it contradicts the undecidability of the Halting Problem. Do you
disagree? If so, I would love to see a proof. Exactly how do you
propose to compute G (given an algorithm for computing F)?




For some T (namely ones
for which the halting problem is decidable) G is recursive. For some T
(namely ones for which the halting problem for T is undecidable - and
for a universal Turing machine, it *is* undecidable) G fails to be
recursive. Thus - not all such G are recursive, which is what I set
out to show. Do you think that the OP is wrong and that it is a
theorem of recursion theory that F partial recusive implies G (*as
defined*) is partial recursive? If so, why not supply a proof? It is
not true by definition since min is not mu (maybe the OP *meant* mu -
but I have been taking "min" at face value with his "unrestricted"
qualifier to mean not restricted by the requirement that F(x,0), ...,
F(x,y) all exist. Perhaps the OP could clarify. What do they mean by
"min" and "mu" ?)

one for x and one for the T.M. So it is of the
form G(x,<T>), where <T> belongs to a fixed recursive enumeration of all
T.M.'s. If you try a diagonalization, i.e. put x=<T>, in order to get a
G with only one variable, you end up to the previous mentioned
conclusion that the set of T.M.'s is not recursive.- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -- Hide quoted text -

- Show quoted text -

.

Relevant Pages

  • Re: Peter Olcotts Source of Confusion
    ... >> see if a Turing machine M halts on input x. ... >would solve the Halting Problem sure seems like pure malarkey. ... Processing speed is irrelevant as long as there is some lower bound ...
    (sci.logic)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (comp.theory)
  • Re: [PO] Re: Refutation of the Halting Problems Proof (Clarifications Wanted)
    ... > every existing proof of the Undecidability of the Halting Problem. ... "halt analyzer" is a term you need to define, ... TMs don't return results to other TMs. ... "Since returning the result back to the Turing Machine being analyzed is ...
    (sci.logic)
  • Re: Exploiting limitations of Turing machines in Turing tests?
    ... correctly answer _any_ halting problem question. ... You were proposing that there exists some finite set of special Turing ... able to successfully answer _all_ halting problem questions. ... It's a description of some Turing Machine, and some input, with the simple ...
    (comp.ai.philosophy)
  • Re: Gödel, Turing, and Cantor
    ... >1) Gödel's incompleteness theorem ... >machine for which the halting problem is undecidable. ... Turing machine #n [in an appropriate ... finitely many steps that the Turing machine performs until it halts]. ...
    (sci.math)