Проблема - остановка
Cтраница 3
Вспоминая, что множество пар ( р, х) программа р завершает работу на входе х является одним из т-пол-ных перечислимых множеств, можно сказать, что 0 вы числимые функции вычисляются машинами, которым придан специальный оракул, решающий проблему остановки: этому оракулу посылают программу и вход, и он отвечает, останавливается ли эта программа на этом входе или не останавливается. При этом посылаемая на экспертизу программа - самая обычная, без обращений к оракулу. [31]
Однако проблема остановки трещины связана с некоторой неопределенностью статического подхода к ее решению. Тем не менее предложено рассматривать остановку трещины как явление, обратное ее инициированию относительно шкалы времени. Эта концепция говорит о том, что все накопленные знания, касающиеся механизма инициирования трещины, основываются на решении проблемы остановки трещины, и фактически большая часть работ посвящена этому вопросу. Накопленный опыт подтверждает это, хотя неясно, идентичны ли значения К и Gc для остановки и инициирования трещины. [32]
Однако эта ситуация не настолько безнадежна, как это может показаться на первый взгляд. С практической точки зрения решение проблемы остановки трещин имеет наиболее важное значение для тех материалов, которые не обнаруживают заметной пластичности во время быстрого распространения трещины. Случаи быстрого, катастрофического разрушения происходят в условиях, когда пластическая зона по фронту трещины практически мала. Поэтому использование методов линейной механики хрупкого разрушения ( с учетом динамических эффектов) может стать эффективным при решении проблемы остановки трещин. [33]
Неразрешимые проблемы разрешения впервые были обнаружены при исследовании основ понятия алгоритма. Как правило, базисной проблемой разрешения является проблема остановки для машины Тьюринга. В ней ставится вопрос, существует ли алгоритм, который для любого слова в ленточном алфавите некоторой машины Тьюринга решает, остановится или нет эта машина, если она начнет работу в положении, когда читающая головка стоит у первого слева символа рассматриваемого слова, которое считается отпечатанным на ленте. [34]
К ним относится проблема распознавания самоприменимости машин Тьюринга, проблема остановки алгоритма, проблема распознавания принадлежности числа данному нерекурсивному множеству натуральных чисел. [35]
Сопротивление их хрупкому разрушению может быть настолько высоким, что проблема остановки трещин может стать второстепенной, поскольку инициирования трещины может не произойти. Эффективными оказались композитные металлы, содержащие как высокопрочную компоненту, несущую нагрузку, так и вязкую компоненту, которая обеспечивает остановку трещин. Создание в конструкциях специальных отверстий и полостей для проверки влияния второй компоненты композитного металла на его сопротивление хрупкому разрушению, а также применение нагретых зон позволяют выявить дополнительные эксплуатационные возможности материала в специфических условиях. [36]
 |
Иерархия Хомского. [37] |
Это обстоятельство приводит к неразрешимости проблемы распознавания принадлежности данного выражения заданному языку. В действительности приведенные сейчас рассуждения служат неким обоснованием неразрешимости так называемой проблемы остановки: не всегда можно предусмотреть, остановится данная машина или нет. [38]
Но, полагая х т, мы видим, что абак с номером т, запущенный с т камешками в регистре RI и всеми остальными пустыми регистрами, останавливается тогда и только тогда, когда он не делает этого. Значит, такого абака не существует, а потому никакой абак не вычисляет функцию h и проблема остановки абаков неразрешима. [39]
Например, невозможно в полной общности решить, зацикливается ли программа Р или еще, эквивалентна ли Р программе Q. Если бы такое решение было возможно, то ( в противоречии с предыдущим) решалась бы и проблема остановки. [40]
На этом основании делается вывод, что исследуемая проблема также алгоритмически неразрешима. Если бы существовало решение задачи ПАСС с произвольной функцией Л разметки, то данное сведение позволило бы решить проблему остановки машины Тьюринга, которая, как известно, является алгоритмически неразрешимой. [41]
Читатель может заметить определенное сходство между рассуждениями, устанавливающими, вопреки недоказуемости, истинность Р & ( &), и парадоксом Рассела. Помимо этого, наблюдается сходство и с доказательством Тьюринга о невозможности существования машины Тьюринга, которая могла бы решить проблему остановки. Эти сходства не случайны. Между этими тремя событиями имеется прочная историческая нить. [42]
Он построил около полудюжины простых хорновских дизъюнктов, представляющих необходимый механизм УМТ, и доказал затем, что любая вычислимая по Тьюрингу функция может быть вычислена с помощью резолюции, исходя из этих дизъюнктов в ответ на соответствующие целевые утверждения. Кроме того, хорошо известный факт о том, что не существует никакого алгоритма, позволяющего решить, закончится или нет произвольное тьюрингово вычисление ( проблема остановки), преобразуется тогда в эквивалентный факт: не существует никакого алгоритма, позволяющего решить, дает ли произвольная программа на хорновских дизъюнктах конечное успешное резолютивное вычисление. Это в свою очередь просто вариант того факта, что общезначимость произвольных предложений в логике первого порядка не является полностью разрешимой. [43]
То есть мы покажем, что процедуру Е вместе с некоторыми другими, существование которых неоспоримо, можно было бы применить для решения того частного случая проблемы остановки, неразрешимость которого была доказана ранее; следовательно, предположение о существовании Е приводит к противоречию. [44]
Розенберг в [7] и независимо от него авторы установили ряд результатов по неразрешимости, включая результат для автоматов с двумя головками. Оказалось, что для моделирования этих автоматов в известном смысле могут быть использованы схемы с двумя ячейками, и мы воспользуемся: этим обстоятельством, чтобы установить неразрешимость разного вида проблем остановки и проблем эквивалентности для схем программ. [45]
Страницы: 1 2 3 4