Сборник содержит работы, посвященные оценкам сложности алгоритмов и вычислений, классификациям рекурсивных функций и различным типам вычислительных устройств, связанных с такими классификациями. Рассматриваются «ограниченные» машины Тьюринга, обощения конечных автоматов.
В книге описываются узловые моменты становления наиболее заметных концепций в истории логики с древнейших времен до начала XX столетия. Особое внимание уделяется зарождению и развитию алгебраических методов в логике.
Посвящается одному из актуальных и бурно развивающихся разделов математической логики – теории алгоритмов, а также важнейшим ее связям с другими разделами математики. Является одним из лучших пособий для знакомства с основными направлениями, идеями и методами теории алгоритмов.
В книге дается доступное для начинающего читателя и достаточно полное изложение основных разделов современной математической логики и многих ее приложений. Наряду с такими разделами, как логика высказываний, исчисление предикатов, формальная арифметика и теория алгоритмов, в ней освещены также теория моделей и аксиоматическая теория множеств.
В учебном пособии содержится материал основного курса «Введение в математическую логику», читаемого на механико-математическом факультете МГУ. Излагаются элементы теории множеств, основные понятия, относящиеся к семантике формализованных логико-математических языков первого порядка, исчисление предикатов и теорема о его полноте, дается введение в теорию алгоритмов и вычислимых функций. Для студентов математических факультетов университетов, педагогических институтов, а также других вузов с углубленным изучением информатики и кибернетики.
В книге известных американских математиков излагаются разделы теории вычислимости. Связанные с логической проблематикой. Излагаются основные методы теории вычислимости, приводятся доказательства теорем о неразрешимости логики предикатов пеервого порядка, тьюрингова вычислимость, теоремы Геделя о неполноте, нестандартные модели и многое другое.
Монография американских ученых, посвященная вопросам сложности решения комбинаторных задач, возникающих в дискретной оптимизации, математическом программировании, алгебре, теории чисел, теории автоматов, математической логике, теории множеств, теории графов и т.п. Книга отличается строгим и систематическим изложением теории в приложении содержится более 300 труднорешаемых задач из различных разделов математики.
В книге изложены основные классические исчисления математической логики: исчисление высказываний и исчисление предикатов; имеется краткое изложение основных понятий теории множеств и теории алгоритмов. Ряд разделов книги — теория моделей и теория доказательств — изложены более подробно, чем это предусмотрено программой. Для студентов математических специальностей вузов. Может служить пособием для спецкурсов.
Книга содержит изложение современного состояния теории рекурсивных функций и обзор основных приложений этой теории. В ней прослежено развитие теории рекурсивных функций, начиная с ее зарождения в тридцатых годах и кончая результатами исследований самых последних лет. Не предполагающая в основной своей части никаких предварительных знаний, кроме знакомства с теоретико-множественной терминологией, книга Роджерса написана хорошим, ясным языком.
Эта монография принадлежит перу одного из самых известных современных специалистов в области математической логики. Она задумана автором в качестве учебника для студентов, а также в известной мере в качестве справочника. Предполагая у читателя только общую математическую культуру, книга с первых же страниц вводит его в глубокую проблематику, связанную с основными понятиями математической логики. Изложенный в ней материал представляет ценность для всякого математика, в том числе и для специалиста по математической логике.