Re: Partial recursive functions and minimization

On Dec 22, 9:35 pm, Twoflower <standa.ku...@xxxxxxxxx> wrote:
On 22 Pro, 21:21, Twoflower <standa.ku...@xxxxxxxxx> wrote:





On 22 Pro, 15:44, stevendaryl3...@xxxxxxxxx (Daryl McCullough) wrote:

Twoflower says...

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?

Well, you need to think about how one would go
about computing G(x). You could start with
y=0, and check to see if F(x,0) = 0. But that
computation might run forever. If it never halts,
then you will never be able to move onto checking
whether F(x,1) = 0.

Alternatively, if you try running F(x,0) and
F(x,1) in parallel, what do you do if F(x,1) = 0?
That might mean that 1 is the minimum y such
that F(x,y) = 0. Or it might mean that 0 is the
minimum y, if you only waited long enough.

There is never a point where you know for sure that
G(x) = 0, unless F(x,0) halts.

What is partially recursive is the following function
related to G(x):

   G'(x) = Min(y) (F(x,y) = 0 and forall z < y, F(x,z) halts)

--
Daryl McCullough
Ithaca, NY

Thank you Daryl, that's exactly the argument I've encoutered so far.
But I don't understand, what's exactly the problem. We know that
partial recursive functions are not expected to be defined for each
input so what's the problem if G(x) will diverge?- Skrýt citovaný text -

- Zobrazit citovaný text -

Well, maybe...I get it. The problem is that writing

G(x) = Min(y) (F(x,y) = 0)

we mean: "Let G(x) be function such that G(x) yields value 'y' if and
only if there exists value 'y' such that F(x,y) = 0 and then G(x)
equals to least of these values. G(x) diverges if and only if there is
no such 'y' that F(x,y) = 0."

Now even I finally see that G(x) doesn't do what we proposed it should
do. So that's the problem. So far I only saw the converges/diverges
sides and thought to myself that it's no problem for partial recursive
function to diverge.

Am I right now with the explanation? :-)- Hide quoted text -

- Show quoted text -

The terms 'diverge/converge' are unknown to me in this context but I
take them to mean 'the computation doesn't halt/the computation does
halt'.

A second previous question: if F is a partial recursive function, then
it is recursive, since recursive functions encompass both total and
partial functions.

Now let me try to put it my way, though I will not be saying anything
Daryl McCullough has not already said.

Assuming Church thesis, a partial recursive function is a function
that can be algorithmically computed whenever it is defined.

I assume G and F are functions over the naturals. Take some n and
suppose F(n,y) is not defined for y=0. Assume also that F(n,y) is
defined for y=1 and that F(n,1) = 0.

Then G(n) = 1 but G(n) may be algorithmically incomputable because
there might be no algorithm able to tell us that F(n,0) is not
defined, so we may have no effective way to know that G(n) =/= 0.

This can happen because the halting problem is not algorithmically
solvable, as Turing showed (again under Church thesis): there might be
no algorithm to show us that the algorithm computing F(n,0) will never
halt.

In conclusion, even though F is algorithmically computable whenever it
is defined, G need not be so.

Regards
.

Relevant Pages

  • Re: coerce for arbitrary types
    ... the algorithm itself is essentially last-in first-out, ... via some sort of recursion? ... WaitStack <= new stack containing topnode ... As nested lists, there's only one number in a proper position. ...
    (comp.lang.lisp)
  • Re: coerce for arbitrary types
    ... algorithm that Cormen, Leiserson, and Rivest use in their DFS. ... inherently first-in first-out, like a queue, not at all stack-like ... experience, once you get over the hurdle of recursion, ... *intention* is nested lists, *not* arbitrary CONS trees. ...
    (comp.lang.lisp)
  • 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)
  • Meaning of in-place; was fast stable sort
    ... view is that the "in-place" should refer only to the data element ... Recursion should be an additional qualifier, ... Thus your sorting algorithm that uses indices would be in-place ... The distinction is significant because ...
    (comp.programming)
  • Re: Software bugs arent inevitable
    ... I suggested that for a given algorithm implemented ... iteration should always be faster by a small factor. ... > recursive function can run out of stack space while the heap still has ... Which is why, in the part you snipped, I said that recursion (unlike ...
    (comp.lang.python)