¿La equivalencia es computable sobre el conjunto de funciones recursivas primitivas?

La equivalencia de las funciones recursivas primitivas es indecidible. Esto se desprende del teorema de que es indecidible si una función mu-recursiva es total.

El teorema de la forma normal de Kleene nos dice que cada función mu-recursiva [matemática] f [/ matemática] puede expresarse como

[matemáticas] f (x_1, \ ldots, x_n) = U (\ mu z. p (e, x_1, \ ldots, x_n, z)) [/ math]

para algunos dados [math] e \ in \ mathbb {N} [/ math]. Aquí [math] U [/ math] es una función recursiva primitiva y [math] p [/ math] es un predicado recursivo primitivo, es decir, una función recursiva primitiva cuyo rango es [math] \ {0,1 \} [ /mates]. Esta forma normal se puede determinar de manera efectiva. Esto se deduce del resultado de que las máquinas Turing y las funciones recursivas mu tienen el mismo poder expresivo; la prueba construye una función mu-recursiva en forma normal.

Una función recursiva mu [matemática] f [/ matemática] de la forma anterior de es total si es el caso de que para cada [matemática] (x_1, \ ldots, x_n) [/ matemática] tenemos que [matemática] p (e, x_1, \ ldots, x_n, z) = 1 [/ math] para algunos [math] z \ in \ mathbb {N}. [/ math] Si [math] f [/ math] no es total, entonces [matemática] p (e, x_1, \ ldots, x_n, z) = 0 [/ matemática] por cada [matemática] z \ in \ mathbb {N} [/ matemática].

Si la equivalencia fuera decidible para las funciones recursivas de los primates, también podríamos determinar si un recursivo mu [matemático] f [/ matemático] es total al verificar si [matemático] p [/ matemático] y la función constante [matemática ] g (e, x_1, \ ldots, x_n, z) = 0 [/ math] fueron equivalentes.