Тезис Геделя. Теорема Черча — страница 2

  • Просмотров 3236
  • Скачиваний 332
  • Размер файла 4
    Кб

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

до сих пор. Ее суть заключается в следующем. Программу машины Тьюринга можно закодировать каким-либо определенным шифром. На ленте машины можно изобразить ее же собственный шифр, записанный в алфавите машины. Здесь как и в случае обычной программы возможны два случая: 1. машина применима к своему шифру, то есть она перерабатывает этот шифр и после конечного числа тактов останавливается; 2. машина неприменима к своему шифру, то

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

неразрешима. 3). Проблема эквивалентности слов для ассоциативных исчислений. Рассмотрим некоторый алфавит и множество слов в этом алфавите. Будем рассматривать преобразования одних слов в другие с помощью некоторых допустимых подстановок , где и два слова в том же алфавите Если слово содержит как подслово, например Ассоциативным исчислением называется совокупность всех слов в некотором алфавите вместе с какой-нибудь

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

называются эквивалентными: Для каждого ассоциативного исчисления возникает своя специальная проблема эквивалентности слов: для любых двух слов в данном исчислении требуется узнать эквивалентны они или нет. Теорема 3. Проблема эквивалентности слов в любом ассоциативном исчислении алгоритмически неразрешима. Эта проблема решена лишь в некоторых ассоциативных исчислениях специального вида. Математические теории.