Cтраница 3
Методом Коэна была установлена неразрешимость в ZF гипотезы Суслина. [31]
В частности, установлена неразрешимость большого числа естественных алгоритмич. Результаты этого типа ( совершенно отсутствующие в курсах традиционного анализа) имеют очевидную теоре-тич. Теоремы о невозможности алгоритмов часто сопровождаются в К. Сопоставление таких результатов позволяет во многих случаях получить отчетливое представление о том, как можно корректно ставить ту или иную алгоритмич. [32]
В большинстве случаев доказательства неразрешимости основываются на диагональном методе, как, например, в следующем важном примере. [33]
Таким образом, кривая неразрешимости Рг Pr ( Re) имеет две ветви. [34]
Теперь, после доказательства неразрешимости арифметики с операциями сложения и умножения, совершенно уместной выглядит теорема Пресбургера о разрешимости арифметики сложения ( гл. [35]
Покажем прежде всего, как неразрешимость монадической логики следует из теоремы 25.1. Мы опишем эффективный способ построения по каждому монадическому предложению S бескванторной) предложения S, выполнимого тогда и только тогда, когда выполнимо S. [36]
Дэвис приводит полное доказательство Матиясевича неразрешимости десятой проблемы Гильберта. [37]
Вопрос о соотношении между результатами о неразрешимости, например теоремой Геделя или проблемой остановки для машин Тьюринга, и возможностями машин решать задачи был достаточно запутан как в литературе, так и в умах многих исследователей. Никем не было показано, что мозг имеет преимущество перед машинами, так как он может использовать теорему Геделя для доказательства справедливости некоторых недоказуемых высказываний. Однако нет причин, мешающих машине воспроизвести эти же самые доводы, пользуясь вышеупомянутой якобы непротиворечивой метасистемой; в этом нет ничего такого, что выходило бы за рамки обычных стереотипных доказательств. [38]
Хотя медленная сходимость еще не означает неразрешимость той или иной задачи, она часто свидетельствует о том, что такую задачу нельзя решить с разумной затратой времени и средств. Поэтому иногда для повышения скорости сходимости приходится поступаться другими рабочими характеристиками классификаторов. [39]
Не значит ли это, что неразрешимость связана с тем, что исследуемая проблема является слишком массовой. Нет, не значит, потому что, вводя ограничения на алгоритмы или на слова, или и на то и другое, можно все множество одиночных проблем, входящих в состав массовой проблемы, оставить бесконечным ( счетным), имеющим то же кардинальное число, что и исходное множество, но тем не менее получить разрешимую проблему. В некоторых случаях множество одиночных проблем неразрешимой проблемы оказывается подмножеством аналогичного множества одиночных проблем, образующих разрешимую проблему. [40]
Теорема 15.2 ( теорема Черча о неразрешимости) Теория L неразрешима. [41]
Мы изложим здесь некоторые результаты о неразрешимости, показывающие, что многие из условий в теоремах предыдущего раздела не могут быть заметно ослаблены. Так как класс уравнений, рассматриваемых в этом разделе, включает уравнения, для которых этапы I и III процедуры доказательства существования, описанной в гл, 11, были обоснованы ранее, то неразрешимость задачи Дирихле в этих случаях связана с отсутствием граничной оценки градиента. В действительности несуществование такой оценки для этих уравнений может быть показано непосредственно с помощью техники, аналогичной той, которая используется далее. [42]
Однако результаты Черча и Тьюринга о неразрешимости логики предикатов первого порядка в какой-то степени оттеснили работы Эрбрана на задний план. Интерес к ним возрос лишь в 60 - е годы, когда Гилмор реализовал эрбрановскую процедуру вывода на компьютере. Действительно, если нет процедуры для проверки противоречивости ( общезначимости) формул логики предикатов первого порядка, то самое большее, что можно сделать - это проверить противоречивость ( общезначимость) формулы, если она на самом деле таковой и является. [43]
В настоящее время получены достаточные условия локальной неразрешимости уравнений с частными производными. [44]
Доказательство этого факта близко к доказательству неразрешимости уравнений степени 5 в радикалах ( Руффини - Абель - Галуа): оно выводится из неразрешимости некоторой группы. В отличие от обычной теории Галуа, речь идет здесь не о конечной группе, а о неразрешимой группе Ли. Наука, занимающаяся этими вопросами, называется дифференциальной алгеброй. [45]