Мы видели, что поведение машины Тьюринга определяется ее таблицей; если мы знаем таблицу, мы знаем по существу и машину.
Тезис Тьюринга. Для любого алгоритма, понимаемого в интуитивном смысле, можно построить машину Тьюринга, функционирование которой эквивалентно этому алгоритму.
Понятие машины Тьюринга является строгим уточнением понятия алгоритма. Переход от интуитивного понятия алгоритма к точному понятию машины Тьюринга позволяет решить вопрос алгоритмической (машинной) разрешимости той или иной проблемы.
Один из первых отрицательных результатов был получен американским ученым Черчем в 1936 г. при рассмотрении проблемы распознавания выводимости в математической логике.
Определить для любых заданных формул R и S в логическом исчислении, существует ли дедуктивная цепочка, ведущая от R к S, или нет.
Если формула А может быть преобразована в формулу В однократным применением допустимой подстановки, и наоборот, то А и В — смежные формулы. Последовательность формул, соседние из которых смежные, называется дедуктивной цепочкой, ведущей от к . Под решением проблемы распознавания выводимости понимается алгоритм, дающий ответ на вопрос о существовании дедуктивной цепочки (для любых R и S).
Проблема является алгоритмически неразрешимой, если не существует алгоритма (соответствующей машины Тьюринга) для ее решения. Отдельная машина Тьюринга может быть представлена как программа произвольного вида для ЦВМ с потенциально бесконечной памятью.
Теорема 8.1 (теорема Черча). Проблема распознавания выводимости алгоритмически неразрешима.