Описание тега halting-problem
Проблема остановки - известная проблема теоретической информатики. Учитывая, что в качестве входных данных используется описание программы (обычно машины Тьюринга) и входные данные для этой программы, проблема остановки заключается в том, чтобы решить, завершается ли эта программа на этом входе.
2
ответа
Программы agda обязательно заканчиваются?
В нескольких местах было указано, что все программы agda завершаются. Однако я могу построить такую функцию: stall : ∀ n → ℕ stall 0 = 0 stall x = stall x Подсветка синтаксиса, кажется, не нравится, но нет ошибок компиляции. Вычисление нормальной …
12 авг '13 в 03:02
1
ответ
Прекращение замены букв
Дано: Строка символа S длина l содержащий только символы из 'a' в 'z' Набор из ordered правила замещения R (в виде X->Y) где x, y отдельные буквы от 'a' to 'z' (например, 'a' -> ' e' может быть действительным правилом, но 'ce'->'abc' никогд…
06 июн '16 в 17:10
2
ответа
Python - длительная остановка при расчете числа палиндрома
Я пытаюсь найти наибольшее число палиндромов, составленное из двух трехзначных чисел с моим кодом. он хорошо работает для 2-значных и 3-значных чисел, но когда я пробую его с 4-значными числами, он больше не работает. Нет вывода или "Процесс заверше…
02 ноя '18 в 02:32
1
ответ
Почему мы должны использовать отрицание в Доказательстве остановки Тьюринга?
Например, допустим, у меня есть машина Тьюринга H, которая сообщает нам, остановится ли программа и ввод. Допустим, мы называем H на себя. Он должен дать ответ, поэтому, если он печатает "не останавливается", то не технически ли он останавливает печ…
01 фев '15 в 07:24
1
ответ
Универсальная машина Тьюринга U должна определить, останавливается ли M(x)
Итак, у нас есть универсальная машина Тьюринга U, которая должна определить, остановится ли машина Тьюринга M с входом x. Решение должно быть представлено в псевдокоде. Может ли кто-нибудь помочь мне немного, кто я должен решить это?
08 ноя '13 в 14:58
1
ответ
"try" может решить, когда программа остановится
У меня есть эта функция: isUndefined :: () -> Bool isUndefined x = case unsafePerformIO $ (try (return $! x) :: IO (Either SomeException ())) of Left _ -> True Right _ -> False затем: isUndefined () = False isUndefined undefined = True Реше…
20 июн '15 в 21:24
26
ответов
Что именно является проблемой остановки?
Всякий раз, когда люди спрашивают о проблеме остановки, связанной с программированием, люди отвечают: "Если вы просто добавите один цикл, вы получите программу остановки и, следовательно, не сможете автоматизировать задачу ". Имеет смысл. Если ваша …
10 июл '09 в 18:18
0
ответов
Можно ли создать функцию остановки без ссылки / сборки / генерации решателя на входе?
Вопрос в том, можно ли решить проблему остановки, если решатель не собирается, не эмулируется, не генерируется, не воссоздается, а не помещает ваш выбор здесь / не используется ли он в какой-либо форме внутри анализируемой функции? Есть очень похожи…
29 май '15 в 08:44
1
ответ
Доказательство того, что проблема остановки является NP-трудной?
(Я прошу прощения, если это неправильный сайт для этого вопроса, но, учитывая, что здесь много вопросов теории CS "не так уж сложно для CS", я думаю, что это может подойти. Пожалуйста не стесняйтесь перемещать это, если это неуместно.) В этом ответе…
09 авг '11 в 02:06
8
ответов
Все ли регулярные выражения останавливаются?
Есть ли регулярное выражение, которое для некоторой входной строки будет искать совпадение всегда?
06 авг '09 в 20:28
2
ответа
Прекратится ли этот алгоритм?
Будет ли когда-нибудь завершаться этот алгоритм (псевдокод) с разными значениями в коллекции? while (curElement != average(allElements)) { curElement = average(allElements); nextElement(); } Обратите внимание, что я предполагаю, что мы начнем заново…
10 фев '12 в 09:45
1
ответ
Является ли mfix для "Возможно, невозможно быть нетривиальным"?
Поскольку Nothing >>= f = Nothing для каждого fследующее тривиальное определение подходит для mfix: mfix _ = Nothing Но это не имеет практического применения, поэтому у нас есть следующее нетитальное определение: mfix f = let a = f (unJust a) …
13 июл '18 в 11:29
3
ответа
Действие контроллера вызывается дважды
Я заметил, что действие "index" моего контроллера вызывается дважды. Акция имеет следующую структуру: def index if params[:tags].nil? # [fork #1] just return the whole collection of model @items = Item.all else # [fork #2] filter items by tags @item…
14 окт '10 в 05:29
1
ответ
Может ли машина Тьюринга решить, завершена ли формальная модель вычислений?
То есть может ли машина Тьюринга взять формальную систему S в качестве входных данных и решить, является ли S полной по Тьюрингу? Я думаю, что это неразрешимая проблема, я прав? Если это неразрешимо, почему мы (как люди) можем решить полноту Тьюринг…
19 апр '13 в 17:41
9
ответов
Обнаружение бесконечного цикла в программе brainfuck
Я написал простой интерпретатор Brainfuck на языке сценариев MATLAB. Он подается случайным BF программ для выполнения (как часть проекта генетического алгоритма). Проблема, с которой я сталкиваюсь, заключается в том, что программа оказывается бескон…
15 дек '08 в 05:49
2
ответа
Понимание значения CheckHalt(X,X) в доказательстве теоремы Дискретной математики Сусаны Эпп с приложениями
У меня есть очень простое знакомство с алгоритмами. Я выпускник по математике. Я читал проблему остановки в книге "Дискретная математика с приложениями" Сюзанны Эпп. Имеет следующую теорему: Теорема: не существует компьютерного алгоритма, который пр…
03 авг '17 в 17:11
4
ответа
Почему не может быть программа, которая проверяет другую программу
Я пытаюсь найти логическое объяснение, почему не может быть программа, которая проверяет другие программы. Я помню, что мы учились на курсе вычислений, но теперь я просто не могу найти решение, и мне нужно объяснить это кому-то на моей работе. Спаси…
28 апр '10 в 21:56
1
ответ
Немного другая версия проблемы с остановкой
Я застрял с вопросом и хотел бы получить небольшое руководство для решения. Мне нужно доказать, что следующая проблема неразрешима:Ввод - программа Проблема - больше ли возможных входов, для которых программа останавливается, больше, чем тех, для ко…
19 сен '17 в 17:12
4
ответа
Проблема остановки машины Тьюринга
У меня есть вопрос о машинах Тьюринга и проблеме остановки. Предположим, что у нас есть Atm = {(M,w), где M - машина Тьюринга, а w - вход} иHALTtm = {(M,w) где M - машина Тьюринга останавливается с вводом w} Я хочу доказать, что HALTtm <=m Atm Я про…
24 мар '10 в 18:42
1
ответ
Можно ли определить, доступен ли массив памяти вне границ в программе Brainfuck?
Я написал собственный BF Interpreter в Assembly, и теперь я пишу BF Compiler на Java, который компилируется в ассемблерный код. Я хотел реализовать небольшую приятную функцию, которая обнаружила, что массив ячеек памяти вышел за пределы. Традиционно…
17 ноя '16 в 17:03