Описание тега decidable

Вопросы с тегом
Разрешаемые языки - это языки, в которых проблема того, принадлежит ли данное слово ему или нет, является разрешимой. Проблема принятия решения, то есть вопрос с ответом да / нет, называется разрешимой, если существует алгоритм (машина Тьюринга), который может и будет возвращать логическое значение true или false (вместо бесконечного цикла).
1 ответ

Учитывая кодировку конкретной машины Тьюринга, можно ли решить, остановится ли она на конкретном входе?

Скажем, у меня есть универсальная машина Тьюринга, кодирующая конкретную машину Тьюринга T. Также скажите, что у меня есть кодировка конкретного ввода s. Вопрос о том, останавливается ли T на s, разрешим? Можно ли использовать симуляцию бега T на s,…
28 июл '17 в 01:55
1 ответ

Реализуйте перечислитель, используя машину Тьюринга - избыточные отпечатки

По следующему алгоритму: мы реализуем перечислитель, используя машину Тьюринга, и предполагается, что перечислитель выводит язык, принятый машиной Тьюринга. Принятые слова из Σ* печатаются несколько раз (на каждой итерации ранее напечатанные слова б…
17 мар '18 в 17:15
1 ответ

Разрешается ли использование CFG с использованием нулевого языка?

Если у меня есть контекстно-свободная грамматика G такая, что язык G ноль, можно ли решать G? Я знаю, что ответ - да, но мне трудно доказать это. Моя первая мысль состоит в том, чтобы сказать, что есть только одно состояние, q1, которое является нач…
22 мар '11 в 05:33
4 ответа

Почему OWL Full неразрешима?

Я все время думал о том, почему OWL Full неразрешима, но я не нашел простого для понимания примера, который заставил бы меня понять его. Я нашел утверждения, которые объясняют, что это происходит из-за "Завершения Entailment", и это также связано с …
14 окт '17 в 02:47
2 ответа

Почему знать, нужен ли какой-то кусок памяти, неразрешимо?

Я перечитывал урок по Javascript для Mozilla и пролистал эту информацию. В языки высокого уровня встроено программное обеспечение, называемое "сборщик мусора", задачей которого является отслеживание выделения и использования памяти, чтобы определить…
24 дек '15 в 13:02
3 ответа

Связь между NP-трудными и неразрешимыми проблемами

Я немного запутался в связи между неразрешимыми проблемами и трудными проблемами NP. Являются ли трудные проблемы NP подмножеством неразрешимых проблем, или они одинаковы и равны, или они не сопоставимы? Для меня я спорил со своими друзьями, что нер…
08 май '12 в 07:05
1 ответ

Этот язык регулярный или нет?

У меня есть язык {4^(w⋅g)34^(g)|w,g∈NAT} над алфавитом {0,1}. Мне нужно выяснить, является ли этот язык узнаваемым, разрешимым, контекстно-зависимым, регулярным или ни одного из них. Как мне поступить так или узнать? Спасибо
30 июл '14 в 10:18
1 ответ

Доказательство разрешимости подмножества в Агде

Предположим, у меня есть это определение Подмножество в Агде Subset : ∀ {α} → Set α → {ℓ : Level} → Set (α ⊔ suc ℓ) Subset A {ℓ} = A → Set ℓ и у меня есть набор data Q : Set where a : Q b : Q Можно ли доказать, что все подмножество q разрешимо и поч…
09 дек '15 в 16:00
2 ответа

Логика первого порядка на практике, как бороться с неразрешимостью?

Я очень новичок в этих вещах. Надеюсь, это не очень наивный вопрос. Я пробовал следующую формулу в Прологе: A ⇒ B и учитывая, что B истинно, я оцениваю A, и он говорит ЛОЖЬ. Мой вопрос почему ЛОЖЬ? (почему не ИСТИНА?) Учитывая текущую информацию, мы…
09 авг '14 в 05:53
1 ответ

L = {T | T - машина Тьюринга, которая распознает {00, 01}} Доказательство L неразрешимо

L = { | T - машина Тьюринга, которая распознает {00, 01}} Докажи, что L неразрешима. У меня действительно есть трудности, даже понимание сокращения, чтобы использовать здесь. Я не прошу бесплатный обед, просто толчок в правильном направлении.
05 дек '12 в 01:34
2 ответа

Является ли язык {⟨A⟩∣A NFA и L(A)={0,1}∗} разрешима? неразрешима?

Как можно доказать / опровергнуть язык {⟩∣A⟩∣A - это NFA, а L(A)={0,1}∗} является / не может быть решено? Сначала я предположил, что, поскольку это был NFA, это было бы решаемо, но так как нет входной строки для симуляции, это меняет вещи? Если так,…
02 мар '18 в 23:59
1 ответ

Прямая редукция, машина Тьюринга и DFA

Я читал, и я пытаюсь понять сокращение, когда речь заходит об истинной машине. Вот как я это понимаю: это означает, что это превращает проблему А в проблему С. Но я не совсем уверен, как она полностью работает. давайте посмотрим на пример: Учитывая …
15 июн '15 в 11:06
0 ответов

Колмогоровская сложность не вычислима с помощью редукций

Может кто-нибудь, пожалуйста, дайте мне доказательство неразрешимости K-сложности с использованием сокращений. например: PCP (2) <= PCP(3) Я могу доказать, что PCP(3) неразрешима путем сокращения до PCP(2) (путем отображения каждого экземпляра). Я н…
26 апр '15 в 04:27
1 ответ

Является ли C++ рекурсивно перечислимым языком?

Я знаю, что C++ не разрешим. Но это рекурсивно перечислимо? Давайте определим набор допустимых программ на C++ как любую четко определенную программу в соответствии с текущими стандартами C++. Можно ли построить компилятор, который всегда может опре…
15 мар '14 в 05:13
1 ответ

Насколько произвольным является представление машины Тьюринга?

Я работаю над соответствующей проблемой разрешимости / распознаваемости, и для ее решения мне нужно уточнить кодирование / представление машины Тьюринга. Я знаю, что машина Тьюринга формально определяется как 7-кортеж. Если у меня есть машина Тьюрин…
27 окт '10 в 19:41
1 ответ

Докажите, является ли этот язык разрешимым или неразрешимым

Поэтому я просматриваю свои заметки по этой проблеме, и я не могу понять, как эта проблема работает. Скажем, у нас есть M, и M принимает входные данные, которые заставляют его посещать каждое состояние без остановки. Я убедил себя, что эта проблема …
24 апр '16 в 23:14
1 ответ

Рекурсивно разрешимый язык, принятие бесконечного языка

Поэтому я понимаю, что рекурсивно-разрешимые языки - это языки, на которых мы можем построить машину Тьюринга так, чтобы с учетом входных данных этого языка машина Тьюринга всегда принимала и останавливала, либо отклоняла и останавливала. Что меня с…
17 авг '17 в 07:25
1 ответ

Формулы ЭПР с равенством и неравенством

Я кодирую множества как отношения, а операции над множествами - как универсально выраженные значения. У меня есть оператор выбора для наборов, который создает новые наборы путем выбора элементов, удовлетворяющих унарному предикату p (например, v<4, …
10 май '13 в 22:54
1 ответ

Докажите, что конкретный язык не является полуразрешимым

Я должен доказать, что язык L = {: |L(M)| <= 2016} НЕ является полуразрешимым. Теперь я подумал сделать это так: Возьмем случайный алфавит E. Теперь в E. есть бесконечное количество слов. Мы можем только заключить, что | L (M) | <= 2016, передавая к…
28 май '17 в 14:01
1 ответ

Имеет ли значение порядок предэкспонирования во фрагменте ЭПР?

Эффективно пропозициональный (ЭПР) фрагмент логики первого порядка часто определяется как набор предэквантовых формул вида ∃X.∀Y.Φ(X,Y), где X а также Y являются (возможно, пустыми) последовательностями переменных. Есть ли порядок количественного оп…
12 сен '17 в 23:38