Cтраница 4
Обратное ( что гораздо труднее) тоже верно. Из ( с) теперь следует, что ограниченная проблема соответствия над алфавитом A Q а, р при 90 неразрешима. Кодируя A J а, р двухбуквенным алфавитом ( см. следствие 6.1.2), мы получаем неразрешимость ограниченной проблемы соответствия ( а значит, и общей проблемы соответствия) над любым алфавитом, содержащим более одной буквы. [46]
Внимательно рассматривая нормальные алгоритмы, мы видим, что они вполне соответствуют нашему пониманию алгоритма, но имеют очень частный характер. Большинство алгоритмов, встречающихся на практике, не являются нормальными алгоритмами. Но, безусловно, нормальные алгоритмы описаны с полной математической строгостью и точностью. Они вполне пригодны для тех целей, для которых были разработаны, а именно - для целей обоснования математики и исследования неразрешимости проблем. [47]
В своем настоящем виде эта книга является переработкой моей более ранней книги Основы теории функций вещественной переменной, вышедшей небольшим тиражом в 1941 году в издании Ленинградского университета и в скором времени полностью разошедшейся. Мысль о переиздании этой, более ранней, книги возникла уже довольно давно и отчасти была осуществлена издательством Радянська школа, выпустившим расширенный украинский перевод книги. Этот перевод, выполненный доцентом Киевского университета С. И. Зуховицким, помимо разного рода мелких добавлений, содержал три новых главы, отсутствовавших раньше и посвященных точечным множествам в многомерных пространствах и функциям нескольких переменных. В настоящее издание, кроме этих добавлений, включен довольно обширный новый материал: начала функционального анализа ( в том объеме, который требуется последней университетской программой), теория полунепрерывных функций, неразрешимость проблемы измерения, подробное изложение вопроса о предельном переходе под знаком интеграла и другое. [48]
В первом разделе данной работы вводится параллельная схема программы и определяются некоторые ее свойства, исследуемые в дальнейшем. Во втором разделе даются необходимые и достаточные условия однозначности схем некоторого определенного подкласса. В третьем разделе приводятся некоторые технические результаты, относящиеся к префиксам вычислительных процессов. В четвертом разделе исследуется класс так называемых счетчиковых схем и даются алгоритмы распознавания таких свойств этих схем как однозначность, ограниченность, свобода, замкнутость. Эти результаты получены посредством сведения данных проблем к некоторым разрешимым проблемам векторной алгебры. Установлена также неразрешимость проблемы эквивалентности в некотором подклассе схем. Этот результат, как и аналогичный результат работы [7] о неразрешимости, существенно использует память, состоящую более чем из одной ячейки. В то же время при монолитной памяти, как это имеет место для схем Янова, проблема эквивалентности разрешима. В пятом разделе, посредством сужения класса счетчиковых схем, определяется понятие параллельной операторной схемы. Параллельные операторные схемы можно рассматривать как обобщение последовательных операторных схем, приспособленное для представления параллельных вычислений. Для этих схем проблема эквивалентности оказывается разрешимой. [49]
В диалогах О государстве и О законах он дает определения, получившие в дальнейшем широкую известность. В диалоге О законах говорится, что закон есть заложенный в природе высший разум, велящий нам совершать то, что совершать следует, и запрещающий противоположное. Именно эти общие определения делают, однако, внутренне проблематичной всю концепцию. Ибо разум диктует человеку, как мы видели, в одних случаях защищать самого себя, в других - крепить сообщество и хранить порядок справедливого солидарного взаимообмена в нем, в-третьих же - достойно вести себя по отношению к людям как таковым, а не гражданам определенного сообщества. Нельзя сказать, что сам Цицерон не видел этой проблемы. Но удовлетворительным образом она решена быть не могла. В современные издания его диалогов, тексты которых сохранились далеко не полностью, включены фрагменты позднейших, христианских авторов, в частности, Лактанция ( Божественные установления) и Августина, цитировавших Цицерона и споривших с его идеями. Для Лактанция очевидна неразрешимость проблемы в перспективе общественного устройства Рима, далеко еще не ставшего миром, Рима активных завоеваний. Римский народ, говорит Лактанций, своей завоевательной политикой дает понять, насколько польза расходится со справедливостью ( Inst. VI, 9, 2 - 4); у Цицерона защищается на деле не естественная справедливость ( которую диктует высший разум), а гражданская ( фактически значимые правовые ( Нормы) ( Inst. Аналогичным образом и Августин ( О граде Божьем, XIX, 21) говорит, что никогда не существовало того идеального Римского государства, которое рисует Цицерон в своем диалоге. [50]