6

Función Computacional

Embed Size (px)

Citation preview

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

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

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

http://slidepdf.com/reader/full/funcion-computacional 2/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

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

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

 

� 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.

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

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

 

� 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.

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

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

 

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

recursivo.

� f: N N

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

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}

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

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

 

� 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.