Prove that function is not primitive recursive.
- From: "Atreides" <gpekhimenko@xxxxxxxxx>
- Date: 9 Nov 2006 10:14:55 -0800
Hi.
I have a function
UP(z,x) = U ( min y < (A( (z)_0, x ) + z ) T( (z)_1, x, y))
z is a program ( we use RM programs)
(z)_x means in prime decomposition of z = p0^l0 * p1^l1 .. *px^lx ..
get x' power
so (z)_x = lx.
T - is a Kleene T predicate.
U - is just an output function. U(y) = ( ( (y)_(length(y)-1) )_1. Get
final state and get first register with the result.
I need to prove that this function is not primitive recursive.
The idea is usually to define diagonal function D(x) = UP( ...) + 1 ,
and then show contradiction using argument that for some e : D(e) = UP
(...).
I don't know how to define D(x) in this case :(.
I try to define D(x) = UP(e,x) + 1 for some fixed e.
I prove that UP(e,x) is a primitive recursive => D(x) is pr.rec.
And I prove that for every unary pr. res. f(x) exists n such that f(x)
= UP(n,x).
The problem is that n and e can be different so I do not have
contradiction :(.
Any ideas?
.
- Follow-Ups:
- Re: Prove that function is not primitive recursive.
- From: Atreides
- Re: Prove that function is not primitive recursive.
- Prev by Date: Prove that function is not primitive recursive.
- Next by Date: Request for Reference/Link to example of defining a theory/logic.
- Previous by thread: Prove that function is not primitive recursive.
- Next by thread: Re: Prove that function is not primitive recursive.
- Index(es):
Relevant Pages
|
