Una máquina de Turing es una construcción filosófica de cómo podría funcionar una computadora, inventada en 1936 por Alan Turing, un famoso matemático y lógico inglés del siglo XX. Las ideas detrás de la máquina de Turing son la base de todos los sistemas de hardware y software informáticos modernos que existen a partir de 20, aunque los conceptos reales que Turing creó nunca se utilizaron para construir un dispositivo real en ese momento, y se inventaron antes de que existieran las computadoras digitales en cualquier forma real. Los principios sobre los que funciona una máquina de Turing incluyen un conjunto de controles para los datos de entrada y salida, la máquina para procesar los datos de alguna forma y un conjunto de reglas establecidas sobre cómo la máquina procesa estos datos.
La genialidad detrás del descubrimiento de Alan Turing fue que cualquier grupo consistente de símbolos que representen información significativa, como los símbolos matemáticos o las letras que componen un lenguaje, podría ser procesado mecánicamente por una máquina si se le diera un conjunto adecuado de reglas para su procesamiento. Esto daría lugar a la creación de dispositivos mecánicos a los que se les podrían hacer preguntas lógicas para problemas complejos y dar rápidamente respuestas imparciales. La máquina de Turing fue un precursor a este respecto de un algoritmo informático, que es una lista compilada de instrucciones informáticas en las que se basan las unidades centrales de procesamiento (CPU) en las computadoras para funcionar a partir de 2011.
El diseño de la máquina de Turing era simplista según los estándares informáticos modernos del siglo XXI, y su función física no tenía aspectos prácticos en cuanto a su implementación, pero las ideas sobre las que se construyó tenían una base sólida. La máquina consistía en una cinta o cinta con símbolos impresos en ella, que podían leerse con un cabezal mientras pasaban la cinta por encima. A medida que se leían los símbolos, estos invocarían ciertos estados en la máquina, que dirigirían el movimiento de la cinta y afectarían los valores de salida producidos por la máquina. Lo análogo a los sistemas informáticos modernos de 21 sería que la cinta representa el código o algoritmos de software, el lector es la CPU y la salida serían los sistemas de visualización y transmisión como monitores, altavoces e impresoras, tráfico de red y más.
Las ideas detrás de la máquina de Turing se vieron como una función fundamental para realizar cualquier serie de cálculos y también podrían compararse con el funcionamiento del cerebro humano. El propio Turing y otros de su época creían que la máquina de Turing podía adaptarse para realizar prácticamente cualquier tipo de cálculo imaginable y actuar como una máquina universal para resolver todos los problemas humanos. Sin embargo, el problema que surgió pronto con el concepto se conoce como tarpit de Turing y se refiere al hecho de que, aunque cualquier conjunto de símbolos autoconsistentes puede ser procesado por una máquina de Turing, conseguir que dicha máquina produzca respuestas significativas a preguntas se basa completamente en conjuntos de reglas de procesamiento cada vez más complejos y de múltiples capas.
La informática pronto encontró problemas con la forma en que los sistemas de software y hardware basados en los principios de la máquina de Turing podían atascarse en cálculos sin sentido conocidos como ciclos de programa. Las limitaciones lógicas llevaron a adaptaciones en los principios de la máquina de Turing, como la de las máquinas de Turing cuántica y probabilística. Una máquina de Turing probabilística utiliza la idea de que se ejecuten varias cintas en la máquina simultáneamente para producir diferentes resultados en paralelo, que luego se comparan entre sí en función de la probabilidad de que el resultado sea más exacto. Tales máquinas llegarían a conclusiones de una manera similar a cómo funciona el software de lógica difusa en los sistemas de control avanzados a partir de 2011.
Una computadora cuántica basada en el principio de la máquina de Turing tendría una cinta de longitud infinita con celdas de símbolos en un estado indeterminado perpetuo hasta que se lea. Esto proporcionaría una forma de procesamiento paralelo que sería muy superior a los procedimientos de procesamiento de datos utilizados en computadoras a partir de 2011. Las máquinas de Quantum Turing ofrecen la opción de almacenar múltiples valores en celdas individuales de memoria hasta que se acceda, lo que las computadoras estándar basadas en lógica no pueden hacer.