Re: Partial recursive functions and minimization

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

Relevant Pages

  • Re: Halting Problem
    ... If halts() returns true on line 7, then might_haltwould jump into the infinite loop on line 9. ... It appears to me that the reason that "might_halt" causes this approach to fail is, simply, that the generated tree would be infinitely large due to recursion. ... would it be fair to say that the halting problem is only undecidable when recursion is allowed? ... Could we then further conclude that the halting problem is only undecidable for SOME recursive programs, and even for these programs, the condition of undecidability can at least be detected? ...
    (comp.programming)
  • Halting Problem
    ... Suppose I write a function that solves the halting problem for all ... If halts() returns true on line 7, ... large due to recursion. ... the condition of undecidability can at least be detected? ...
    (comp.programming)
  • Re: Halting Problem
    ... If halts() returns true on line 7, ... large due to recursion. ... would it be fair to say that the halting problem is only undecidable ... the condition of undecidability can at least be detected? ...
    (comp.programming)
  • Re: Disproof of the Halting Problems Conclusion
    ... is enough to show that Halt is not recursive). ... >> and the Halting Problem asks in terms of all possible programs. ... >> I've presented the standard recursion theoretic proof of the halting ... >> Turing Machine. ...
    (comp.theory)
  • Re: Disproof of the Halting Problems Conclusion
    ... is enough to show that Halt is not recursive). ... >> and the Halting Problem asks in terms of all possible programs. ... >> I've presented the standard recursion theoretic proof of the halting ... >> Turing Machine. ...
    (sci.logic)