Función Computacional

5/8/2018 Función Computacional - slidepdf.com

http://slidepdf.com/reader/full/funcion-computacional 1/6



� Son el objeto básico de estudio de la teoría de la

computabilidad y consisten en las funciones que pueden

ser calculadas por una máquina de Turing

� Son una formalización de la noción intuitiva de algoritmo y

según la Tesis de Church-Turing son exactamente las

funciones que pueden ser calculadas con una máquina de

cálculo



� Las funciones computables son usadas para discutir

computabilidad sin referirse a ningún modelo de

computación concreto, como el de la máquina de Turing o

el de la 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.



� Se llama computable si el gráfico de f es un conjunto

recursivamente enumerable.

f: N N

� El conjunto de funciones parcialmente computables con unparámetro normalmente se escribe P¹ o P.




recursivo.

� f: N N


recursivo. El conjunto de funciones totalmente computables

con un parámetro se escribe normalmente R¹ o R .

� Una función computable f se llama predicado computable si

los valores de la función son booleanos, o sea

� f: N {0,1}



� El objetivo era concretar la noción de función calculable,

esto quiere decir, una función/expresión cuyos valores se

pueden calcular de forma automática a partir de un

algoritmo.

Documents

Función Computacional