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

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

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

Тест на логику "Логическое сравнение". 93% не проходят его с первого раза.А ты?

Пройти тест

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

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

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

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

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

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

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

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

 

Случайная новость

  • Задание 2.
    Дайте полную логическую характеристику понятиям: ...