Post machine, self-reference and paradoxes.pdf Моя цель заключается в том, чтобы изменить установку по отношению к противоречию и к доказательству противоречивости... ЛюДвиг Витгенштейн (RFM, III, 82) Запрет на предложения (или их последовательности), которые содержат в себе признаки самореференции (self-reference), является, пожалуй, самым популярным из существующих традиционных средств борьбы с семантическими парадоксами (ср. с этим: [2. P. 32; 3. P. 15; 4. P. 8-9; 5. С. 105; 6. С. 11-12]. Появление такого запрета обычно связывают с именем Бертрана Рассела, и прежде всего с его знаменитой теорией типов, в которой любые самореферентные предложения рассматриваются как примеры бессмысленных (meaningless) выражений [7. С. 110-112, 114, 129-130, 135-141; 8. С. 22-26, 64-65]17. Альфред Тарский позднее распространил действие этого запрета на область всей теоретической семантики, показав проблематичность использования любых семантически замкнутых языков из-за таящейся в них угрозы появления пара-доксов18. Предложениям просто строго воспрещалось высказываться о самих себе19 [9. P. 402-403; 10. P. 158-165, 186-188, 265-267; 12. С. 99-100; ср. с этим также: 13. P. 65; 14. P. 44; 15. P. 219]. И хотя иногда казалось, что они нарушают этот запрет (например, как это пытается делать предложение «Это предложение ложно»), расселовские иерархии логических типов и тарскиан-ские иерархии метаязыков обычно без труда устраняли последствия неудобств, возникающих из-за несовершенства грамматических конструкций подобного рода предложений. Многие логики, однако, остались недовольны иерархическим подходом Рассела - Тарского, и прежде всего самим запретом на самореферентные предложения (или их последовательности) (например, см.: [16. P. 69-71; 17. P. 394; 18. P. 528; 19. P. 89; 20. P. 298; 21. С. 476-480]). Помимо очевидных логических выгод, такой запрет сулил также и довольно серьёзные семантические издержки. С одной стороны, он был очевидным образом слишком широк, поскольку не позволял использовать такие невинные с виду саморефе-рентные предложения, как «Это предложение на русском языке»20; с другой -слишком узок, ибо попустительствовал таким последовательностям предложений, которые содержали в себе порочный регресс (вроде цепочки предложений «Следующее за мной предложение ложно. Следующее за мной предложение ложно. и т.д.») и могли при определенных обстоятельствах вести к появлению новых неожиданных парадоксов (например, см.: [22. P. 146; 23. P. 168]). Особые неприятности в этой связи причиняет так называемый «Бесконечный лжец» Стивена Ябло [24. P. 251-252]. Именно этот парадокс обычно рассматривается как наиболее веский и убедительный контраргумент против иерархического подхода Рассела - Тарского (ср.: [6. С. 19-21]). Предложенная американским логиком бесконечная последовательность предложений S1, S2, S3, Sn, каждое из которых сообщает, что все следующие за ним предложения не являются истинными, образует следующую парадоксальную конструкцию: S1: для всех k > 1, Sk не является истинным S2: для всех k > 2, Sk не является истинным S3: для всех k > 3, Sk не является истинным Sn: для всех k > n, Sk не является истинным. Если некоторое произвольное предложение Sn такой бесконечной последовательности являлось бы истинным, все следующие за ним предложения Sn+1, Sn+2, ., Sn+m не были бы таковыми. Но предложение Sn+1, подобно предложению Sn, тогда также оказалось бы истинным, поскольку оно само фактически утверждает, что все следующие за ним предложения Sn+2, ., Sn+m не являются таковыми. Значит, подобно всем следующим за ним предложениям Sn+1, Sn+2, ., Sn+m некоторое произвольное предложение Sn такой бесконечной последовательности истинным не является. Но оно должно быть таковым, поскольку само фактически утверждает, что все следующие за ним предложения Sn+1, Sn+2, ., Sn+m не являются истинными. Налицо очевидный парадокс! «Бесконечный лжец», кажется, не содержит в себе явных признаков са-мореференции (ср. с этим: [3. P. 29; 22. P. 139; 25. P. 206]). Каждое из предложений этой бесконечной последовательности говорит не о себе самом, но всегда только обо всех следующих за собой предложениях. В этом отношении логическая конструкция «Бесконечного лжеца» очевидным образом изоморфна иерархической структуре как таковой, что и делает этот парадокс столь убийственно сильным критическим контраргументом против иерархического подхода Рассела - Тарского. Однако является ли «Бесконечный лжец» в действительности реальной угрозой для него? Чтобы ответить на этот вопрос, нам потребуется иная стратегия семантического анализа, радикальным образом отличная от той, что обычно используется для демонстрации парадоксальности «Бесконечного лжеца». Прежняя не способна нас удовлетворить, поскольку она готова мириться с присутствием процедур рекурсивного определения истинностного значения некоторых отдельных предложений, составляющих подобную бесконечную последовательность. Например, истинностное значение предложения Sn+1, казалось бы, определяемое с помощью предложения Sn, тем не менее находится в скрытой рекурсивной зависимости от истинностного значения всех следующих за ним предложений Sn+2, ., Sn+m. Разделяющий же базовые принципы иерархического подхода Рассела - Тарского семантический анализ «Бесконечного лжеца», не должен содержать в себе возможности для рекурсивных определений; и для этих целей нам как нельзя лучше подходит модифицированный вычислительный алгоритм так называемой «машины Поста». Такая простейшая абстрактная машина, как известно, состоит из бесконечной ленты, разделенной на отдельные ячейки, и оперирующего над ней механизма нанесения / удаления меток [26. P. 103]. Если представить предложения «Бесконечного лжеца» в качестве отдельных команд для программы действий машины Поста (табл. 1), некоторое произвольное предложение Sn «для всех k > n, Sk не является истинным» этой бесконечной последовательности на языке такой абстрактной машины означало бы, что ее механизм нанесения / удаления меток, расположенный над определенной ячейкой (n), должен был бы последовательно сдвигаться вправо по ленте, нанося или удаляя метки в каждой из ячеек (k), в зависимости от того, оказалась ли помеченной сама эта ячейка (n) или нет. Таблица 1. Программа машины Поста «Бесконечный лжец» Номер ячейки в ленте Номер команды в программе Описание команды (п) : Sn Все k(k>n) не являются истинными (п + 1 ): Sn+1 Все k(k>n+i) не являются истинными (п + 2) : Все k(k>n+2) не являются истинными _ S. Все ... не являются истинными Например, если бы некоторая произвольная стартовая ячейка (n) бесконечной ленты машины Поста вдруг оказалась пуста21, механизм нанесения / удаления меток последовательно сдвигался бы вправо по ленте, нанося метки в каждой из ячеек (k), и напротив, если бы она оказалась помеченной22, механизм нанесения / удаления меток также последовательно сдвигался бы вправо по ленте, но при этом удалял бы метки в каждой из ячеек (k). Но что произойдет, если мы заставим машину Поста выполнять алгоритм, формирующий бесконечную последовательность предложений Ябло, в качестве своеобразной программы? Столкнется ли она с невозможностью ее выполнить? Иными словами, будет ли выполнимым для машины Поста инфинитный детерминированный процесс, репрезентируемый предложениями «Бесконечного лжеца», или нет? Невыполнимость (или парадоксальность) для машины Поста системы команд из бесконечной последовательности предложений Ябло подразумевала бы ее нерезультативную остановку, или ситуацию, в которой механизм нанесения / удаления меток, сдвинувшись вправо на необходимую ячейку, пытался бы выполнить невозможное действие, например нанести метку в том случае, когда она уже есть, или же удалить ее, если метки там нет. Однако наблюдение за видимой23 (неоперабельной) частью ленты после выполнения соответствующей команды из бесконечной последовательности предложений Ябло очевидным образом свидетельствует, что алгоритм программы «Бесконечный лжец» при любом исходном состоянии ленты и стартовой позиции механизма маркировки ячеек оказывается вполне выполнимым для машины Поста. Пустая стартовая ячейка (n) не приводит машину Поста к нерезультативной остановке (табл. 2)24. Таблица 2. Состояния машины Поста при выполнении программы «Бесконечный лжец» (стартовая ячейка является пустой) Состояние машины Поста Номер ячейки ленты (n) (n + 1) (n + 2) (n + 3) (n + 4) (n + •••) Номер команд программы Sn - - - - - Sn+\ - Sn+2 - - - - Sn+3 - - Sn+4 - - s„+... - - - Не происходит нерезультативной остановки машины Поста и в том случае, когда стартовая ячейка (n) оказывается помеченной (табл. 3). Таблица 3. Состояния машины Поста при выполнении программы «Бесконечный лжец» (стартовая ячейка имеет метку) Состояние машины Поста Номер ячейки ленты (n) (n + 1) (n + 2) (n + 3) (n + 4) (n + •••) Номер команд программы Sn - Sn+1 - - - - - Sn+2 - - Sn+3 - - - - Sn+4 - - - Sn+... - - - Отсутствие нерезультативной остановки машины Поста при выполнении команд «Бесконечного лжеца» объяснимо тем, что вычислительный алгоритм такой программы имеет вид монотонной иерархической структуры, в которой каждое произвольное предложение Sn бесконечной последовательности фиксирует значение только строго следующих за собой предложений Sn+1, Sn+2, ..., Sn+m, что полностью исключает любые формы рекурсивных определений. При выполнении команд «Бесконечного лжеца» машина Поста всегда сдвигается только вправо по ленте и никогда влево, а стало быть, несмотря на бесконечные повторные манипуляции над одними и теми же ячейками, она никогда не сталкивается с требуемыми для нерезультативной остановки ситуациями. Но что случится, если мы, например, посадим очевидным образом страдающего от избыточной референции25 «Бесконечного лжеца» на «диету», нарушив тем самым монотонность иерархической структуры предложений внутри самой этой последовательности? Как поведет себя машина Поста, например, если мы представим ей для выполнения такую бесконечную последовательность предложений, где любое произвольное предложение Sn будет ссылаться не на все расположенное непосредственно за ним множество, а только на два ближайших предложения Sn+1 и Sn+2 (табл. 4)? Останется ли такой своеобразный «Диетический бесконечный лжец» выполнимым для нее алгоритмом? Таблица 4. Программа машины Поста «Диетический бесконечный лжец» Номер ячейки в ленте Номер команды в программе Описание команды (п) : Sn (п + 1) и (п + 2) не являются истинными, (п + 1) (п + 1) : Sn+1 (п + 2) и (п + 3) не являются истинными, (п + 2) (п + 2) : Sn+2 (п + 3) и (п + 4) не являются истинными, (п + 3) (...) : S. (...) и (...) не являются истинными, (.+1) Исчезновение монотонности внутри иерархической структуры бесконечной последовательности предложений Ябло почти мгновенно приводит к нерезультативной остановке машины Поста при любом исходном состоянии ленты и стартовой позиции механизма маркировки ячеек. Пустая стартовая ячейка (n) «Диетического бесконечного лжеца» приводит машину Поста к нерезультативной остановке в ячейке (n + 3) (табл. 5)26. Таблица 5. Состояния машины Поста при выполнении программы «Диетический бесконечный лжец» (стартовая ячейка имеет метку) Состояние машины Поста Номер ячейки ленты (п) (п + 1) (п + 2) (п +3) (п + 4) (п +.) Номер команды программы s„ - - S„+1 - ! Если стартовая ячейка (n) «Диетического бесконечного лжеца» оказывается помеченной, нерезультативная остановка машины Поста также происходит в ячейке (n + 3) (табл. 6). Таблица 6. Состояния машины Поста при выполнении программы «Диетический бесконечный лжец» (стартовая ячейка имеет метку) Состояние машины Поста Номер ячейки ленты (п) (п + 1) (п + 2) (п + 3) (п + 4) (п +-..) Номер команды s„ программы S„+1 - - ! - - Различие в поведении, которое демонстрирует машина Поста при выполнении программ «Бесконечного лжеца» и «Диетического бесконечного лжеца», служит очевидным свидетельством эффективности базовых принципов иерархического подхода Рассела - Тарского в борьбе против семантических парадоксов. Бесконечная последовательность предложений Ябло может рассматриваться в качестве оригинального семантического парадокса, если и только если мы готовы принимать ее в качестве одномоментно заданного инфинитного множества элементов, значение которых фиксируется с помощью рекурсивных определений27. Парадоксальность такой последовательности исчезает, как только мы начинаем трактовать ее в качестве аналога монотонной иерархической структуры, элементы которой пошагово конструируются согласно принципам не содержащего рекурсивные определения вычислительного алгоритма. Строгое следование монотонной иерархии команд программы «Бесконечного лжеца» не ведет к нерезультативной остановке машины Поста. В полном соответствии с идеалами иерархического подхода Рассела - Тарского кажущаяся нам парадоксальной последовательность предложений «Бесконечного лжеца» оказывается выполнимым для машины Поста вычислительным алгоритмом.

Скачать электронную версию публикации