Re: Partial recursive functions and minimization

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). 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: 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: Partial recursive functions and minimization
    ... Suppose that T is a Turing Machine. ... Then G is partial recursive if and only if the halting problem for T ... whether or not T halts on x. Stated this way, ... since it contradicts the undecidability of the Halting Problem. ...
    (sci.math)
  • 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)