Teoría de autómatas y modelos computacionales alternativos
Citation preview
Teora de Autmatas II
3 curso
Ingeniera Tcnica en Informtica de Sistemas
UNED
Sesin 2
Funciones recursivas parciales
Funciones recursivas parciales
Proceso de minimalizacin de funciones:
Produce una funcin
a partir de otra
De manera que
Que se lee f(x) es igual a la menor y, tal que g(x,y) es cero, y
g(x,z) est definida para todos los enteros no negativos z menores
que y
Ejemplo de minimalizacin: Figura 4.8
Ejercicio: para que valores est definida f(x)
si f(x) = y[ms(x,y)=0]?
Funciones recursivas parciales
El proceso de minimalizacin aplicado a una funcin parcial
computable produce una funcin parcial computable.Nueva familia de
funciones: funciones recursivas parciales:
Aquellas que se construyen a partir de funciones iniciales
aplicando un nmero finito de combinaciones, composiciones,
recursividades primitivas y minimalizaciones.
Funciones recursivas parciales
Las funciones recursivas parciales son un sper conjunto de las
recursivas primitivas (Vase grfico 4.9).Tesis de Church: La clase
de las funciones recursivas parciales contiene todas las funciones
parciales computables.
Nadie ha podido demostrar que esta afirmacin es falsa.
La tesis de Church es equivalente a la tesis de Turing.
