robot de la enciclopedia para niños

Función computable para niños

Enciclopedia para niños

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 una máquina de Turing.

Introducción

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.

Definición

Una función parcial

f:\subseteq \mathbb{N} \to \mathbb{N}

se llama parcialmente computable si el gráfico f es un conjumerable. El conjunto de funciones parcialmente computables con un parámetro es normalmente escrito \mathbf{P}^{(1)} o ath> si el número de parámetros puede deducirse del contexto.

Una función total

f:\mathbb{N} \to \mathbb{N}

se llama computable si el gráfico de f es un conjunto recursivo. El conjunto de funciones totalmente computables con un parámetro normalmente se escribe \mathbf{R}^{(1)} o \mathbf{R}.

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

f:\subseteq \mathbb{N} \to \{0,1\}

Comentarios

A veces, por razones de claridad, se escribe una función computable como

g:\subseteq \mathbb{N}^k \to \mathbb{N}

Se puede fácilmente codificar g en una nueva función

f:\subseteq \mathbb{N} \to \mathbb{N}

usando una función de pares.

Ejemplos

  • Adición f : N2→ N, f(n1,n2) := n1 + n2

Propiedades

  • Si f y g son funciones computables entonces f + g, f.g y fog son funciones computables.
  • Las funciones computables son definibles aritméticamente.
  • Una función con valor booleano f es un predicado computable si y sólo si el lenguaje \{x \in \Sigma^{*} : f(x)=1\} es recursivo.

Véase también

Kids robot.svg En inglés: Computable function Facts for Kids

Obtenido de «https://ninos.kiddle.co/index.php?title=Función_computable&oldid=3850572»
kids search engine
Todo el contenido de los artículos de la Enciclopedia Kiddle (incluidas las imágenes) se puede utilizar libremente para fines personales y educativos bajo la licencia Atribución-CompartirIgual a menos que se indique lo contrario. Citar este artículo:
Función computable para Niños. Enciclopedia Kiddle.