Может ли распознаваемый по Тьюрингу язык быть разрешимым, если можно перечислить его строки неубывающей длины?
Я думаю, это не потому, что вы можете уйти в бесконечность, и это сделает ее неразрешимой, верно?
Распознаваемый по Тьюрингу язык разрешим или нет?
comment
Пожалуйста, переместите это на cstheory.stackexchange.com
- person C-Otto schedule 08.05.2017
comment
Перемещено cstheory .stackexchange.com/questions/38168/
- person PTN schedule 08.05.2017
comment
Узнаваемый язык всегда МОЖЕТ быть разрешимым. Возможно, ваш вопрос: разрешим ли каждый перечислимый язык, который можно перечислить в неубывающем порядке? Тогда да.
- person Peter Leupold schedule 09.05.2017
comment
@ C-Otto: это не исследовательский уровень и не относится к cstheory.
- person user2357112 supports Monica schedule 11.05.2017
Ответы (1)
Вопрос о поиске элемента в бесконечном потоке S упорядоченных элементов: очень естественный алгоритмический вопрос.
Эта проблема действительно решаема, хотя и несколько хитроумным образом. Нужно рассуждать падежами. Если элементы в S имеют верхнюю границу, то S конечно и, следовательно, разрешимо, поскольку разрешимо каждое конечное множество. С другой стороны, если S не имеет границ, оно содержит элементы больше любого числа. Итак, если вы ищете w, достаточно перечислить, пока не найдете элемент, больший или равный w (который должен существовать), а затем сравнить его с w.
Однако доказательство не является конструктивным, так как вы не можете решить, является ли р. множество конечно или нет. Это означает, что вы знаете (в классическом смысле), что должна существовать некая программа, определяющая S, но у вас нет возможности вывести ее из кода, перечисляющего S. ситуация :)
person
Andrea Asperti
schedule
11.05.2017
Я бы не стал утверждать, что у вас нет способа вывести решающий фактор. Предполагая, что у вас есть счетчик, вы можете создать двухленточный НП, который записывает условие поиска на второй ленте, перечисляет на первой и чередует перечисление со сравнением лент. Существует конструктивное доказательство того, что двухленточные ТМ эквивалентны одноленточным ТМ. Учитывая TM, который перечисляет L в порядке неубывания длины, вы можете, таким образом, построить одноленточный решающий модуль. Единственная неконструктивная часть предполагает, что такой счетчик существует, но это считается само собой разумеющимся в качестве гипотезы.
- person Patrick87; 11.05.2017
@ Патрик, я не слежу за тобой. Вы не можете быть уверены, что найдете элемент, больший, чем тот, который вы ищете (если вы не знаете, что множество бесконечно, но вы этого не знаете), поэтому вы не знаете, когда остановиться.
- person Andrea Asperti; 11.05.2017
@AndreaAsperti: Разве вы не могли вначале просто догадаться, является ли данный набор конечным? Для этого предположения вы также угадываете верхнюю границу. Конечные множества можно было бы определить таким образом, а бесконечные - путем предположения, что они бесконечны, и следуя подходу перечисления. Это должно дать (недетерминированный) решающий фактор, начиная только с алгоритма перечисления.
- person Peter Leupold; 12.05.2017
@PerterLeupold Нет: как я уже сказал, неразрешимо, если р.э. множество конечно.
- person Andrea Asperti; 12.05.2017
