12.4: Configuraciones y cómputos
- Page ID
- 103681
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Recordemos el rastreo a través de las configuraciones de la máquina par antes. El mecanismo imaginario que consiste en cinta, cabezal de lectura/escritura y programa de máquina Turing es realmente una forma intuitiva de visualizar lo que es un cálculo de máquina Turing. Formalmente, podemos definir el cálculo de una máquina de Turing en una entrada dada como una secuencia de configuraciones —y una configuración a su vez es una secuencia de símbolos (correspondiente al contenido de la cinta en un punto dado en el cálculo), un número que indica la posición del cabezal de lectura/escritura, y un estado. Usando estos, podemos definir lo que la máquina Turing\(M\) computa en una entrada dada.
Definición\(\PageIndex{1}\): Configuration
Una configuración de la máquina Turing\(M = \tuple{Q, \Sigma, q_0, \delta}\) es un triple\(\tuple{C, m, q}\) donde
-
\(C \in \Sigma^*\)es una secuencia finita de símbolos de\(\Sigma\),
-
\(m \in \Nat\)es un número\(< \len{C}\), y
-
\(q \in Q\)
Intuitivamente, la secuencia\(C\) es el contenido de la cinta (símbolos de todos los cuadrados desde el cuadrado más a la izquierda hasta el último cuadrado no en blanco o visitado previamente),\(m\) es el número del cuadrado que el cabezal de lectura/escritura está escaneando (comenzando\(0\) por ser el número del cuadrado más a la izquierda), y\(q\) es el estado actual de la máquina.
La entrada potencial para una máquina Turing es una secuencia de símbolos, generalmente una secuencia que codifica un número de alguna forma. La configuración inicial de la máquina Turing es aquella configuración en la que iniciamos la máquina Turing para trabajar en esa entrada: la cinta contiene el marcador final de cinta inmediatamente seguido de la entrada escrita en los cuadrados a la derecha, el cabezal de lectura/escritura está escaneando el cuadrado más a la izquierda de la entrada (es decir, el cuadrado a la derecha del marcador del extremo izquierdo), y el mecanismo está en el estado de inicio designado\(q_0\).
Definición\(\PageIndex{2}\): Initial configuration
La configuración inicial de\(M\) para entrada\(I \in \Sigma^*\) es\[\tuple{\TMendtape \frown I, 1, q_0}.\nonumber\]
El\(\frown\) símbolo es para concatenación —queremos asegurarnos de que no haya espacios en blanco entre el marcador final izquierdo y el comienzo de la entrada.
Definición\(\PageIndex{3}\)
Decimos que una configuración\(\tuple{C, m, q}\) produce la configuración\(\tuple{C', m', q'}\) en un solo paso (según\(M\)), iff
-
el\(m\) -ésimo símbolo de\(C\) es\(\sigma\),
-
el conjunto de instrucciones\(M\) especifica\(\delta(q, \sigma) = \tuple{q', \sigma', D}\),
-
el\(m\) -ésimo símbolo de\(C'\) es\(\sigma'\), y
-
-
\(D = L\)y\(m' = m - 1\) si\(m>0\), de otro modo\(m'=0\), o
-
\(D = R\)y\(m' = m + 1\), o
-
\(D = N\)y\(m' = m\),
-
-
si\(m' = \len{C}\), entonces\(\len{C'} = \len{C} + 1\) y el\(m'\) -ésimo símbolo de\(C'\) es\(\TMblank\). De lo contrario\(\len{C'}=\len{C}\).
-
para todos\(i\) esos que\(i < \len{C}\) y\(i \neq m\),\(C'(i) = C(i)\),
Definición\(\PageIndex{4}\)
Una ejecución\(M\) de entrada\(I\) es una secuencia\(C_i\) de configuraciones de\(M\), donde\(C_0\) está la configuración inicial de\(M\) para entrada\(I\), y cada \(C_i\)rinde\(C_{i+1}\) en un solo paso.
Decimos que se\(M\) detiene en la entrada\(I\) después de \(k\)los pasos si\(C_k = \tuple{C, m, q}\), el símbolo\(m\) th de\(C\) es\(\sigma\), y\(\delta(q, \sigma)\) es indefinido. En ese caso, la salida de\(M\) para entrada\(I\) es\(O\), donde\(O\) es una cadena de símbolos que no comienza o termina en\(\TMblank\) tal que\(C = \TMendtape \concat \TMblank^i \concat O \concat \TMblank^j\) para algunos\(i, j \in \Nat\).
De acuerdo con esta definición, la salida\(O\) de\(M\) siempre comienza y termina en un símbolo distinto de\(\TMblank\), o, si en\(k\) el momento se llena toda la cinta\(\TMblank\) (excepto el más a la izquierda\(\TMendtape\)), \(O\)es la cadena vacía.