Cтраница 2
Тома, следующие за томом 59, вскоре станут претолстыми, поскольку существуют миллионы различных способов комбинировать символы и составлять Белые Программы. Однако мы не будем печатать здесь весь этот бесконечный каталог; нам важно знать только то, что он четко определен и что каждая Белая Программа Блупа имеет свой собственный, неповторяющийся индекс. Именно в этом - основная идея. [16]
Мы также показали, что Блуп не описывает всех функций натуральных чисел, которые можно выразить словами. Можно ли улучшить Блуп таким образом, что Beldiag [ N ] станет в нем представимой. [17]
Но Beldiag [ N ] не может быть равен одновременно и числу, и его последователю, как утверждают эти два уравнения. Нам придется вернутся назад и избавиться от допущения, на котором основано это противоречие. Единственным кандидатом оказывается уравнение ( 2), утверждающее, что Beldiag [ N ] может быть закодировано как Белая Программа Блупа. И это доказывает, что Beldiag не является примитивно-рекурсивной функцией. [18]
Теперь нам нужен тест Блупа под названием ТЕРМИНАТОР. Однако хитроумный аргумент, придуманный Аланом Тюрингом, доказал, что никакая программа Блупа не сможет безошибочно находить это различие. [19]
Если у вас есть только цепь определений процедур, то ни одна из них не исполняется; для этого необходим некий вызов, вводящий специфические числовые величины. Только тогда процедуры начинают действовать. Это напомиа-ет мясорубку, ждущую, чтобы в нее заложили порцию мяса - или, скорее, целую цепь мясорубок, связанных таким образом, что каждая из них получает сырье от предыдущих. Сравнение с мясорубками, возможно, не слишком аппетитно; однако в случае программ Блупа это понятие очень важно. [20]
Нам самим не придется этим заниматься; упомянем только, что существует целый класс компьютерных программ с точно такой же выразительной мощностью, как Флуп, в том смысле, что любое вычисление, программируемое на одном языке, может быть запрограммировано на всех остальных языках. Интересно то, что почти любая попытка создать достойный внимания компьютерный язык приводит к созданию языка этого класса, то есть языка с выразительной мощностью Флупа. Приходится попотеть, чтобы создать достаточно интересный компьютерный язык слабее этих языков. Блуп, разумеется, пример более слабого языка, но это - скорее исключение, чем правило. Дело в том, что существует некий естественный путь создания алгоритмических языков, так что разные люди, работая назависимо друг от друга, обычно создают эквивалентные языки, отличающиеся скорее стилем, чем степенью мощности. [21]
Основное различие между методом Кантора и нашим методом заключается в том, какое предположение мы решили изменить В Канторовском методе этим предположением была сомнительная идея, что подобный список вообще возможен. Построение d доказало, что полную таблицу действительных чисел составить невозможно; иными словами, множество целых чисел не достаточно велико, чтобы пронумеровать множество всех действительных чисел. С другой стороны, в нашем доказательстве мы знаем, что список Белых Программ можно составить1 множество целых чисел достаточно велико, чтобы пронумеровать множество всех Белых Программ. Поэтому нам приходится искать другую сомнительную идею. Ею оказывается предположение, что Beldiag [ N ] может быть закодировано как Белая Программа Блупа. Именно в этом - тонкое различие в приложении диагонального метода. [22]
В действительности, большинство специалистов считают, что для описания вычислений не может существовать более мощных языков, чем языки, эквивалентные Флупу. Эта гипотеза была сформулирована в 1930 - х годах двумя людьми, работавшими независимо друг от друга. Принимаем Тезис Ч - Т за истину, мы должны заключить, что Глуп - не более, чем миф, поскольку во Флупе нет никаких ограничений, которые можно было бы снять; его мощность невозможно усилить, сняв с него цепи, как мы это сделали с Блупом. [23]