Probar que una función es recursiva primitiva

Question

Hey,

Me estoy tomando un curso en la teoría de la computabilidad, pero estoy luchando con recursión primitiva. Más específicamente, a menudo nos preguntan para demostrar que algunas de función arbitraria es primitiva recursiva, pero yo realmente no sé cómo hacerlo.

Por ejemplo:

Deje $\pi (x)$ el número de números primos que se $\le x$. Mostrar que $\pi (x)$ es primitiva recursiva.

¿Cómo usted va sobre lo que demuestra esta formalmente? Y, en general, ¿cuáles son las condiciones necesarias para probar si algo es o no es primitiva recursiva.

Nota: esta no es la tarea, he tirado la pregunta de una lista de ejemplos que nos han dado :)

Answer 1

Esto no es una respuesta exacta, pero ayuda a determinar rápidamente en muchos de los casos que una función dada es primitiva recursiva. La idea es usar un razonable lenguaje de programación en el que su función puede ser expresada más fácilmente que con la "cruda" de la aritmética y primitivo de la recursividad. Por supuesto, el lenguaje de programación debe ser limitado suficiente para evitar ilimitado de búsquedas y otras construcciones que llevan a general de la recursividad. Voy a mencionar sólo un fácil posibilidad.

Supongamos que una función de $f : \mathbb{N} \to \mathbb{N}$ es calculada por un simple imperativo programa en el polinomio tiempo de ejecución (en realidad, como Grigory señala en su respuesta, cualquier primitiva recursiva enlazado va a hacer). Más precisamente, el programa está permitido el uso de operaciones básicas de la aritmética, valores booleanos, variables, matrices, bucles y sentencias condicionales. A continuación, la función de $f$ es primitiva recursiva.

La razón por la que un programa de este tipo sólo se puede definir una función recursiva primitiva es que la totalidad de la ejecución del programa puede ser codificada por un número $N$ cuyo tamaño de bits es acotado por un polinomio $p(n)$ donde $n$ es la entrada. Debido a que la verificación de que un número codifica la ejecución de un simple imperativo programa es primitiva recursiva, se puede realizar una búsqueda delimitada a a $2^{p(n)}$ encontrar el número de $N$ (un almacén de búsqueda es primitiva recursiva) y extracto de la respuesta de ella.

Apliquemos esto a su pregunta. El siguiente programa en Python se calcula la función de $\pi(n)$ y utiliza sólo un par de bucles y aritmética básica (podríamos sustituir la función del resto % con otro bucle). Su tiempo de funcionamiento es de segundo grado en $n$, suponiendo que todas las operaciones básicas que son constantes en el tiempo:

def pi(n):
   '''Computes the number of primes which are less than or equal n.'''
   p = 0 # the number of primes found
   k = 2 # for each k we test whether it is prime
   while k <= n:
       j = 1 # possible divisors of k
       d = 0 # number of divisors of k found
       while j <= n:
           if k % j == 0: d = d + 1
           j = j + 1
       if d == 2: p = p + 1
       k = k + 1
   return p

Por lo tanto, su función es primitiva recursiva.

Answer 2

Una prueba simple expresiones para si una función es primitiva recursiva es o no se puede escribir en Bloop.

El punto crucial es que la estructura de flujo de control de lazo te obliga a decir de antemano cuántas veces se lazo.

Aquíde algún código de ejemplo para trabajar con números primos en Bloop.

Answer 3

Hay un teorema que dice que cualquier función computable por una máquina de Turing en el tiempo que es una primitiva de la función recursiva de la longitud de la entrada es primitivo recursivo.

Este teorema se puede encontrar aquí: http://en.wikipedia.org/wiki/Primitive_recursive_function

Su función es primitivo recursivo porque puede ser calculado en $O(n^2)$ tiempo (aquí $n$ es la longitud de la entrada) en un equipo utilizando algún lenguaje de programación como C++. La diferencia entre el tiempo necesario para implementar este algoritmo en C++ y en una máquina de Turing es el polinomio en la longitud de la entrada de modo que la resultante tiempo necesario para la implementación de una máquina de Turing es el polinomio en $n$.

[editar] Demostrando que la función no es primitiva recursiva es más difícil. Hay una prueba con el método de diagonalización que muestra que existe en algunos no primitivamente función recursiva. Construir una función explícita se puede observar que, si la función crece demasiado rápido que no es primitivo recursivo. Ackerman función tiene el derecho de la tasa de crecimiento para este.

Answer 4

Demostrar que la función de $$f(x)=\begin{cases}1,&\text{if $x$ is prime;}\\\0,&\text{otherwise}\end{cases}$$ es primitiva recursiva.

A continuación, mostrar que dado cualquier primitiva de la función recursiva $f:\mathbb N\to\mathbb N$, la función de $g:\mathbb N\to\mathbb N$ tal que $g(x)=\sum_{y=1}^xf(y)$ también es primitiva recursiva. Luego adaptar esto para probar lo que usted desea.

En general, lo que se hace para demostrar que una función específica es primitiva recursiva depende de la función---como era de esperar. Me encantaría oír acerca de la no-trivial condiciones suficientes de carácter general, aunque...

Hay, por otro lado, varias de las condiciones necesarias para que una función primitiva recursiva, que puede ser utilizado para mostrar que las funciones específicas no es primitiva recursiva. Esto es como una muestra, por ejemplo, que la función de Ackermann no es primitiva recursiva: una muestra de que crezca demasiado rápido.

Answer 5

Hay un teorema que dice que cualquier función computable por una máquina de Turing en el tiempo que es una primitiva de la función recursiva de la longitud de la entrada es primitivo recursivo.

Esto que acabo de mencionar resultado es un poderoso teorema con numerosas aplicaciones.

Es fácilmente los rendimientos de los resultados como este.

Suponga que g,h,p, son prim rec. Entonces f es prim rec donde

f(x,y)=g(x,y) si x veces y es 0 y f(x+1,y+1)=h(x,y,f(x,f(x,p(x,y))),f(x+1,y)).

Tratando de averiguar "soluciones directas" es más o menos imposible.

Así que mi recomendación: Si el curso de los valores de la recursividad y simultánea la recursividad no funciona, pruebe el teorema anterior.