Re: Partial recursive functions and minimization

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)

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 -


.

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)