Вопросы, касающиеся проблемы остановки, которая заключается в том, чтобы решить, останавливается ли данная программа на заданном входе.
Я не понимаю, почему проблема остановки так часто используется, чтобы исключить возможность определения, останавливается ли программа. Википедия [статья] [1] правильно объясняет, что детерминированная машина с конечной памятью либо остановит, либо повторит предыдущее состояние. Вы можете...
Мы знаем, что проблема остановки (на машинах Тьюринга) неразрешима для машин Тьюринга. Проводятся ли некоторые исследования того, насколько хорошо человеческий разум может справиться с этой проблемой, возможно, с помощью машин Тьюринга или компьютеров общего назначения? Примечание : Очевидно, что в...
Алан Тьюринг предложил модель для машины (Turing Machine, TM), которая вычисляет (числа, функции и т. Д.), И доказал теорему Остановки . ТМ - это абстрактное понятие машины (или двигателя, если хотите). Теорема Остановки - результат невозможности. Двигатель Карно (CE) - это абстрактное понятие...
Я понимаю доказательство неразрешимости проблемы остановки (приведенное, например, в учебнике Пападимитриу), основанное на диагонализации. Хотя доказательство является убедительным (я понимаю каждый его шаг), оно не является для меня интуитивным в том смысле, что я не понимаю, как кто-то может его...
Википедия, а также другие источники, которые я обнаружил в списке voidтипа C как тип единицы, а не пустой тип. Мне кажется, что это сбивает с толку, так как мне кажется, что оно voidлучше подходит под определение пустого / нижнего типа voidНасколько я могу судить, ценности не обитают . Функция с...
Проблема с остановкой утверждает, что нет алгоритма, который бы определял, останавливается ли данная программа. Как следствие, должны быть программы, о которых мы не можем сказать, прекращаются они или нет. Каковы самые простые (самые маленькие) известные примеры таких...
Довольно просто понять, почему проблема остановки неразрешима для нечистых программ (т. Е. Программ, в которых ввод / вывод и / или состояния зависят от состояния машины); но интуитивно кажется, что остановка чистой программы на идеальном компьютере может быть решена, например, статическим...
Я смотрел « Пять этапов принятия конструктивной математики » Андрея Бауэра, и он говорит, что существует два вида доказательств от противного (или две вещи, которые математики называют доказательством от противного): Предположим, что является ложным ... бла-бла-бла, противоречие. Следовательно,...
Как черные дыры в информатике. Мы можем только знать, что они существуют, но когда у нас есть один из них, мы никогда не узнаем, что это один из
Этот вопрос был перенесен из теоретического обмена стеков информатики, потому что на него можно ответить в обмене стеков информатики. Мигрировал 7 лет назад . «Алан Тьюринг доказал в 1936 году, что общий алгоритм для решения проблемы остановки для всех возможных пар ввода программы не может...
Машина Тьюринга, которая возвращается в ранее обнаруженное состояние со своей головкой чтения / записи в той же ячейке той же самой ленты, будет зациклена. Такая машина не останавливается. Может ли кто-нибудь привести пример никогда не останавливавшейся машины, которая не...
Недавно я услышал интересную аналогию, которая гласит, что доказательство Тьюринга неразрешимости проблемы остановки очень похоже на парадокс Рассела. Поэтому мне стало интересно: математикам в конечном итоге удалось согласовать теорию множеств, перейдя от наивной формулировки поля Кантора к более...
Возможно ли для среды выполнения обнаружить бесконечные циклы и впоследствии остановить связанный процесс, или реализация такой логики будет эквивалентна решению проблемы остановки? Для целей этого вопроса я определяю «бесконечный цикл», чтобы обозначить последовательность инструкций и связанных...
Из моего понимания доказательства того, что проблема остановки не вычислима, эта проблема не вычислима, потому что если у нас есть программа P (x), которая вычисляет, останавливается ли программа x или нет, мы получаем парадокс, когда передаем P в качестве входных данных для тот же P, имеющий: P...
Основное определение машины Тьюринга (ТМ), по крайней мере, в моем собственном справочнике (Hopcroft + Ullman 1979), является детерминированным. Следовательно, мое собственное понимание проблемы остановки главным образом относится к детерминированной ТМ, хотя я знаю, что это может быть рассмотрено...
Существует ли машина Тьюринга, которая останавливается на всех входах, но это свойство не доказуемо по какой-то причине? Мне интересно, если этот вопрос был изучен. Обратите внимание, что «недоказуемое» может означать «ограниченную» систему доказательств (которая в слабом смысле думает, что ответ...
Существуют релятивистские пространства-времени (например, пространства-времени МГ; см. Хогарт, 1994), где мировая линия бесконечной длительности может содержаться в прошлом конечного наблюдателя. Это означает, что обычный наблюдатель может иметь доступ к бесконечному количеству вычислительных...
У меня проблема: Покажите, что существует действительное число, для которого не существует ни одной программы, которая работает бесконечно долго и записывает десятичные цифры этого числа. Я полагаю, что это можно решить, сведя его к проблеме остановки, но я понятия не имею, как это сделать. Буду...
Я читал в Википедии и некоторых других текстах, которые Проблема остановки [...] разрешима для линейных ограниченных автоматов (LBA) [и] детерминированных машин с конечной памятью. Но ранее было написано, что проблема остановки - неразрешимая проблема, и поэтому TM не может ее решить! Так как LBA...
Я читал ответ на недавний вопрос, и мне в голову пришла странная эфемерная мысль. Мои просьбы об этом могут предать либо то, что мои теоретические отбросы серьезно отсутствуют (в основном это правда), либо что мне еще слишком рано читать этот сайт. Теперь с отказом от ответственности ... Это хорошо...