Тезис Геделя. Теорема Черча

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

Приватний вищий навчальний заклад Європейський Університет Уманська філія Кафедра математики та інформатики Реферат з дисципліни «Теория алгоритмів та представлення знань» на тему: «Тезис Гьоделя. Теорема Черча» Перевірив: Виконав: викладач студент 3-го курсу Бєсєдіна С.В. 36 групи Оцінка ______ Левицький Е.Г. Умань – 2005 Зміст 1. TOC o "1-3" h z u Вступ. PAGEREF _Toc119118926 h 3 2.Теорема Черча. Проблема распознавания выводимости

алгоритмически неразрешима. PAGEREF _Toc119118927 h 4 3. Проблема распознавания самоприменимости алгоритмически неразрешима. PAGEREF _Toc119118928 h 5 4. Проблема эквивалентности слов в любом ассоциативном исчислении алгоритмически неразрешима. PAGEREF _Toc119118929 h 6 5.Примеры теорий первого порядка. PAGEREF _Toc119118930 h 8 6.Теорема Геделя о неполноте. PAGEREF _Toc119118931 h 9 7.Список використаних джерел. 15 Вступ Введение понятия машины Тьюринга уточняет понятие алгоритма и

указывает путь решения какой-то массовой проблемы. Однако машина Тьюринга бывает неприменима к начальной информации (исходному слову алфавита). Та же ситуация повторяется относительно некоторых задач, для решения которых не удается создать машины Тьюринга. Один из первых результатов такого типа получен Черчем в 1936 году. Он касается проблемы распознавания выводимости в математической логике. 1). Аксиоматический метод в

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

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