Тезисы Тьюринга и Чёрча

Одно из основных свойств алгоритма заключается в том, что он представляет собой единый способ, позволяющий для каждой задачи из искомого бесконечного множества задач за конечное число шагов найти её решение.

На понятие алгоритма можно взглянуть и с несколько иной точки зрения. Каждую задачу из бесконечного множества задач можно выразить (закодировать) некоторым словом некоторого алфавита, а решение задачи каким-то другим словом того же алфавита. В результате получим функцию, заданную на некотором подмножестве множества всех слов выбранного алфавита и принимающую значение в множестве всех слов того же алфавита. Решить какую-либо – значит найти значение этой функции на слове, кодирующем данную задачу. А иметь алгоритм для решения всех задач данного класса – значит иметь единый способ, позволяющий за конечное число шагов «вычислить» значение построенной функции для любых значений аргумента из её области определения. Таким образом, алгоритмическая проблема – по существу проблема о вычислении значений заданной функции в некотором алфавите.

Остается уточнить, что значит уметь вычислить значение функции. Это значит вычислить значение функции с помощью подходящей машины Тьюринга. Для каких же функций возможно их тьюрингово вычисление? Многочисленные исследования ученых показали, что такой класс функций чрезвычайно широк. Каждая функция, для вычисления значений которой существует какой-нибудь алгоритм, оказалась вычисляемой посредством некоторой машины Тьюринга. Это дало повод Тьюрингу высказать следующую гипотезу, называемую основной гипотезой теории алгоритмов или тезисом Тьюринга.

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

Это означает, что строгое математическое понятие вычислимое по Тьюрингу функции является идеальной моделью взятого из опыта понятия алгоритма. Данный тезис есть не что иное, как аксиома, постулат, о взаимосвязях нашего опыта с той математической теорией, которую мы под этот опыт хотим подвести. Конечно же, данный тезис в принципе не может быть доказан методами математики, потому что он не имеет внутри математического характера (одна сторона в тезисе – понятие алгоритма – не является точным математическим понятием). Он выдвинут, исходя из опыта, и именно опыт подтверждает его состоятельность.

Впрочем, не исключается принципиальная возможность того, что тезис Тьюринга будет опровергнут. Для этого должна быть указана функция, вычисляемая с помощью какого-нибудь алгоритма, но не вычисляемая на какой-нибудь машине Тьюринга. Но такая возможность представляется маловероятной.

Подобно тезису Тьюринга в теории рекурсивной функции выдвигается соответствующая гипотеза, носящая название тезиса Чёрча.

Тезис Чёрча.Числовая функция тогда и только тогда алгоритмически вычислима, когда она рекурсивна.

И эта гипотеза не может быть доказана строго математически, она подтверждается практикой, опытом, ибо призвана увязать практику и теорию. Все рассматриваемые в математике конкретные функции, вычислимые в алгоритмическом смысле, оказались рекурсивными.

Мы познакомились с несколькими теориями, каждая из которых уточняет понятие алгоритма. Возникает вопрос, как связаны эти теории между собой. Ответ на него дает следующая теорема.

Теорема 1 Следующие классы функций (заданные на натуральных числах и принимающие натуральное значение) совпадают.

1) Класс всех функций вычислимых по Тьюрингу;

2) Класс всех рекурсивных функций.

Это уже не гипотеза и не тезис, а математическая теорема, которая строго доказывается.

Можно отметить, что существуют ещё и другие теории алгоритмов, и для всех них также доказана их равнозначность с рассматриваемыми теориями.

В 1936 году Чёрчем было доказано, что не существует алгоритма, позволяющего для каждой формулы логики предикатов определить, будет ли она выполнимой или общезначимой.

Одной из наиболее знаменитых алгоритмических проблем математики являлась 10-я проблема Гильберта, поставленная им в числе других в 1901 году на Международном математическом конгрессе. Требовалось найти алгоритм, определяющий для любого диофантова уравнения, имеет ли оно целочисленное решение.

Диофантово уравнение есть уравнение вида где – многочлен с целыми показателями степеней и целыми коэффициентами. В общем случае эта проблема долго оставалась нерешенной и только в 1970 году советский математик Ю. В. Матиясевич доказал её неразрешимость.

В заключение ещё раз отметим, что алгоритмическая неразрешимость означает лишь отсутствие единого способа для решения всех задач данной бесконечной серии, в то же время каждая индивидуальная задача вполне может быть решена индивидуальным способом. Так, например, несмотря на отсутствие единого алгоритма, определяющего имеет ли диофантово уравнение целочисленное решение, для частного случая диофантово уравнение хорошо известно, что все его целые корни следует искать среди делителей свободного члена

Вопросы для самоконтроля

1 Что Вы понимаете под машиной Тьюринга?

2 Из каких частей состоит машина Тьюринга?

3 Дайте определение машинного слова.

4 Какая функция называется числовой?

5 Какая функция называется частично-числовой?

6 Дайте определение функции, вычислимой по Тьюрингу.

7 Какие функции называются простейшими?

8 Дайте определение операции суперпозиции.

9 Дайте определение операции примитивной рекурсии.

10 Дайте определение операции минимизации.

11 Сформулируйте тезис Черча.

12 Сформулируйте тезис Тьюринга.

13 Какая связь между функциями, вычисляемыми по Тьюрингу и частично рекурсивными функциями?

 

 

 

 

ЛИТЕРАТУРА

1 Карпов, В. Г. Математическая логика и дискретная математика [Текст] : учебное пособие для студентов университетов / В.Г.Карпов,

В. А. Мощенский. – Мн. : Вышэйшая школа, 1977. – 255с.

2 Яблонский, С. В. Введение в дискретную математику [Текст] : учебное пособие для вузов по специальности «Прикладная математика» /

С. В. Яблонский. – М. : Наука, 1979. – 272с.

3 Мощенский, В. А. Лекции по математической логике [Текст] : учебное пособие для студентов математических специальностей вузов /

В. А. Мощенский. – Мн. : Изд. Центр БГУ, 1973. – 159с.

4 Лавров, И. А. Задачи по теории множеств, математической логике и теории алгоритмов [Текст] : учебное пособие для студентов математических специальностей вузов / И. А. Лавров, Л. Л. Максимова. – 2-е стер. – М. : Наука, 1984. – 223с.

5 Гаврилов, Г. П. Сборник задач по дискретной математике [Текст] : учебное пособие для вузов по специальности «Прикладная математика»/ Г. П. Гаврилов, А. А. Сапоженко. – М. : Наука, 1984. – 223с.