12.8: Variantes de Máquinas Turing

Última actualización
Guardar como PDF

Page ID: 103667

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Template:MathJaxZach

De hecho, hay muchas formas posibles de definir las máquinas Turing, de las cuales la nuestra es solo una. De alguna manera, nuestra definición es más liberal que otras. Permitimos alfabetos finitos arbitrarios, una definición más restringida podría permitir solo dos símbolos de cinta,\(\TMstroke\) y\(\TMblank\). Permitimos que la máquina escriba un símbolo a la cinta y se mueva al mismo tiempo, otras definiciones permiten ya sea escribir o mover. Permitimos la posibilidad de escribir sin mover el cabezal de la cinta, otras definiciones dejan fuera la\(\TMstay\) “instrucción”. En otras formas, nuestra definición es más restrictiva. Supusimos que la cinta es infinita en una sola dirección, otras definiciones permiten que la cinta sea infinita tanto a la izquierda como a la derecha. De hecho, incluso se puede permitir cualquier número de cintas separadas, o incluso una cuadrícula infinita de cuadrados. Representamos el conjunto de instrucciones de la máquina Turing mediante una función de transición; otras definiciones utilizan una relación de transición donde la máquina tiene más de una instrucción posible en cualquier situación dada.

Esta última relajación de la definición es particularmente interesante. En nuestra definición, cuando la máquina está en símbolo de\(q\) lectura de estado\(\sigma\),\(\delta(q, \sigma)\) determina cuál es el nuevo símbolo, estado y posición del cabezal de cinta. Pero si permitimos que el conjunto de instrucciones sea una relación entre los pares de estado-símbolo actuales\(\tuple{q, \sigma}\) y los nuevos triples estado-símbolo-dirección\(\tuple{q', \sigma', D}\), la acción de la máquina de Turing puede no ser determinada de manera única, la relación de instrucción puede contener ambos\(\tuple{q, \sigma, q', \sigma', D}\) y \(\tuple{q, \sigma, q'', \sigma'', D'}\). En este caso tenemos una máquina Turing no determinista. Estos juegan un papel importante en la teoría de la complejidad computacional.

También hay diferentes convenciones para cuando una máquina Turing se detiene: decimos que se detiene cuando la función de transición no está definida, otras definiciones requieren que la máquina esté en un estado de detención designado especial. Dado que las cintas de nuestras máquinas Turing son infinitas en una sola dirección, hay casos en los que una máquina Turing no puede llevar a cabo correctamente una instrucción: si lee el cuadrado más a la izquierda y se supone que debe moverse hacia la izquierda. Según nuestra definición, simplemente se queda en su lugar, pero podríamos haberlo definido para que se detenga cuando eso suceda.

También hay diferentes formas de representar números (y de ahí la función de entrada-salida calculada por una máquina de Turing): usamos representación unaria, pero también se puede usar representación binaria. Esto requiere de dos símbolos además de\(\TMblank\) y\(\TMendtape\).

Ahora bien, aquí hay un dato interesante: ninguna de estas variaciones importa en cuanto a qué funciones son computables Turing. Si una función es Turing computable de acuerdo con una definición, es Turing computable de acuerdo con todas ellas.