Función calculada

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 10 de abril de 2019; la verificación requiere 1 edición .

Las funciones computables son el conjunto de funciones de la forma que se pueden implementar en una máquina de Turing . La tarea de calcular una función se denomina algorítmicamente decidible o algorítmicamente indecidible , dependiendo de si el algoritmo que calcula esta función es posible. $f\dos puntos N\to N,$ $F$

Como un conjunto , generalmente se considera un conjunto: un conjunto de palabras en el alfabeto binario , con la condición de que el resultado del cálculo puede ser no solo una palabra, sino también un valor especial "incertidumbre", correspondiente al caso cuando el algoritmo "se cuelga". Así, se puede dar la siguiente definición : $norte$ $B^{*}$ $B=\{0,1\}$ $norte$

$N=B^{*}\cup \{\operatorname {undef} \},$

donde , a es un elemento especial que denota incertidumbre. $B=\{0,1\}$ ${\ estilo de visualización \ nombre del operador {undef}}$

El papel de un conjunto puede ser desempeñado por el conjunto de números naturales, al que se suma el elemento , y luego las funciones computables son algún subconjunto de funciones de valor natural del argumento natural. Es conveniente suponer que varios conjuntos contables pueden actuar como conjunto: el conjunto de números naturales, el conjunto de números racionales, el conjunto de palabras en algún alfabeto finito, etc. Es importante que haya algún lenguaje formal en el finito. alfabeto para describir los elementos del conjunto y que se calculó el problema de reconocimiento correcto. Por ejemplo, para describir los números naturales, es conveniente utilizar el sistema numérico binario, el lenguaje para describir los números naturales en el alfabeto . $norte$ ${\ estilo de visualización \ nombre del operador {undef}}$ $norte$ $norte$ $B$

En esta definición, en lugar de un ejecutor de máquina de Turing, se puede tomar uno de los ejecutores completos de Turing . En términos generales, el "ejecutor de referencia" puede ser una computadora abstracta, similar a las computadoras personales utilizadas, pero con una memoria potencialmente infinita y características arquitectónicas que permiten el uso de esta memoria infinita.

Es importante señalar que el conjunto de programas para este ejecutor (por ejemplo, el conjunto de máquinas de Turing con un alfabeto fijo de datos de entrada y salida) es contable . Por tanto, el conjunto de funciones computables es a lo sumo contable, mientras que el conjunto de funciones de la forma es incontable, si es contable. Esto significa que hay funciones no computables y la cardinalidad de su conjunto es mayor que la cardinalidad del conjunto de funciones computables. Un ejemplo de una función no computable (problema algorítmicamente irresoluble) puede ser una función de detección de parada , una función que recibe una descripción de alguna máquina de Turing y una entrada para ella como entrada, y devuelve 0 o 1 dependiendo de si esta máquina se detiene en una entrada determinada o no. Otro ejemplo de una función no computable es la complejidad de Kolmogorov . $f\dos puntos N\to N,$ $norte$

Historia

La comprensión de que algunas funciones de la forma son computables y otras no, apareció incluso antes de la llegada de las primeras computadoras. La teoría de la computabilidad tiene su origen en la disertación de Turing ( 1936 ), en la que introdujo el concepto de una computadora abstracta y las funciones que son computables en ella. A medida que se desarrolló la teoría de la computabilidad , se formularon varias definiciones que, como resultó más tarde, definen el mismo conjunto de funciones: el conjunto de funciones computables: $f\dos puntos B^{*}\a B^{*}$

funciones implementadas en máquinas de Turing ( Alan Turing );
funciones implementadas en algoritmos normales de Markov ( A. A. Markov );
funciones implementadas en la máquina de Post ;
funciones parcialmente recursivas ( Kurt Gödel , Stephen Kleene );
Funciones implementadas en una máquina registradora .

Véase también

Tesis de Church-Turing
Completitud de Turing
Funciones parcialmente recursivas
Funciones recursivas generales
Funciones recursivas primitivas
Conjuntos resolubles
Conjuntos enumerados
Funciones no computables ( problemas algorítmicamente irresolubles ):

detener el problema
Problema de equivalencia de algoritmos
El problema de probar la verdad o falsedad de un enunciado
Décimo Problema de Hilbert - Solvibilidad de una Ecuación Diofántica en Números Enteros
Autoaplicabilidad

Enlaces

Cursos de computabilidad