JК
Принцесса или тигр :: Смаллиан Рэймонд
Страница: 254 из 257Поэтому полное познание машины U означает полное познание всех машин, а следовательно, и всея математических систем. И наоборот, любой вопрос том, напечатает ли некая машина заданное число; может быть сведен к вопросу о том, доказуемо ли тo или иное утверждение в определенной математической системе. Таким образом, полное познание всех формальных математических систем означает полное познание нашей универсальной машины.
Итак, главный вопрос, стоящий перед нами, можно сформулировать следующим образом. Пусть V — множество чисел, которые может напечатать универсальная машина U (это множество иногда называют универсальным множеством). Разрешимо множество V или нет? Если оно разрешимо, то мечта Лейбница осуществима; если же нет, то его стремления никогда не смогут быть реализованы. Поскольку V эффективно перечислимо (ведь оно генерируется машиной U), то вопрос сводится к тому, существует ли некая машина Ма, которая сможет напечатать дополнение V, а именно множество V'. Иначе говоря, существует ли такая машина Ма, которая печатает те и только те числа, которые машина U не печатает? На этот вопрос можно дать исчерпывающий ответ лишь на основании утверждений 1 и 2, о которых мы упоминали выше.
Теорема L. Множество V' не является эффективно перечислимым: для любой заданной машины Ма либо существует какое-то число, принадлежащее множеству V, которое машина Ма не может напечатать, либо машина Ма напечатает по крайней мере одно число, которое принадлежит не множеству V', а множеству V.
Итак, главный вопрос, стоящий перед нами, можно сформулировать следующим образом. Пусть V — множество чисел, которые может напечатать универсальная машина U (это множество иногда называют универсальным множеством). Разрешимо множество V или нет? Если оно разрешимо, то мечта Лейбница осуществима; если же нет, то его стремления никогда не смогут быть реализованы. Поскольку V эффективно перечислимо (ведь оно генерируется машиной U), то вопрос сводится к тому, существует ли некая машина Ма, которая сможет напечатать дополнение V, а именно множество V'. Иначе говоря, существует ли такая машина Ма, которая печатает те и только те числа, которые машина U не печатает? На этот вопрос можно дать исчерпывающий ответ лишь на основании утверждений 1 и 2, о которых мы упоминали выше.
Теорема L. Множество V' не является эффективно перечислимым: для любой заданной машины Ма либо существует какое-то число, принадлежащее множеству V, которое машина Ма не может напечатать, либо машина Ма напечатает по крайней мере одно число, которое принадлежит не множеству V', а множеству V.