Я знаю, что неразрешимо определить, может ли набор плиток укладывать плитку в результате того, что Бергер использовал плитки Ванга . Мой вопрос состоит в том, известно ли также, что неразрешимо определить, может ли один данный фрагмент мозаики составить плоскость - моноэдральный фрагмент . Если это...
Хорошо известно, что проблема эквивалентности неразрешима для общих контекстно-свободных языков. Тем не менее, все доказательства этого факта, о которых я знаю, похоже, включают в себя некоторые неоднозначные контекстно-свободные грамматики. По этой причине я хотел бы спросить, известно ли,...
Проблема остановки для машин Тьюринга, возможно, является каноническим неразрешимым множеством. Тем не менее, мы доказываем, что существует алгоритм, решающий почти все его экземпляры. Таким образом, проблема остановки является одной из растущих коллекций тех, кто демонстрирует феномен «черной...
Ответ: не известно. Задаваемые вопросы являются естественными, открытыми и, по-видимому, сложными; сейчас вопрос вики сообщества. обзор Вопрос состоит в том, чтобы разделить языки, принадлежащие к классу сложности PPP - вместе с машинами Тьюринга (TM), которые принимают эти языки, - на два...
Известно, что многие логические проблемы (например, проблемы выполнимости нескольких модальных логик) не разрешимы. Есть также много неразрешимых проблем в теории алгоритмов, например, в комбинаторной оптимизации. Но на практике эвристики и приближенные алгоритмы хорошо работают для практических...
Какова простейшая вычислительная модель, для которой проблема пустоты неразрешима? Проблема пустотности для вычислительной модели (например, автомат конечного состояния, автомат с переменным нажатием, квантовый автомат с ограниченной ошибкой со счетчиком, детерминированный LBA и т. Д.) Состоит в...
Игра «Назови наибольшее число» просит двух игроков тайно записать число, и победителем становится тот, кто записал большее число. Игра обычно позволяет игрокам записывать функции, оцененные в определенный момент, поэтому 222222222^{2^{2^{2}}} также было бы приемлемо записать. Значение функции Busy...
Есть проблемы, которые разрешимы, есть проблемы, которые неразрешимы, есть полурешимость и т. Д. В этом случае мне интересно, может ли проблема быть мета неразрешимой. Это означает (по крайней мере, в моей голове), что мы не можем сказать, разрешимо это или нет. Возможно, известно, что разрешимость...