12.9: Теза Церква-Тьюринга

Last updated
Save as PDF

Page ID: 53014

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

Машини Тьюринга повинні бути точною заміною концепції ефективної процедури. Тьюринг думав, що кожен, хто схопив як концепцію ефективної процедури, так і концепцію машини Тьюринга, матиме інтуїцію, що все, що можна зробити за допомогою ефективної процедури, може бути зроблено машиною Тьюринга. Це твердження підтверджується тим, що всі інші запропоновані точні заміни для концепції ефективної процедури виявляються екстенційно еквівалентними концепції машини Тьюринга - тобто вони можуть обчислити точно такий же набір функцій. Це твердження називається тезою Церква-Тьюринга.

Визначення\(\PageIndex{1}\): Church-Turing thesis

Теза Церква-Тьюринга стверджує, що все, що обчислюється за допомогою ефективної процедури Тьюринга обчислюється.

Теза Церква-Тьюринга оскаржується двома способами. Перший вид використання тези Церква-Тьюринга - це привід для ліні. Припустимо, у нас є опис ефективної процедури обчислення чогось, скажімо, в «псевдокоді». Тоді ми можемо посилатися на тезу Церква-Тьюринга, щоб обґрунтувати твердження про те, що одна і та ж функція обчислюється якоюсь машиною Тьюринга, навіть якщо ми насправді не побудували її.

Інше використання тези Церква-Тьюринга є більш філософськи цікавим. Можна показати, що існують функції, які не можуть бути обчислені машинами Тьюринга. З цього, використовуючи тезу Церква-Тьюринга, можна зробити висновок, що її неможливо ефективно обчислити, використовуючи будь-яку процедуру. Бо якби була така процедура, за тезою Церква-Тьюринга, випливало б, що була б машина Тьюринга. Отже, якщо ми можемо довести, що немає машини Тьюринга, яка її обчислює, також не може бути ефективної процедури. Зокрема, теза Церква-Тьюринга посилається стверджувати, що так звана проблема зупинки не тільки не може бути вирішена машинами Тьюринга, вона взагалі не може бути ефективно вирішена.