matemáticas

máquina de Turing

A Turing machine is an abstract computational model that manipulates symbols on a tape.
4 artículos relacionados · 1 quién trabajó aquí

Descripción

Formalmente, una máquina de Turing consta de una cinta infinita dividida en celdas, cada una de las cuales contiene un símbolo de un alfabeto finito; un dispositivo de control con una memoria finita de estados; y un cabezal capaz de leer, escribir y desplazarse una celda. La función de transición determina, a partir del estado actual y el símbolo leído, un nuevo símbolo, la dirección de desplazamiento (I/D) y un nuevo estado. La máquina comienza con la palabra de entrada en la cinta y puede detenerse en un estado de aceptación o de rechazo, o quedar atrapada en un bucle infinito. La máquina universal de Turing puede simular cualquier otra a partir de su descripción, lo que prefigura el concepto de computadora programable.

Historia

En 1936, Alan Turing, al abordar el Entscheidungsproblem (problema de decisión) de David Hilbert, introdujo el concepto de «a-machine» (máquina automática) en su artículo «On Computable Numbers». Su objetivo era formalizar la noción intuitiva de algoritmo. De forma independiente, Alonzo Church llegó al concepto equivalente del cálculo lambda. La tesis de Church-Turing afirma que cualquier proceso intuitivamente computable puede llevarse a cabo en una máquina de Turing. En 1945, John von Neumann utilizó este modelo en la arquitectura EDVAC, precursora de las computadoras modernas. En 1985, David Deutsch propuso la máquina cuántica de Turing, abriendo el camino a la computación cuántica.

Cómo funciona

La máquina de Turing computa manipulando cadenas de símbolos. Algorítmicamente, es equivalente a un lenguaje de programación con un único array de longitud infinita. Propiedades clave: existencia de una máquina universal (intérprete), indecidibilidad del problema de parada (no se puede determinar algorítmicamente si una máquina arbitraria se detendrá con una entrada dada), teorema de recursión (la máquina puede obtener su propia descripción). En teoría de la complejidad se consideran máquinas con oráculo (que reciben información adicional) y máquinas probabilísticas (con una fuente de bits aleatorios). Las máquinas cuánticas de Turing operan con estados en un espacio de Hilbert y usan transformaciones unitarias; no violan la tesis de Church-Turing, pero pueden ofrecer una aceleración exponencial para ciertos problemas.

En la práctica

Cualquier programa de computadora, desde una calculadora hasta un asistente con IA, se reduce a instrucciones que una máquina de Turing puede ejecutar. En ella se basa toda la teoría de la computación.

Dato curioso

La máquina universal de Turing más sencilla, ideada por Marvin Minsky, utiliza solamente 7 estados y 4 símbolos, y aun así es capaz de calcular todo lo que puede un potente superordenador, aunque a una velocidad terriblemente lenta.

Concept graph →

Artículos relacionados · 16

Cuatro directores de la orquesta celular: cómo el epitelio elige el camino hacia la fluidez
El epitelio recubre nuestros órganos como las baldosas recubren el suelo. En reposo, las células se aferran unas a otras y el tejido es elástico. Pero durante el desarrollo del embrión, la cicatrización de una herida o el crecimiento de un tumor, esta capa comienza a fluir como miel espesa. ¿Qué es lo que desencadena ese ablandamiento?
Restauración del Z3: los clics de los relés resucitan la computadora perdida
Berlín, diciembre de 1943. El destello de una bomba y la primera computadora completamente automática y programable de la historia, el Z3, desaparece entre las llamas. Su creador, Konrad Zuse, ni siquiera intenta restaurar el hardware: después de la guerra construye nuevas máquinas.
Orquesta sin director: un grupo elástico para la inferencia de LLM
Siete núcleos se detienen en una barrera invisible. El octavo se ha entretenido en un proceso ajeno... y toda la inferencia de LLM se congela. Así es el principal conflicto de convivencia entre las tareas de aprendizaje automático y los procesos comunes en un mismo procesador.
Umbral 2: cómo una regla de goma resiste el promedio infinito
2 es el umbral más allá del cual una secuencia dócil corre el riesgo de perder su estructura. En lugar de una escala uniforme habitual, una regla de goma con elasticidad no uniforme. Así son los espacios de Orlicz: espacios de Banach de sucesiones donde cada escala tiene su propia rigidez, descrita por una función convexa de Young (una especie de muelle).
Computadora química en un tubo de ensayo
En un tubo de ensayo flotan moléculas. Su cantidad —digamos, la concentración de alguna proteína— se convierte en la señal de entrada. Y a la salida no se necesita solo una solución turbia, sino una respuesta clara tipo 'sí' o 'no'. Los autores del trabajo construyen una cadena química que hace exactamente esto.
Caligrafía sin alfabeto: cómo el cerebro dibuja letras que nunca ha visto
La mano dibuja en el aire la palabra «mamá»: arcos y palos familiares. El cerebro, mientras tanto, no reproduce la fotografía de cada letra. Activa una cadena de movimientos simples. Los neuroingenieros pusieron a prueba esta idea: la escritura mental no es una galería de imágenes prefabricadas, sino un juego de construcción con los mismos «ladrillos» motores.
Cómo evitar que los motores moleculares patinen
Dentro de cada célula hierve la vida: diminutas máquinas proteicas transportan cargas sin descanso, leen genes y corrigen errores. Pero su trabajo dista de ser perfecto: a menudo patinan, dan pasos hacia atrás o se quedan atrapadas en ciclos inútiles. Es como un atasco urbano, donde los coches corretean sin rumbo quemando gasolina.
Cómo ajustar un motor molecular sin romperse la cabeza
Una fábrica donde cientos de diminutas líneas de montaje trabajan sin parar. Cada línea es un motor molecular que convierte combustible químico en movimiento. Para que el motor vaya más rápido o en la dirección deseada, el ingeniero cambia los ajustes: la forma de las piezas, la fuerza de las interacciones.
La inteligencia artificial abre camino a los chips ópticos
Un rayo láser se divide en decenas de finos hilos, atraviesa un vidrio esmerilado y vuelve a concentrarse en un solo punto. Así se ve la mesa de trabajo en la que se ha sentado el programa. No recibió instrucciones, solo un objetivo general: comprender cómo cambia la luz al atravesar un medio dispersivo y encontrar algo nuevo.
Física Atómica2026-04-241 minarXiv:2604.22406exprés
Trampas para átomos: cómo llenarlas hasta el borde
Una pinza óptica es un haz láser que mantiene un átomo en un punto, como los dedos sostienen un guisante. Con estas pinzas se construyen redes enteras de átomos, la base de las futuras computadoras cuánticas. Pero hay un problema: no en cada pinza cae un átomo.
La máquina que no se estorba a sí misma
Una orquesta donde cada músico toca su parte pero solo oye al vecino. En cuanto uno se equivoca, una ola de errores recorre toda la sala. Así funcionan las máquinas de Ising: dispositivos especiales para resolver problemas donde hay que elegir la mejor opción entre muchas.
Física Cuántica2026-04-151 minarXiv:2604.13872exprés
La danza de los iones: cómo nacen los vórtices cuánticos
En una trampa de campos, los científicos ensamblaron un cristal — 150 iones a temperatura ultrabaja. Cada ion se comporta como un diminuto imán, capaz de girar en cualquier dirección. Controlando fuerzas que dependen de este espín, los físicos hicieron que todos los pequeños imanes se arremolinaran en un remolino común, llamado skyrmion.
Ideas que nadie buscaba
La ciencia se parece a una ciudad donde las calles las trazan los propios habitantes. Donde ya hay senderos pisoteados se construyen casas nuevas, mientras que los solares vírgenes pasan desapercibidos, no porque no se pueda construir allí, sino porque nadie se acerca a mirarlos.
Metodología2026-02-191 minarXiv:2602.17772exprés
El cerebro se imprime solo: cómo los pares de electrodos aceleran la lectura de la mente
Una persona mira una pantalla donde parpadean letras. No mueve ni la mano ni el ojo: solo marca mentalmente el símbolo deseado. Unos sensores en la cabeza captan las débiles ondas eléctricas del cerebro, y la computadora entiende qué letra ha elegido la persona. Así funciona la interfaz cerebro-computadora: da voz a quienes no pueden hablar ni moverse.
Superconductividad2026-01-101 minarXiv:2601.06632exprés
Memoria superconductora: un interruptor que no olvida
La memoria de computadora común gasta energía constantemente para no olvidar lo que se ha guardado. Un superconductor podría almacenar datos sin pérdidas, pero es difícil hacer que conmute. En el nuevo trabajo, el superconductor está intercalado entre dos aislantes magnéticos.
Resonancia de túnel: cómo los diodos aprenden a ver
En 1974, los físicos describieron por primera vez un dispositivo en el que los electrones atraviesan una barrera de energía gracias al efecto túnel cuántico. Hoy, ese dispositivo, el diodo de túnel resonante, se convierte en el corazón de una arquitectura computacional inusual.