Принцесса или тигр   ::   Смаллиан Рэймонд

Машина Мак-Каллоха и теоремы Геделя



Возможно, читатель уже отметил определенное сходство приведенных выше задач с некоторыми свойствами первой машины Мак-Каллоха. В самом деле, работа этой машины оказывается связанной с теоремой Гёделя, и вот каким образом.

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

Условие Мс1. Для любых чисел X и Y, если число X порождает число Y в первой машине Мак-Каллоха, утверждение 8Х истинно тогда и только тогда, если утверждение Y доказуемо. (Напомним, что число 8Х это не 8, умноженное на X, а цифра 8, за которой стоит число X.)

Условие Мс2. Для любого числа X утверждение 9X истинно тогда и только тогда, если утверждение X не является истинным.

Найдите такое число N, при котором утверждение N истинно, но недоказуемо в данной системе.

8. Предположим, что в условии Mс1 говорится не о «первой машине Мак-Каллоха», а о «третьей машине Мак-Каллоха». Попробуем теперь найти такое утверждение, которое было бы истинным, но недоказуемым.

9. Парадокс ли это?

Вернемся вновь к задаче 1, однако внесем в нее некоторые изменения.