12.3: Máquinas Turing

Última actualización
Guardar como PDF

Page ID: 103682

\( \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

La definición formal de lo que constituye una máquina Turing parece abstracta, pero en realidad es simple: simplemente empaqueta en una estructura matemática toda la información necesaria para especificar el funcionamiento de una máquina Turing. Esto incluye (1) que indica que la máquina puede estar en, (2) qué símbolos pueden estar en la cinta, (3) qué estado debe comenzar la máquina, y (4) cuál es el conjunto de instrucciones de la máquina.

Definición\(\PageIndex{1}\): Turing machine

Una máquina de Turing\(M\) es una tupla\(\langle Q, \Sigma, q_0, \delta\rangle\) que consiste en

un conjunto finito de estados\(Q\),
un alfabeto finito\(\Sigma\) que incluye\(\TMendtape\)\(\TMblank\) y
un estado inicial\(q_0 \in Q\),
un conjunto de instrucciones finito\(\delta\colon Q \times \Sigma \pto Q \times \Sigma \times \{\TMleft, \TMright, \TMstay\}\).

La función parcial también\(\delta\) se llama la función de transición de\(M\).

Suponemos que la cinta es infinita en una sola dirección. Por esta razón es útil designar un símbolo especial\(\TMendtape\) como marcador para el extremo izquierdo de la cinta. Esto facilita que los programas de máquinas Turing indiquen cuándo están “en peligro” de salir de la cinta. Podríamos suponer que este símbolo nunca se sobrescribe, es decir, que\(\delta(q,\TMendtape) = \tuple{q', \TMendtape, x}\) si\(\delta(q,\TMendtape)\) se define. Algunos libros de texto hacen esto, nosotros no. Simplemente puede tener cuidado al construir su máquina Turing que nunca sobrescribe\(\TMendtape\). Además, hay casos en los que permitir tal sobrescritura proporciona cierta flexibilidad conveniente.

Ejemplo\(\PageIndex{1}\)

Even Machine: La máquina par es formalmente la cuádruple\(\tuple{Q, \Sigma, q_0, \delta}\) donde\[\begin{aligned} Q & = \{ q_0, q_1 \} \\ \Sigma & = \{ \TMendtape, \TMblank, \TMstroke \}, \\ \delta(q_0, \TMstroke) & = \tuple{q_1, \TMstroke, \TMright},\\ \delta(q_1, \TMstroke) & = \tuple{q_0, \TMstroke, \TMright},\\ \delta(q_1, \TMblank) & = \tuple{q_1, \TMblank, \TMright}.\end{aligned}\]