Post propuso un camino para obtener un conjunto no completo para la reductibidad de Turing, definiendo y estudiando reducibilidades intermedias. Así, las diferencias importantes entre la reducción M y la de Turing son
obviamente el poder efectuar mas de una pregunta, y en segundo lugar el poder “hacer lo contrario” de lo que indica la respuesta; pero la propiedad realmente relevante resulta ser un poder que cada pregunta dependa
esencialmete de las respuestas obtenidas a preguntas anteriores
(“adaptabilidad” de la reducción). Es posible definir reducibilidades intermedias, entre ellas las reducciones por la tabla de variedad, que no son adaptativas.
Y, en efecto, una versión reforzada de los conjuntos simples, los hipersimples, proporciona conjuntos que no son completos respecto de la reductibilidad por tablas de verdad. Post demostró este hecho, y construyo un conjunto hipersimple; nosotros lo tenemos facil por que, de hecho, ya lño tenemos: el propio conjunto SK no solo es simple si no hipersimple.
Asimismo, propuso un concepto de hiper-hipersimple, y demostró que existen, en la esperanza de que no fueran completos respecto reducciones de Turing. La idea era procurar que los complementarios fueran “lo mas delgados
posible” en cierto sentido intuitivo: en un inmune “no cabe” un recursivamente enumerable y en un hiperinmune (complementario de un hipersimple) “el siguiente elemento esta siempre demasiado lejos” para lo que puede
lograr enumerar una función recursiva. Sin embargo mas adelante se estableció que existen hiper-hipersimples que son T-completos e incluso que existen recursivamente numerables maximales respecto a la inclusión, y por
tanto con complementario “lo mas delgado posible” en este sentido intuitivo, y que son T-completos.
La solucion finalmente requirió un concepto tecnico nuevo, las construcciones por metodos de prioridad, que extendieron otra de las varias contribuciones de Post. Merece la pena comentar que actualmente existen varioas
demostraciones diferentes, algunas de las cuales pueden considerarse la culminación del programa estructural de Post; pese a lo cual, los metodos de prioridad han de verse como el camino apropiado de solución.
6.3 Funciones Computables
Las funciones computables son usadas para discutir computabilidad sin referirse a ningún modelo de computación concreto, como máquina de Turing o máquina de registros. Los axiomas de Blum pueden ser usados para definir una teoría de complejidad computacional abstracta sobre el conjunto de funciones computables.
Según la tesis Church-Turing, la clase de funciones computables es equivalente a la clase de funciones definidas por funciones recursivas, cálculo lambda, o algoritmos de Markov.
Alternativamente se pueden definir como los algoritmos que pueden ser calculados por una máquina de Turing, un sistema de Post, o una máquina de registros.
En teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable esta conocido como un problema de funciones.
Una función parcial
se llama computable si el gráfico de f es un conjunto recursivamente enumerable. El conjunto de funciones parcialmente computables con un parámetro es normalmente escrito o si el número de parámetros es claro del contexto.
Una función total
se llama computable si el gráfico de f es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro normalmente se escribe o .
Una función computable f se llama predicado computable si es una función con valor booleano, o sea
Definición
La recursión primitiva se define sobre los números naturales o sobre tuplas de números naturales. La aridad de una función es el número de sus argumentos. El conjunto de las funciones primitivas recursivas se define en base a las siguientes reglas:
1. La constante 0 es primitiva recursiva.
2. La función sucesor S, de aridad 1, que produce el siguiente entero según los axiomas de Peano, es primitiva recursiva.
3. Las funciones de proyección Pin, de aridad n que producen como resultado su argumento de la posición i son primitivas recursivas.
4. Composición: Dado f, una función primitiva recursiva de aridad k y k funciones primitivas recursivas de aridad l g0,...,gk-1, la composición de f con g0,...,gk-1, es decir, la función h(x0,...,xl-1) = f(g0(x0,...,xl-1),...,gk-1(x0,...,xl-1)), es primitiva recursiva.
5. Recursión primitiva: Dado f una función primitiva recursiva de aridad k y g una función primitiva recursiva de aridad k+2, la función de aridad k+1 definida como la función h donde h(0,x0,...,xk-1) = f(x0,...,xk-1) y h(S(n),x0,...,xk-1) = g(h(n,x0,...,xk-1),n,x0,...,xk-1), es primitiva recursiva.
Se puede notar que las funciones de proyección permiten contrarrestar la rigidez impuesta por la paridad de las funciones en la definición anterior, dado que en la composición se puede pasar cualquier subconjunto de los argumentos.
Una función es primitiva recursiva si es la función constante cero, la función sucesor, una proyección o si se define a partir de funciones primitivas recursivas utilizando únicamente composición y recursión primitiva.
Según la tesis Church-Turing, la clase de funciones computables es equivalente a la clase de funciones definidas por funciones recursivas, cálculo lambda, o algoritmos de Markov.
Alternativamente se pueden definir como los algoritmos que pueden ser calculados por una máquina de Turing, un sistema de Post, o una máquina de registros.
En teoría de la complejidad computacional, el problema de determinar la complejidad de una función computable esta conocido como un problema de funciones.
Una función parcial
se llama computable si el gráfico de f es un conjunto recursivamente enumerable. El conjunto de funciones parcialmente computables con un parámetro es normalmente escrito o si el número de parámetros es claro del contexto.
Una función total
se llama computable si el gráfico de f es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro normalmente se escribe o .
Una función computable f se llama predicado computable si es una función con valor booleano, o sea
Definición
La recursión primitiva se define sobre los números naturales o sobre tuplas de números naturales. La aridad de una función es el número de sus argumentos. El conjunto de las funciones primitivas recursivas se define en base a las siguientes reglas:
1. La constante 0 es primitiva recursiva.
2. La función sucesor S, de aridad 1, que produce el siguiente entero según los axiomas de Peano, es primitiva recursiva.
3. Las funciones de proyección Pin, de aridad n que producen como resultado su argumento de la posición i son primitivas recursivas.
4. Composición: Dado f, una función primitiva recursiva de aridad k y k funciones primitivas recursivas de aridad l g0,...,gk-1, la composición de f con g0,...,gk-1, es decir, la función h(x0,...,xl-1) = f(g0(x0,...,xl-1),...,gk-1(x0,...,xl-1)), es primitiva recursiva.
5. Recursión primitiva: Dado f una función primitiva recursiva de aridad k y g una función primitiva recursiva de aridad k+2, la función de aridad k+1 definida como la función h donde h(0,x0,...,xk-1) = f(x0,...,xk-1) y h(S(n),x0,...,xk-1) = g(h(n,x0,...,xk-1),n,x0,...,xk-1), es primitiva recursiva.
Se puede notar que las funciones de proyección permiten contrarrestar la rigidez impuesta por la paridad de las funciones en la definición anterior, dado que en la composición se puede pasar cualquier subconjunto de los argumentos.
Una función es primitiva recursiva si es la función constante cero, la función sucesor, una proyección o si se define a partir de funciones primitivas recursivas utilizando únicamente composición y recursión primitiva.
6.2 Un problema simple insoluble
El demostrador (del Arggone Natinla Laboratory) demostró, en esencia, que de las ecuaciones de algebra de Robbins:
x _ y = y _ x
(x _ y) _ z = x _ (y_ z)
: ( : (x_y) _ : (x_:y)) = x
Implican las ecuaciones de algebre de Boole:
x _ y = y _ x
(x _ y) _ z = x _ (y_ z)
: ( : (x_y) _ : (x_:y)) = x
Es decir el demostrador demostró ser capaz de razonar con ecuaciones matemáticas, de hacer demostraciones dentro de una teoría matemática.
x _ y = y _ x
(x _ y) _ z = x _ (y_ z)
: ( : (x_y) _ : (x_:y)) = x
Implican las ecuaciones de algebre de Boole:
x _ y = y _ x
(x _ y) _ z = x _ (y_ z)
: ( : (x_y) _ : (x_:y)) = x
Es decir el demostrador demostró ser capaz de razonar con ecuaciones matemáticas, de hacer demostraciones dentro de una teoría matemática.
.6.1 Problemas insolubles para la teoría de lenguajes
Problemas de decisión.
Un problema de decisión (PD) es aquel formulado por una pregunta (referida a alguna propiedad) que requiere una respuesta de tipo “si/no”.
Problemas de decisión.
Un problema de decisión es
Soluble si existe un algoritmo total para determinar si la propiedad es verdadera (Existe una MT que siempre para al resolver el problema).
Parcialmente soluble si existe un algoritmo parcial para determinar si la propiedad es verdadera (existe una MT que resuelve el problema, pero puede no parar).
Insoluble si no existe un procedimiento efectivo para determinar si la propiedad es verdadera (no existe una MT),
Ejemplos de problemas de decisión:
¿Existe un algoritmo para decidir si un número natural cualquiera es par?
Si es soluble.
¿Existe un algoritmo para decidir si dos autómatas finitos cualesquiera son equivalentes?
Si es un problema soluble.
¿Existe un algoritmo para determinar si una gramática es ambigua o no?
No es insoluble.
Muchos problemas insolubles son paradójicos en su naturaleza. Ej: la paradoja de Russell.
Un peluquero afecta a todas las personas que no se afectan a si mismas. El peluquero: ¿se afeita así mismo? (insoluble).