Я готовлюсь к выступлению, направленному на студентов по математике, и в рамках этого я рассматриваю возможность обсуждения концепции разрешимости. Я хочу привести пример проблемы, о которой мы пока не знаем, что она разрешима или неразрешима. Таких проблем много, но пока что ни одна из них не...
Если ограничить машины Тьюринга конечной лентой (т. Е. Использовать ограниченное пространство ), то проблема остановки решаема, в основном потому, что после ряда шагов (которые можно рассчитать из числа состояний Q , S и размер алфавита), конфигурация должна быть повторена.SSSQQQSSS Существуют ли...
Я знаю, что неразрешимо определить, может ли набор плиток укладывать плитку в результате того, что Бергер использовал плитки Ванга . Мой вопрос состоит в том, известно ли также, что неразрешимо определить, может ли один данный фрагмент мозаики составить плоскость - моноэдральный фрагмент . Если это...
Хорошо известно, что проблема эквивалентности неразрешима для общих контекстно-свободных языков. Тем не менее, все доказательства этого факта, о которых я знаю, похоже, включают в себя некоторые неоднозначные контекстно-свободные грамматики. По этой причине я хотел бы спросить, известно ли,...
Меня интересует следующая задача: заданы целочисленные матрицы A1,A2,…,AkA1,A2,…,AkA_1,A_2, \ldots, A_k решают, равно ли каждое бесконечное произведение этих матриц нулевой матрице. Это означает именно то, что вы думаете, что он делает: мы будем говорить, что множество матриц обладает тем...
Это известный результат, что вопрос Генерирует ли контекстно-свободная грамматика обычный язык? неразрешима. Однако он становится разрешимым в унарном алфавите просто потому, что в этом случае классы контекстно-свободных и регулярных языков совпадают. Мой вопрос состоит в том, чтобы знать, что...
Я знаю, что невозможно определить эквивалентность для нетипизированного лямбда-исчисления. Цитирование Барендрегта, Л. П. Лямбда-исчисление: его синтаксис и семантика. Северная Голландия, Амстердам (1984). :ββ\beta Если A и B являются непересекающимися непустыми множествами лямбда-членов, замкнутых...
Я пытаюсь решить конкретную проблему, и я подумал, что смогу решить ее, используя теорию автоматов. Мне интересно, какие модели автоматов имеют разрешимость за полиномиальное время? то есть если у вас есть машины вы можете проверить, эффективно ли . L ( M 1 ) ⊆ L ( M 2 )M1, M2M1,M2M_1, M_2Л ( М1) ⊆...
Проблема остановки для машин Тьюринга, возможно, является каноническим неразрешимым множеством. Тем не менее, мы доказываем, что существует алгоритм, решающий почти все его экземпляры. Таким образом, проблема остановки является одной из растущих коллекций тех, кто демонстрирует феномен «черной...
Ответ: не известно. Задаваемые вопросы являются естественными, открытыми и, по-видимому, сложными; сейчас вопрос вики сообщества. обзор Вопрос состоит в том, чтобы разделить языки, принадлежащие к классу сложности PPP - вместе с машинами Тьюринга (TM), которые принимают эти языки, - на два...
Известно, что многие логические проблемы (например, проблемы выполнимости нескольких модальных логик) не разрешимы. Есть также много неразрешимых проблем в теории алгоритмов, например, в комбинаторной оптимизации. Но на практике эвристики и приближенные алгоритмы хорошо работают для практических...
Каковы известные пределы разрешимости сравнения скорости роста функций из ? Я здесь думаю о разрешимости таких вопросов, как «Является ли x x ∼ 2 ⌊ x lg ( x + 2 ) ⌋ ?» или «Является ли 2 lg ∗ x ∈ O ( lg lg x ) ?».N→NN→N\mathbb{N} \to \mathbb{N}xx∼2⌊xlg(x+2)⌋xx∼2⌊xlg(x+2)⌋x^x \sim 2^{\lfloor x \lg...
Какова простейшая вычислительная модель, для которой проблема пустоты неразрешима? Проблема пустотности для вычислительной модели (например, автомат конечного состояния, автомат с переменным нажатием, квантовый автомат с ограниченной ошибкой со счетчиком, детерминированный LBA и т. Д.) Состоит в...
Система векторного сложения (VAS) - это конечный набор действий . - это набор разметок . В рабочем цикле является непустое слово маркировки й . Если такое слово существует , мы говорим , что является достижимым из .A ⊂ Z d A⊂ZdA \subset \mathbb{Z}^dN dNd\mathbb{N}^dm 0 m 1 … m nm0m1…mnm_0 m_1\dots...
Ответ: неизвестно Большое спасибо всем, кто помог уточнить этот вопрос и определения, связанные с ним. Определения этой вики послужили отправной точкой для более новой вики TCS: « Содержит ли P языки, существование которых не зависит от PA или ZFC? (Вики сообщества TCS) ». Более поздняя вики...
Игра «Назови наибольшее число» просит двух игроков тайно записать число, и победителем становится тот, кто записал большее число. Игра обычно позволяет игрокам записывать функции, оцененные в определенный момент, поэтому 222222222^{2^{2^{2}}} также было бы приемлемо записать. Значение функции Busy...
Рассмотрим произвольную контекстно-свободную грамматику гGG по алфавиту { 0 , 1 ,0¯¯¯,1¯¯¯}{0,1,0¯,1¯}\lbrace 0,1,\overline{0} ,\overline{1} \rbrace, К произведениям этой грамматики добавьте два фиксированных неконтекстно-свободных произведения.пPP: 0¯¯¯0 → ϵ0¯0→ϵ\overline{0} 0 \rightarrow \epsilon...
Есть проблемы, которые разрешимы, есть проблемы, которые неразрешимы, есть полурешимость и т. Д. В этом случае мне интересно, может ли проблема быть мета неразрешимой. Это означает (по крайней мере, в моей голове), что мы не можем сказать, разрешимо это или нет. Возможно, известно, что разрешимость...
Каждый ли распознаваемый по Тьюрингу неразрешимый язык имеет NP-полное подмножество? Этот вопрос можно рассматривать как более сильную версию того факта, что каждый бесконечный распознаваемый по Тьюрингу язык имеет бесконечное разрешимое...
Если у вас есть две функции, реализующие другой алгоритм сортировки, то можно ли по исходному коду сделать вывод, что они имеют одинаковые внешние свойства? Это означает, что у них обоих будет возможная несортированная последовательность в качестве входных данных и отсортированная...