Разрешимость префиксного языка

9

В середине срока был вариант следующего вопроса:

Для разрешимого определить Показать, что не обязательно разрешимый.прив ( L ) = { х | у  й  рентгеновские у LLPref ( L )

Pref(L)={xy s.t. xyL}
Pref(L)

Но если я выберу то я думаю, что также , поэтому разрешима. Также дает тот же результат. И так как должен быть разрешимым, я не могу выбрать проблему остановки или что-то подобное .. Pref ( L ) Σ L=ΣPref(L)ΣLL=L

  1. Как я могу найти такой, что не разрешима?Pref ( L )LPref(L)
  2. Какие условия на сделают разрешимым, а какие - неразрешимыми?Pref ( L )LPref(L)
Ран Г.
источник

Ответы:

9

Обратите внимание, что с помощью экзистенциального квантификатора перед разрешимым языком мы можем получить любой новый язык, то есть каждый язык выражается как

{xΣyΣ x,yV}

где разрешимый язык. К ним относятся неразрешимые языки: .Т М = { е , х | е  кодирует машин Тьюринга , которая принимает  й }V

ATM={e,x e encodes a Turing machine which accepts x}

Единственная разница здесь в том, что здесь мы должны разделить и сами. Стандартный трюк заключается в использовании нового символа для разделения двух частей (предположим, что разделитель принадлежит ). Поэтому любой язык, включая неразрешимые, можно выразить в этом формате.у уxyy

Что касается второго вопроса, то нет общего алгоритмического способа проверить, являются ли префиксы данного разрешимого языка неразрешимыми. Это следует из теоремы Райс.

Кава
источник
Вы можете явно дать который создает ? A T MVATM
Ран Г.
2
Пусть быть строкой , предназначенной для представления останавливая принимая вычисление по , будет проверять , если является допускающим вычисление по . M e x V y M e xyMexVyMex
Каве
Это хорошее решение!
Ран Г.
3

Мета-знание: вы хотите найти неразрешимый язык, который, тем не менее, обладает некоторыми вычислительными свойствами. Произвольный неразрешимый язык, вероятно, не приведет вас слишком далеко. Но полуразрешимый ...


Более сильный намек: что такое полуразрешимый язык? Это означает, что мы можем перечислить слова: это некоторый набор слов такой, что существует целое число такое, чтонun

u=f(n)

Посмотрите на это уравнение немного, имея в виду разрешимость и префиксы.


Говоря интуитивно, предположим, что у вас есть и вы хотите проверить, находится ли он в . Вы не , чем проверка , , и т. Д., Где - буквы алфавита. Это частично рекурсивная функция, которая проверяет членство в . Конечно, мы знали, что уже был; нам нужно показать, что иногда нет альтернативного метода. Давайте возьмем некоторый набор который является ре и не рекурсивным, и пусть будет перечислением (xPref(L)xaxbxaaa,b,Pref(L)Pref(L)SNfSS=f(x)xN ).

Предположим, что алфавит содержит три символа , и (если у вас есть только два символа , закодируйте как , как и как ). Если , пусть будет записанным в базе 2 с использованием символов и без начального .01:{,}01:nNn¯n010

Пусть . Говоря простым языком, мы берем элементы и добавляем их в индекс перечисления. явно разрешима (проверьте, что существует одно что две последовательности цифр не содержат начального , и что первая последовательность цифр записывает изображение на числа, которое пишется второй). Однако решение о том, является ли какой-то префиксом , равносильно решению, находится ли в , что невозможно сделать, не зная поскольку не является рекурсивным по предположению. Формально,S L : 0 f ˉ y L y S x S P r e f ( L ) P r e f ( L ) { 0 , 1 } : = S :L={y¯:x¯y=f(x)}SL:0fy¯LySxSPref(L) не разрешима, потому что не разрешима.Pref(L){0,1}:=S:

Жиль "ТАК - перестань быть злым"
источник