matemáticas - funciones

Las funciones computables son el objeto básico de estudio de la teoría de la computabilidad y son, específicamente, las funciones que pueden ser calculadas por unamáquina de Turing.Las funciones computables 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. La noción de la computabilidad de una función puede ser relativizada 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 con un oráculo por A o f. Tales funciones pueden ser llamadas A-computable o f-computable respectivamente. Antes de la definición precisa de una función computable los matemáticos usaban el término informal efectivamente computable.

Las funciones computables son usadas para discutir sobre 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. 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 de 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 [1].

Alternativamente se pueden definir como los algoritmos que pueden ser calculados por una máquina de Turing, una máquina 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 es conocido como un problema de funciones.Una función parcial

se llama parcialmente computable si el gráfico de  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 puede deducirse del contexto.

Una función total

se llama computable si el gráfico de  es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro normalmente se escribe  o .

Una función computable  se llama predicado computable si es una función con valor booleano, es decir:

Problemas computables y no computables

El identificar los problemas que son computables y los que no lo son tiene un considerable interés, pues indica el alcance y los límites de la computabilidad, y así demuestra los límites teóricos de los ordenadores. Además de las cuestiones sobre algoritmos, se han encontrado numerosos problemas menos "generales" que han resultado ser no computables. La mayoría de las demostraciones de no computabilidad se basan en el método de la diagonal. Como ejemplos de estos problemas podemos citar:

1.- El problema de la palabra para Grupos.- Dado un subconjunto S de elementos de un grupo G, se trata de decidir si una expresión compuesta por elementos de S y con las operaciones del grupo es igual al elemento neutro del grupo. Durante muchos años se buscaron ejemplos de grupos finitamente presentados para los que este problema fuese indecidible. La existencia de uno de estos grupos fué encontrada por Novikov en 1955 y por Boone en 1957. En el algebra moderna hay abundantes ejemplos de interesantes problemas no computables; una gran cantidad de ellos sobre propiedades de palabras o generadores semejantes al problema de la palabra para grupos.

2.- Décimo problema de Hilbert. Una ecuación diofántica es la ecuación de los ceros enteros de un polinomio con coeficientes enteros. El décimo problema de Hilbert, propuesto en 1900, pregunta si hay un procedimiento efectivo que determine si una ecuación diofántica tiene o no solución. Y. Matiyasevich demostró en 1970 que este problema no tiene solución.

3.- Decibilidad de las teorías lógicas. El desarrollo de la teoría de la computabilidad ha ido íntimamente ligado al desarrollo de la lógica matemática. Esto ha sido así porque la decibilidad de los distintos sistemas lógicos es una cuestión fundamental. Es bastante fácil ver que el cálculo proposicional es decidible. Church y Turing demostraron en 1936 que el cálculo de predicados no era decidible. Por otro lado, para cada una de las distintas teorías se ha ido estudiando su posible decibilidad. Como ejemplo más ilustrativo, Tarski demostró que la teoría de los números reales era decidible.

Por otro lado, son muchos los problemas interesantes que se han demostrado computables. Todas las funciones construidas por recursividad primitiva o minimalización a partir de funciones calculables resultan ser calculables como consecuencia de los trabajos de Church y Turing. Pero además, otras funciones más complejamente definidas también son computables, siendo el resultado más significativo en relación con esta cuestión el dado por el siguiente teorema:

Primer teorema de Recursión. Todo operador entre funciones calculables que sea recursivo (esto es que se defina la imagen de f mediante una función calculable en términos de una parte finita de f), tiene una función parcial computable que es el menor punto fijo, es decir, esta función es un punto fijo y cualquier otro punto fijo del operador es una extension de esa función.

Este teorema recibe su nombre porque podemos definir una función mediante una ecuación recursiva más general que la permitida por la recursividad primitiva, a saber

donde  es un operador recursivo. El primer teorema de recursión nos dice que esta definición es posible; hay una función recursiva que satisface esta ecuación. Como en matemáticas se requiere que la definición sea unívoca, se dice que dicha ecuación define el menor punto fijo del operador . Así, y de acuerdo al primer teorema de recursión, la clase de las funciones calculables es cerrada bajo una muy general forma de definición por recursión.

Como ejemplo más interesante de aplicación de este tipo de recursión tenemos la función de Ackermann :

A menudo se utiliza la técnica de reducir un problema a otro para comprobar si tiene o no solución efectiva. La estratégia en el caso de la respuesta negativa es la siguiente, si se reduce de forma efectiva un problema sin solución efectiva a otro problema (mediante una función calculable), entonces este nuevo problema tampoco tendrá solución efectiva. La razón es muy simple, si tuviese solución efectiva, componiendo el algoritmo solución con el algoritmo de transformación obtendríamos una solución para el problema efectivamente irresoluble. En sentido inverso, si se reduce un problema a otro para el que se conoce una solución efectiva, entonces componiendo se obtiene una solución para el primer problema. Esta técnica es muy útil y se utiliza a menudo. Por otro lado, esta mísma técnica es muy empleada en el campo de la complejidad algorítmica. Para asegurarse de que un problema está en una clase de complejidad, basta reducir el problema a otro de dicha clase sin más que asegurarse que la reducción se realiza en la correspondiente clase de complejidad.

Funciones computables son los objetos básicos de estudio en la teoría de la computabilidad. Funciones computables son el análogo formal de la noción intuitiva de algoritmo. Se utilizan para discutir computabilidad sin referirse a ningún modelo concreto de cálculo, tales como máquinas de Turing o máquinas de registro. Cualquier definición, sin embargo, debe hacer referencia a un modelo específico de la computación, pero todas las definiciones válidas producir la misma clase de funciones. Modelos particulares de computabilidad que dan lugar a un conjunto de funciones computables son las funciones Turing computables y funciones recursivas.

Antes de la definición precisa de la función computable, los matemáticos utilizan a menudo el término informal efectivamente calculable. Este término ha llegado ya a identificarse con las funciones computables. Tenga en cuenta que la computabilidad efectiva de estas funciones no implica que se pueden calcular de manera eficiente. De hecho, para algunas funciones efectivamente calculables se puede demostrar que cualquier algoritmo que calcula ellos será muy ineficiente en el sentido de que el tiempo de ejecución del algoritmo aumenta exponencialmente con la longitud de la entrada. Los campos de la computabilidad factible y funciones de estudio de la complejidad computacional que se pueden calcular de manera eficiente.La clase de funciones computables se puede definir en muchos modelos equivalentes de computación, incluyendo

• Máquinas de Turing
• Funciones recursivas
• El cálculo lambda
• Publique máquinas.
• Registrarse máquinas

Aunque los modelos de uso de las diferentes representaciones de las funciones, sus entradas y sus salidas, existen traducciones entre dos modelos. En el resto de este artículo, se utilizan las funciones de los números naturales a los números naturales.

Cada función f computable tiene un número fijo y finito de números naturales como argumentos. Tenga en cuenta que las funciones son parciales, en general, es decir, no se pueden definir para cada posible elección de entrada. Si una función computable se define por un cierto de entrada, entonces se devuelve un solo número natural como salida. Estas funciones se denominan funciones recursivas parciales. En teoría de la computabilidad, se toma el dominio de una función a ser el conjunto de todas las entradas para los que se define la función.

Una función que se define para todos los argumentos posibles se denomina total. Si una función computable es total, se denomina función computable, total o función recursiva total.

La notación f? indica que la función f parcial se define en argumentos x1, ..., xk, y la notación f = f y indica que se define en el argumentos x1, ..., xk y el valor devuelto es y. El caso de que una función f no está definida para argumentos x1, ..., xk se denota por f? .

Características de las funciones computables

La característica básica de una función computable es que debe haber un procedimiento finito dice cómo calcular la función. Los modelos de computación antes mencionados dan diferentes interpretaciones de lo que es un procedimiento y la forma en que se utiliza, pero estas interpretaciones comparten muchas propiedades. El hecho de que estos modelos dan clases de equivalentes de funciones computables se deriva del hecho de que cada modelo es capaz de leer y imitando un procedimiento para cualquiera de los otros modelos, tanto como un compilador es capaz de leer las instrucciones en un lenguaje informático y emitir instrucciones otro idioma.

Enderton da las siguientes características de un procedimiento para el cálculo de una función computable; caracterizaciones similares se les ha dado por Turing, Rogers, y otros.

• "Debe haber instrucciones exactas, finitas de longitud, para el procedimiento."

Así, cada función computable debe tener un programa finita que describe detalladamente el modo de la función se va a calcular. Es posible calcular la función con sólo seguir las instrucciones, no se requiere adivinar o conocimiento especial.

• "Si el procedimiento se le da un x k-tupla en el dominio de f, a continuación, después de un número finito de pasos discretos el procedimiento debe terminar y producir f."

Intuitivamente, el procedimiento avanza paso a paso, con una norma específica para cubrir lo que debe hacer en cada paso del cálculo. Sólo un número finito de pasos se pueden llevar a cabo antes de que el valor de la función se devuelve.

• "Si el procedimiento se da a x k-tupla que no está en el dominio de f, entonces el procedimiento podría durar para siempre, nunca detener. O podría atascarse en algún momento, pero no debe pretender producir un valor para f en x ".

Por lo tanto si se encuentra alguna vez un valor para f, que debe ser el valor correcto. No es necesario que el agente de computación para distinguir los resultados correctos de los incorrectos debido a que el procedimiento es siempre correcta cuando se produce un resultado.

Enderton pasa a enumerar varias aclaraciones de estos 3 requisitos del procedimiento para una función computable:

El procedimiento debe teóricamente trabajar arbitrariamente grandes argumentos. No se supone que los argumentos son más pequeños que el número de átomos en la Tierra, por ejemplo.

Se requiere que el procedimiento para detener después de un número finito de pasos con el fin de producir una salida, pero puede tomar arbitrariamente muchos pasos antes de parar. No se asume ninguna limitación de tiempo.

Aunque el procedimiento se puede utilizar solamente una cantidad limitada de espacio de almacenamiento durante un cálculo con éxito, no hay obligado de la cantidad de espacio que se utiliza. Se supone que el espacio de almacenamiento adicional se puede administrar al procedimiento cada vez que el procedimiento lo pide.

El campo de la complejidad computacional funciones estudios con límites prescritos en el tiempo y/o espacio permitido en un cálculo éxito.