Funciones

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 unarespuesta 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 alresolver 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).

6.3.- Funciones Computables.
Las funciones computables son una formalización de la nociónintuitiva de algoritmo y según la tesis Church-Turing son exactamente las funciones que pueden ser calculadas con una máquina de cálculo.
La noción de la computabilidad de una función puede serrelativizada a un conjunto arbitrario de números naturales A, o equivalentemente a una función arbitraria f de los naturales a los naturales, por medio de máquinas de Turing extendidas por un oracle por Ao f. Tales funciones puede ser llamados A-computable o f-computable respectivamente. Antes la definición preciso de una función computable los matemáticos usaban el término informal efectivamentecomputable.
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 Blumpueden 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 esequivalente 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...