Cтраница 3
Как было замечено в главе 5, каждая конечно представленная группа реализуется в виде фундаментальной группы 4-мно-гообразия. Этот факт вместе с неразрешимостью проблемы изоморфизма был использован А. А. Марковым [15] для доказательства алгоритмической неразрешимости проблемы изоморфизма для 4-многообразий. Работа Маркова была последовательно обобщена Буном, Хакеном и Поенарю [37] на диффео-морфную, а также комбинаторную эквивалентность. В отличие от того, что возникает при работе с группами, в данном случае некоторое внимание должно быть обращено на описание многообразия, к которому применяются критерии проблемы разрешения. [31]
Среди математиков росло убеждение в принципиальной неразрешимости проблемы континуума. Лишь после того, как был найден способ сведения математич. Формальная неразрешимость понимается в смысле не существования формального вывода в системе Цермело - Френкеля ZF как для К. [32]
Результаты Геделя ( верные не только по отношению к арифметике, но и ко всякой системе, содержащей арифметику натуральных чисел как свою часть - такова, напр. Черч, пользуясь методами, аналогичными геделевым, доказал неразрешимость проблемы разрешения как для теорий, содержащих арифметику натуральных чисел, так и для исчисления предикатов), имели важнейшее филос. [33]
Этот тезис дает алгоритмическое толкование понятию частично рекурсивных функций. Практически понятие частично рекурсивных функций используют для доказательства алгоритмической разрешимости или неразрешимости проблем. Использование же частично рекурсивных функций для представления того или иного конкретного алгоритма практически нецелесообразно ввиду сложности такого процесса алгоритмизации. [34]
Вопрос о существовании такого предиката составляет проблему сводимости, эквивалентная формулировка которой была дана в подстрочном примечании на стр. Постом [1944] были построены специальные примеры предикатов вида ( Ey) R ( x, у), неразрешимость проблем разрешимости которых устанавливается не сведением к ним проблем разрешимости предиката ( Еу) 7 ( х, х, у), а искусственными методами. [35]
В этом смысле прав Лешек Кумор, справедливо заметивший, что ахиллесова пята человека скрыта в его голове. И в зависимости от того, насколько эта слабость проявляется у конкретного трейдера, он становится либо частью решения, либо причиной неразрешимости проблемы. [36]
Как известно, общим в постановке таких проблем является поиск ответа на вопрос, обладает ли исследуемый объект интересующим нас свойством, определяющим его принадлежность к множеству всех объектов, этим свойством обладающих. Известен ряд классических неразрешимых проблем. Так, неразрешимость проблемы остановки означает, что нельзя построить алгоритм, который устанавливал бы, остановится ли машина Тьюринга, начав работать над любым словом в заданном алфавите. Неразрешима и более частная проблема: остановится ли машина Тьюринга, работающая с пустой лентой, не содержащей никаких символов, кроме пустого. [37]
Долгое время оставался открытым естественный вопрос: являются ли неразрешимые А. Иначе говоря, существуют ли неразрешимые А. Они доказали неразрешимость проблемы равенства слов ( тождества) для полугрупп, к-рая была поставлена А. [38]
Понятие задачи в общем виде уточняется при помощи понятия массовой проблемы. Ясно поэтому что неразрешимость проблемы не дает оснований для агностич. Неразрешимость массовой проблемы означает невозможность найти соответств. Массовые проблемы чрезвычайно характерны и важны для логики и математики. Даже решение единичных проблем часто ценно именно благодаря тому, что одновременно дает общий метод для решения целого класса проблем; в то же время постановка массовой проблемы означает превращение нек-рого класса проблем в единичную проблему - проблему нахождения А. Ролью массовых проблем и определяется значение А. [39]
Предположим, что алгоритм а существует. Полученное противоречие и доказывает неразрешимость проблемы останова в исходном алфавите операторов. [40]
Поэтому, беря в качестве S4 - любое копредставлеине с неразрешимой проблемой равенства ( причем можно брать групповые копредставления. Тп имеет неразрешимую проблему равенства. Прямое доказательство этого результата для копредставления Т вместе с результатами С. И. Адяна [1966], связывающими моноидные копредставления S4 - с групповыми непредставлениями, дает доказательство неразрешимости проблемы равенства для групп. [41]
Давайте сразу усвоим, что проблема - ключевое понятие, с которым приходится иметь дело диссертанту. Ученый, или претендующий на это гордое звание, обязан уметь поставить научную проблему и либо найти и предложить пути ее решения, либо доказать неразрешимость проблемы. С точки зрения чистой науки отрицательный результат есть тоже научный результат, но право защищать диссертации, основанные на доказательстве неразрешимости поставленной проблемы, - дело избранных. [42]
Смерть никогда не наступает по вине души, но исключительно потому, что разрушается какая-нибудь из главных частей тела ( см. Страсти души, в кн.: Избр. Декарт строго разграничивал тело, управляемое физнч. Именно неразрешимость проблемы психофизич. [43]
Все это не дает, вообще говоря, конечного описания, так как при данном подходе в общем случае нельзя, определить, задает ли предложенное определение на самом деле многообразие. Эта проблема решается, например, в [37], где работают с так называемыми прямолинейными сим-плициальными комплексами, снабженными дополнительными структурами, превращающими их в комбинаторные п-многооб-разия, а также снабжающими их С - атласами, описывающимися алгебраическими уравнениями. Различные проблемы эквивалентности для некоторых классов представлений многообразий переводятся тогда при помощи фундаментальных групп на язык проблем эквивалентности для представлений групп. Алгоритмическая неразрешимость проблем эквивалентности для многообразий следует тогда из соответствующей неразрешимости теоретико-групповых проблем. [44]
Вначале мы вводим понятие счетности ( перечислимости, нумеруемости) и устанавливаем существование несчетных множеств Затем определяется понятие вычислимости посредством машин Тьюринга и доказывается, что проблема их остановки неразрешима. Мы вводим еще два понятия вычислимости и доказываем их эквивалентность вычислимости по Тьюрингу. Неразрешимость ( элементарной) логики первого порядка выводится непосредственно из неразрешимости проблемы остановки, без использования арифметичации Затем устанавливаются корректность и полнота некоторой системы логического вывода. Теорема Левенгейма-Сколема в редакции всякая интерпретация обладает элементарно эквивалентной подинтерпретацией со счетной областью устанавливается при доказательстве корректности и полноты. [45]