La completitud de Turing es cuando un lenguaje de programación es capaz de realizar las funciones de una máquina de Turing. Este es un concepto para una computadora mecánica muy básica, a veces descrita como la máquina más simple que puede considerarse una computadora. Prácticamente todos los lenguajes de programación que se utilizan hoy en día y, en teoría, las computadoras que los ejecutan tienen la integridad de Turing.
El concepto de integridad de Turing proviene de Alan Turing, un informático británico cuyo trabajo incluía descifrar mensajes codificados durante la Segunda Guerra Mundial. Entre sus trabajos sobre informática se encontraba el desarrollo de una filosofía de lo que realmente podía hacer una computadora. Esto incluyó el concepto de que las computadoras funcionan simplemente ejecutando algoritmos. Es decir, siguen un conjunto fijo de reglas para procesar datos y, a su vez, resolver problemas. Esto significa que una computadora no «piensa» ni toma decisiones como lo hace una persona.
Para ilustrar el concepto, Turing describió una máquina hipotética a la que llamó una «máquina a», con la «a» que significa automático; otros más tarde la llamaron la máquina de Turing. La máquina procesaría un carrete de cinta que podría retroceder o avanzar y que contuviera una línea de símbolos. En cualquier momento, la máquina puede procesar un símbolo y, si es necesario, modificarlo. Para los propósitos del concepto, el carrete de cinta podría ser infinitamente largo, lo que significa que la memoria de la computadora no estaba intrínsecamente limitada. Esta es una analogía de la idea de que una vez que una computadora tiene un conjunto de instrucciones a seguir, la cantidad de datos a la que puede aplicar esas instrucciones está sujeta solo a límites físicos.
Irónicamente, la mayoría de las computadoras de hoy en día no tienen la integridad de Turing. Esto se debe a que tienen limitaciones en el espacio de almacenamiento disponible y, por lo tanto, en los datos que pueden procesar. También tienen limitaciones físicas, sobre todo que eventualmente se desgastarán. En realidad, es el lenguaje de programación el que tiene la integridad de Turing. Debido a esto, una computadora que ejecuta un programa de este tipo no es una computadora de Turing, pero puede usarse para simular una.
La completitud de Turing no debe confundirse con la prueba de Turing. Este fue un experimento diseñado por Turing para ver si las computadoras pueden conversar en lenguaje natural. El principio de la prueba es que si un humano no puede diferenciar entre una conversación de solo texto con la computadora y otra persona, la computadora pasa la prueba. Si bien algunas computadoras han pasado la prueba cuando el rango de temas de conversación está restringido, ninguna lo ha hecho en una conversación sin restricciones.