Equivalentemente, esta tesis afirma que una función es computable si y sólo si tiene un algoritmo.
Nótese que un algoritmo en este sentido se entiende como una secuencia de pasos que una persona con tiempo ilimitado y un suministro ilimitado de lápiz y papel podría seguir.
Una forma de describirla es decir que una función es computable si su valor puede obtenerse mediante un procedimiento efectivo.
es computable si y sólo si existe un procedimiento efectivo que, dada cualquier k-tupla
[1] De acuerdo con esta definición, el resto de este artículo supone que las funciones computables toman finitamente muchos números naturales como argumentos y producen un valor que es un único número natural.
Como contrapartida a esta descripción informal, existen múltiples definiciones formales y matemáticas.
La clase de funciones computables se puede definir en muchos modelos de computación equivalentes, incluyendo Aunque estos modelos utilizan diferentes representaciones para las funciones, sus entradas y sus salidas, existen traducciones entre dos modelos cualesquiera, por lo que cada modelo describe esencialmente la misma clase de funciones, dando lugar a la opinión de que la computabilidad formal es a la vez natural y no demasiado estrecha.
Son la clase más pequeña de funciones parciales que incluye las funciones constante, sucesora y de proyección, y es cerrada bajo composición, recurrencia primitiva y el operador μ. Equivalentemente, las funciones computables pueden formalizarse como funciones que pueden ser calculadas por un agente computacional idealizado como una máquina de Turing o una máquina de registro.
El conjunto de funciones parcialmente computables con un parámetro es normalmente escrito
o ath> si el número de parámetros puede deducirse del contexto.
El conjunto de funciones totalmente computables con un parámetro normalmente se escribe
Los modelos de computación enumerados anteriormente dan diferentes interpretaciones de lo que es un procedimiento y cómo se utiliza, pero estas interpretaciones comparten muchas propiedades.
Enderton pasa a enumerar varias aclaraciones de estos 3 requisitos del procedimiento para una función computable: En resumen, desde este punto de vista, una función es computable si:
El campo de la complejidad computacional estudia funciones con límites prescritos en el tiempo y/o espacio permitidos en una computación exitosa.
Un conjunto de números naturales se llama computablemente enumerable (sinónimos: recursivamente enumerable', semidecidible) si existe una función computable f} tal que para cada número n, f(n) está definida si y sólo si.
En Teoría de la computabilidad en informática, es común considerar lenguajes formales.
Por ejemplo, las cadenas binarias son exactamente las palabras del alfabeto 0, 1. .
Debe desarrollarse algún sistema de codificación que permita a una función computable tomar como entrada una palabra arbitraria del lenguaje; esto suele considerarse rutina.
Un lenguaje se llama computable (sinónimos: recursivo, decidible) si existe una función computable f tal que para cada palabra w sobre el alfabeto, f(w) = 1 si la palabra está en la lengua y f(w) = 0 si la palabra no está en el lenguaje.
Un lenguaje es computablemente enumerable (sinónimos: recursivamente enumerable, semidecidible) si existe una función computable f tal que f(w) está definida si y sólo si la palabra w está en el lenguaje.