"Ты помнишь, как все начиналось...?"

Итак, приступаю (и, по старой доброй национальной традиции, не прямо к делу, а несколько издалека)...
Почти всякий курс математической логики начинается стандартно: с исчисления высказываний. Вводятся логические операции (иначе, связки): конъюнкция, дизъюнкция, отрицание, импликация и эквивалентность; также постулируется наличие двух истинностных значения: истина (true) и ложь (false).
Далее, приводятся таблицы истинности логических связок и изучаются способы определения истинности логических формул путем построения таблиц. Учащемуся предлагается изучить два-три десятка логических формул (иногда и больше), которые при любых значениях истинности составляющих их частей, всегда имеют значение true и показывается, как эти формулы можно применять. Потом наступает пора исчисления предикатов и прочих технических вещей, которые не слишком сложны, но порой утомительны. Понятно, что порядок и способ изложения тех или иных понятий может, конечно, разниться, но общая тенденция примерно такова.
Когда учащийся окончательно притомится и начнет терять надежду выпутаться из бесконечных таблиц, логических формул, когда он почти разуверится, что все это может быть не только полезным, но и интересным, это самое интересное и наступает: теория множеств (причем, уровень изложения может быть от элементарного - на уровне понятий, до весьма продвинутого), формальная арифметика и теория доказательств. Обычно, тут излагаются действительно интересные и глубокие вещи: теоремы Геделя, обсуждаются парадоксы и т.д.
Если остается время и силы учащегося окончательно не иссякли, то иногда дается введение в теорию рекурсивных функций и теорию вычислимости.
Тема настоящего блога как раз последнее - вопросы вычислимости. Мы не будем глубоко и тщательно касаться теории (для этого есть много хороших книг, написанных выдающимися специалистами; упомянем имена Д.Гильберта, С.Клини, А.Тарского и других), а в основном займемся практикой. Разумеется, без базовых понятий в той же математической логике не обойтись. Тем, кто запамятовал, что это такое лучше обратиться к какому-нибудь стандартному учебнику, скажем, книгам Мендельсона, Колмогорова, Клини или Новикова (одним словом, подойдет любой университетский учебник логики для математических факультетов, какой читетель сможет найти).
В качестве более живого и увлекательного (но, отнюдь далеко не простого) чтения, можно порекомендовать великолепные книги американского логика и известного популяризатора Р.Смаллиана: поищите, не пожалеете.
Вот, пожалуй, и все, что я хотел сегодня поведать. До встречи и удачи всем !!!