Логика - доступно для всех

  • Увеличить размер шрифта
  • Размер шрифта по умолчанию
  • Уменьшить размер шрифта

Тезис Черча. Алгоритмически неразрешимые проблемы.

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Узнать стоимость

Мы видели, что поведение  машины Тьюринга определяется ее таблицей; если мы знаем таблицу, мы знаем по существу и машину.

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

Понятие машины Тьюринга является строгим уточнением понятия алгоритма. Переход от интуитивного понятия алгоритма к точному понятию машины Тьюринга позволяет решить вопрос алгоритмической (машинной) разрешимости той или иной проблемы.

Один из первых отрицательных результатов был получен американским ученым Черчем в 1936 г. при рассмотрении проблемы распознавания выводимости в математической логике.

Определить для любых заданных формул R и S в логическом исчислении, существует ли дедуктивная цепочка, ведущая от R к S, или нет.

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

Проблема является алгоритмически неразрешимой, если не существует алгоритма (соответствующей машины Тьюринга) для ее решения. Отдельная машина Тьюринга может быть представлена как программа произвольного вида для ЦВМ с потенциально бесконечной памятью.

Внимание!
Если вам нужна помощь в написании работы, то рекомендуем обратиться к профессионалам. Более 70 000 авторов готовы помочь вам прямо сейчас. Бесплатные корректировки и доработки. Узнайте стоимость своей работы.

Теорема 8.1 (теорема Черча). Проблема распознавания выводимости алгоритмически неразрешима.