## [Máquina de Turing](/es/node/58265) Definición Modelo abstracto de computación que consta de una cinta infinita (o ilimitada) dividida en celdas, una cabeza de lectura/escritura que se mueve a la izquierda o derecha, un conjunto finito de estados y una función de transición que asigna (estado actual, símbolo actual) a (estado siguiente, símbolo a escribir, movimiento de la cabeza). ## Principio Principio La computación se modela como transiciones de estado discretas que operan sobre una cinta simbólica con espacio de trabajo ilimitado; la complejidad y la decidibilidad se estudian contando pasos y uso de cinta en relación con el tamaño de la entrada. ## Demostración Demostración Una máquina de Turing determinista sencilla que decide la paridad en entrada unaria: leer símbolos, alternar un estado interno de paridad en cada '1' y detenerse en estados de aceptación/rechazo según la paridad tras barrer la entrada y los blancos. ## Aplicación incorrecta Aplicación incorrecta Equiparar la detención abstracta de una máquina de Turing con el tiempo de ejecución práctico en hardware real, o tratar las computaciones no detenidas como resultados válidos en lugar de ejecuciones indefinidas. ## Consecuencia Consecuencia Forma la base de la teoría de la computabilidad: define problemas decidibles frente a indecidibles, y mediante refinamientos de complejidad proporciona clases (tiempo/espacio) que ordenan los requisitos de recursos algorítmicos. ## Inversión Inversión Un autómata finito solo dispone de memoria de trabajo finita y no puede simular una cinta ilimitada; reconoce una clase estrictamente menor de lenguajes (regulares) frente a los lenguajes computables por una máquina de Turing. ## Límite Límite Las máquinas de Turing deterministas de una sola cinta son un modelo fundamental; variantes incluyen nondeterministas, multi‑cinta o con oráculos que extienden capacidades o cambian la contabilidad de recursos. Modelos cuánticos o probabilísticos quedan fuera de la definición determinista clásica. ## Tensión semántica Tensión semántica Tensión con lenguajes de programación y arquitecturas de alto nivel: la máquina de Turing es un dispositivo teórico mínimo centrado en la computabilidad y los recursos, no en preocupaciones prácticas como factores constantes, paralelismo o conjuntos de instrucciones. ## Síntesis Síntesis Una máquina de Turing es un dispositivo abstracto mínimo que formaliza la computación como transiciones de estado etiquetadas sobre una cinta simbólica ilimitada, sirviendo como modelo estándar para definir computabilidad y cómputo con recursos limitados.