13.2: Enumeración de Máquinas Turing
- Page ID
- 103680
\( \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}\)Podemos demostrar que el conjunto de todas las máquinas Turing es contable. Esto se deduce del hecho de que cada máquina Turing puede describirse finitamente. El conjunto de estados y el vocabulario de cinta son conjuntos finitos. La función de transición es una función parcial de\(Q \times \Sigma\) a\(Q \times \Sigma \times \{\TMleft, \TMright, \TMstay\}\), y así mismo se puede especificar enumerando sus valores para los pares de argumentos finitamente muchos para los que se define. Por supuesto, estrictamente hablando, los estados y el vocabulario pueden ser cualquier cosa; pero el comportamiento de la máquina Turing es independiente de qué objetos sirven como estados y vocabulario. Entonces podemos suponer, por ejemplo, que los estados y los símbolos del vocabulario son números naturales, o que los estados y el vocabulario son todos cadenas de letras y dígitos.
Supongamos que arreglamos un vocabulario contablemente infinito para especificar máquinas Turing:\(\sigma_0 = \TMendtape\)\(\sigma_1 = \TMblank\),\(\sigma_2 = \TMstroke\),\(\sigma_3\),,,...\(\TMright\),\(\TMleft\),,\(\TMstay\),\(q_0\),\(q_1\) ,... Entonces cualquier máquina de Turing puede ser especificada por alguna cadena finita de símbolos de este alfabeto (aunque no todas las cadenas finitas de símbolos especifican una máquina de Turing). Por ejemplo, supongamos que tenemos una máquina Turing\(M = \tuple{Q, \Sigma, q, \delta}\) donde\[\begin{aligned} Q & = \{q'_0, \dots, q'_n\} \subseteq \{q_0, q_1, \dots \} \text{ and}\\ \Sigma & = \{\TMendtape, \sigma'_1, \sigma'_2, \dots, \sigma'_m\} \subseteq \{\sigma_0, \sigma_1, \dots\}.\end{aligned}\] podríamos especificarla por la cadena\[q'_0 q'_1 \dots q'_n \TMendtape \sigma'_1 \dots \sigma'_m \TMendtape q \TMendtape S(q_0',\sigma'_0)\TMendtape \dots \TMendtape S(q'_n,\sigma'_m)\nonumber\] donde\(S(q'_j,\sigma'_i)\) está la cadena\(q'_j \sigma'_i \delta(q'_j, \sigma'_i)\) si\(\delta(q'_j, \sigma'_i)\) está definida, y\(q'_j \sigma'_i\) de lo contrario.
Teorema\(\PageIndex{1}\)
Hay funciones\(\Nat\) a partir de las\(\Nat\) cuales no son computables Turing.
Prueba. Sabemos que el conjunto de cadenas finitas de símbolos de un alfabeto contablemente infinito es contable. Esto nos da que el conjunto de descripciones de las máquinas Turing, como subconjunto de las cadenas finitas del vocabulario contable\(\{q_0, q_1, \dots, \TMendtape, \sigma_1, \sigma_2, \dots\}\), es en sí mismo enumerable. Dado que cada función computable de Turing es calculada por algunas (de hecho, muchas) máquinas Turing, esto significa que el conjunto de todas las funciones computables de Turing de\(\Nat\) a también\(\Nat\) es enumerable.
Por otro lado, el conjunto de todas las funciones de\(\Nat\) a no\(\Nat\) es contable. Esto se deduce inmediatamente del hecho de que ni siquiera el conjunto de todas las funciones de un argumento desde\(\Nat\) el conjunto\(\{0,1\}\) es contable. Si todas las funciones fueran computables por alguna máquina de Turing podríamos enumerar el conjunto de todas las funciones. Entonces hay algunas funciones que no son computables Turing. ◻