WikiDer > Nqthm

Nqthm

Nqthm это средство доказательства теорем иногда упоминается как Устройство доказательства теорем Бойера – Мура. Это было предшественником ACL2.[1]

История

Система была разработана Роберт С. Бойер и Дж. Стротер Мур, профессора информатики в Техасский университет, Остин. Они начали работу над системой в 1971 году в г. Эдинбург, Шотландия. Их целью было создание полностью автоматического средства доказательства теорем, основанного на логике. Они использовали вариант Чистый LISP как рабочая логика.

Определения

Определения формируются как полностью рекурсивные функции, в системе широко используются переписывание и индукция эвристика, которая используется при переписывании, и то, что они называли символической оценкой, терпит неудачу.

Система была построена на Лиспе и обладала некоторыми очень элементарными знаниями о том, что называлось "нулевое значение", состояние машины после самонастройка это на реализацию Common Lisp.

Это пример доказательства простой арифметической теоремы. Функция ВРЕМЯ является частью САПОГИ-РЕМЕНЬ (называемый «спутником») и определяется как

 (DEFN ВРЕМЯ (Икс Y)  (ЕСЛИ (ZEROP Икс)      0      (PLUS Y (ВРЕМЯ (SUB1 Икс) Y))))

Формулировка теоремы

Формулировка теоремы также дается в синтаксисе, подобном Лиспу:

 (Доказательная лемма коммутативность времен (переписать)   (равный (раз Икс z) (раз z Икс)))

Если теорема окажется верной, она будет добавлена ​​в базу знаний системы и может использоваться как правило переписывания для будущих доказательств.

Само доказательство дается квазиестественным языком. Авторы случайным образом выбирают типичные математические фразы для включения шагов в математическое доказательство, что на самом деле делает доказательства вполне читаемыми. Есть макросы для Латекс который может преобразовать структуру Лиспа в более или менее читаемый математический язык.

Доказательство коммутативности времен продолжается:

 Дайте гипотезе имя * 1. Обратимся к индукции. Термины гипотезы предполагают две индукции, обе ошибочны. Мы ограничиваем наше рассмотрение двумя, предложенными наибольшим числом непримитивных рекурсивных функций в гипотезе. Поскольку оба варианта одинаково вероятны, мы выберем произвольно. Мы будем проводить индукцию по следующей схеме: (AND (IMPLIES (ZEROP X) (p X Z)) (IMPLIES (AND (NOT (ZEROP X)) (p (SUB1 X) Z)) (p X Z))). Линейная арифметика, лемма COUNT-NUMBERP и определение ZEROP сообщают нам, что мера (COUNT X) убывает в соответствии с хорошо обоснованным соотношением LESSP на каждом шаге индукции схемы. Приведенная выше схема индукции приводит к следующим двум новым гипотезам: Случай 2. (ПОДРАЗУМЕВАЕТСЯ (ZEROP X) (EQUAL (TIMES X Z) (TIMES Z X))).

и после ряда доказательств индукции, наконец, приходит к выводу, что

Случай 1. (ПОДРАЗУМЕВАЕТ (И (НЕ (ZEROP Z)) (EQUAL 0 (TIMES (SUB1 Z) 0))) (EQUAL 0 (TIMES Z 0))). Это упрощает, расширяя определения ZEROP, TIMES, PLUS , и EQUAL, to: T. Это завершает доказательство * 1.1, которое также завершает доказательство * 1.QED [0.0 1.2 0.5] COMMUTATIVITY-OF-TIMES

Доказательства

Многие доказательства были сделаны или подтверждены системой, в частности

  • (1971) конкатенация списков
  • (1973) сортировка вставкой
  • (1974) двоичный сумматор
  • (1976) компилятор выражений для стековой машины
  • (1978) единственность простых факторизаций
  • (1983) обратимость алгоритма шифрования RSA
  • (1984) неразрешимость проблемы остановки для Pure Lisp
  • (1985) Микропроцессор FM8501 (Уоррен Хант) [2]
  • (1986) Теорема Гёделя о неполноте (Шанкар)
  • (1988) Стек CLI (Билл Бевьер, Уоррен Хант, Мэтт Кауфманн, Дж. Мур, Билл Янг)
  • (1990) Закон квадратичной взаимности Гаусса (Дэвид Руссинофф)
  • (1992) Византийские генералы и синхронизация часов (Бевье и Янг)
  • (1992) Компилятор для подмножества языка Nqthm (Артур Флэтэу)
  • (1993) протокол асинхронной связи двухфазной метки
  • (1993) Motorola MC68020 и Библиотека строк Berkeley C (Юань Ю)
  • (1994) Теорема Пэрис – Харрингтона Рамсея (Кеннет Кунен)
  • (1996) Эквивалентность NFSA и DFSA (Дебора Вебер-Вульф)

PC-Nqthm

Более мощная версия под названием PC-Nqthm (Proof-checker Nqthm) была разработана Мэтт Кауфманн. Это предоставило пользователю инструменты доказательства, которые система использует автоматически, чтобы можно было дать больше указаний по доказательству. Это очень помогает, поскольку система имеет непродуктивную тенденцию блуждать по бесконечным цепочкам индуктивных доказательств.

Литература

  • Справочник по вычислительной логике, Р. Бойер и Дж. С. Мур, Academic Press (2-е издание), 1997.
  • Средство доказательства теорем Бойера-Мура и его интерактивное усовершенствование, совместно с М. Кауфманном и Р. С. Бойером, «Компьютеры и математика с приложениями», 29 (2), 1995, стр. 27–62.

Награды

Награда

В 2005 году Роберт С. Бойер, Мэтт Кауфманн, и Дж. Стротер Мур получил Награда ACM Software System за их работу над средством доказательства теорем Nqthm.[3]

Рекомендации

  1. ^ "Nqthm, испытатель Бойера-Мура".
  2. ^ Хант младший, Уоррен А. (1986), FM8501: проверенный микропроцессор, Технический отчет, 47, Техасский университет в Остине
  3. ^ Ассоциация вычислительной техники, «ACM: пресс-релиз, 15 марта 2006 г.»[постоянная мертвая ссылка], campus.acm.org, по состоянию на 27 декабря 2007 г. (английская версия).

внешняя ссылка