Re: Partial recursive functions and minimization
- From: John Coleman <jcoleman@xxxxxxxxxxxxxx>
- Date: Sun, 23 Dec 2007 04:55:12 -0800 (PST)
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.)
HTH
.
- Follow-Ups:
- Re: Partial recursive functions and minimization
- From: glenn
- Re: Partial recursive functions and minimization
- References:
- Partial recursive functions and minimization
- From: Twoflower
- Partial recursive functions and minimization
- Prev by Date: Re: real analysis - it is neither continuum nor discrete
- Next by Date: Re: Simple questions about Convergent Sequence
- Previous by thread: Re: Partial recursive functions and minimization
- Next by thread: Re: Partial recursive functions and minimization
- Index(es):
Relevant Pages
|
