Cтраница 2
Теорему 1.3 часто интерпретируют как утверждение о не разрешимости проблемы остановки ( для МНР-программ), в ка тором говорится о том, что не существует никакого эффектиЯ ного общего метода установить, остановится ли некотора конкретная программа, запущенная после введения в нее не которого конкретного набора начальных данных. [16]
Применение только депрессаторов без дополнительных мероприятий не позволяет решить проблему остановки скважин в зимнее время. [17]
Для машин Минского и, следовательно, счет-чиковых автоматов неразрешима проблема остановки ( останавливается ли машина, начав работать с заданными начальными значениями счетчиков. [18]
Заметим также, что одной из актуальных проблем прочности являтся проблема остановки трещины. Решение указанной инженерной проблемы приводит к необходимости знания путей распространения разрушения. Последняя задача, достаточно трудная для однородной среды, существенно усложняется при наличии включений и иных неоднородностей. [19]
Тьюринг вводит абстрактную модель цифровой вычислительной машины и доказывает неразрешимость проблемы остановки и проблемы разрешимости для логики первого порядка. [20]
Тьюринга сводится к про блеме конечности автономного поведения, а поскольку проблем остановки алгоритмически неразрешима, то неразрешима и про1 блема конечности. [21]
Однако, очевидно и то, что более глубокое проникновение в проблему остановки трещины возможно, если понят механизм инициирования и развития трещины. Следовательно, оправдана подробное рассмотрение основных факторов, влияющих на инициирование и, распространение трещины. [22]
Вопрос о соотношении между результатами о неразрешимости, например теоремой Геделя или проблемой остановки для машин Тьюринга, и возможностями машин решать задачи был достаточно запутан как в литературе, так и в умах многих исследователей. Никем не было показано, что мозг имеет преимущество перед машинами, так как он может использовать теорему Геделя для доказательства справедливости некоторых недоказуемых высказываний. Однако нет причин, мешающих машине воспроизвести эти же самые доводы, пользуясь вышеупомянутой якобы непротиворечивой метасистемой; в этом нет ничего такого, что выходило бы за рамки обычных стереотипных доказательств. [23]
В добавление к этим следствиям, касающимся транслируе-мости, техника языков значений имеет также следствия, касающиеся разрешимости проблемы остановки для данного класса схем. Это вытекает из того, что проблема пустоты разрешима для контекстно-свободных языков, но неразрешима для рекурсивно-пере-числимых языков ( Хопкрофт и Ульман [2], стр. [24]
Еще одна родственная проблема, подобным же образом оказывающаяся неразрешимой, если только тьюрингово понятие вычислимости универсально, - это проблема остановки из упр. Тьюринга ( неважно, в стандартной или в какой-либо иной заключительной конфигурации), если ее запустить в начальном ее состоянии считывающей самую левую клетку в сплошном массиве единиц на ленте с пустыми символами во всех остальных клетках. Замечательно, что независимо от того, принимается тезис Черча или нет, следующая функция Л, вычислимость которой в интуитивном смысле эквивалентна разрешимости проблемы остановки, оказывается, как можно доказать, невычислимой по Тьюрингу: Л ( тп, п) 2 или 1 в соответствии с тем, остановится в конце концов или нет машина Тьюринга с номером т, если ее запустить в начальном состоянии считывающей самую левую единицу в сплошном блоке из п единиц на ленте с пустыми символами во всех остальных клетках. Таким образом, если тезис Черча верен, то проблема остановки неразрешима. [25]
Мы доказываем неразрешимость логики первого порядка от противного: мы докажем, что если бы соответствующий тест существовал, то проблема остановки оказалась бы разрешимой, т.е. существовала бы эффективная процедура для ответа на вопрос, останавливаются ли в конце концов машины Тьюринга, если их запускать в состоянии gi на самой левой единице в некотором массиве единиц на ленте с пустыми символами в остальных клетках. [26]
Чтобы подробно разобраться в этом вопросе, предположим, что у нас есть некий алгоритм, который иногда позволяет решить проблему остановки. [27]
Хотя исследования по определению скорости распространения трещины были основаны на этом или другом равнозначном энергетическом критерии, его использование для решения проблемы остановки трещины было минимальным. Следовательно, наибольшая часть современной литературы об остановке трещины базируется на статических или квазистатических схемах, хотя ниже рассмотрены и динамические явления. Более того, применение статических методов анализа предложено по меньшей мере половиной исследователей, которые изучали роль динамических эффектов. Ирвин и Уэллс ( 1965 г.) предложили рассматривать остановку трещины как простое реверсирование по шкале времени возможных начальных явлений плоской деформации. Основываясь на этой концепции, можно представить схематично критерий остановки трещин, как и критерий их неустойчивого распространения. [28]
Используя так называемый диагональный метод, Тьюринг построил доказательство того, что не существует алгоритма, который может успешно рассмотреть все частные случаи проблемы остановки. [29]
Таким образом, если мы можем отыскать k, то мы знаем, как построить вычислительную процедуру, для которой алгоритм не дает решения проблемы остановки, но нам ответ известен. Необходимо тщательно изучить конструкцию Я ( п; т) и Т ( т) и понять, как в точности действует 1 Т ( п) х Я ( п; п) в качестве машины Тьюринга. Возможно, мысль о том, что мы умнее каких-то алгоритмов, принесет нам некоторое удовлетворение. [30]