12.9: La Tesis Iglesia-Turing

Última actualización
Guardar como PDF

Page ID: 103688

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

Se supone que las máquinas Turing son un reemplazo preciso del concepto de un procedimiento efectivo. Turing pensó que cualquiera que captara tanto el concepto de un procedimiento efectivo como el concepto de una máquina Turing tendría la intuición de que cualquier cosa que se pudiera hacer a través de un procedimiento efectivo podría ser hecha por la máquina Turing. Esta afirmación está respaldada por el hecho de que todas las demás sustituciones precisas propuestas para el concepto de un procedimiento efectivo resultan ser extensamente equivalentes al concepto de una máquina Turing, es decir, pueden calcular exactamente el mismo conjunto de funciones. A esta afirmación se le llama la tesis Iglesia-Turing.

Definición\(\PageIndex{1}\): Church-Turing thesis

La Tesis Iglesia-Turing establece que cualquier cosa computable a través de un procedimiento efectivo es Turing computable.

La tesis Iglesia-Turing es apelada de dos maneras. El primer tipo de uso de la tesis Iglesia-Turing es una excusa para la pereza. Supongamos que tenemos una descripción de un procedimiento efectivo para computar algo, digamos, en “pseudo-código”. Entonces podemos invocar la tesis Iglesia-Turing para justificar la afirmación de que la misma función es calculada por alguna máquina de Turing, aunque de hecho no la hayamos construido.

El otro uso de la tesis Iglesia-Turing es más filosóficamente interesante. Se puede demostrar que hay funciones que no pueden ser calculadas por las máquinas Turing. A partir de esto, utilizando la tesis Church-Turing, se puede concluir que no se puede computar efectivamente, utilizando ningún procedimiento alguno. Porque si existiera tal procedimiento, por la tesis Church-Turing, se seguiría que habría una máquina de Turing. Entonces, si podemos probar que no hay una máquina de Turing que lo compute, tampoco puede haber un procedimiento efectivo. En particular, se invoca la tesis Church-Turing para afirmar que el llamado problema de la detención no sólo no puede ser resuelto por máquinas Turing, no puede resolverse efectivamente en absoluto.