Мне интересно, все ли бесконечные языки неразрешимы?Все бесконечные языки неразрешимы?
Они должны быть правы, так как ТМ, пытающаяся решить бесконечный язык, будет просто зацикливаться навсегда, что делает ее рекунизатором, а не решателем.
Спасибо, ребята.
Нет, существует множество бесконечных языков, которые разрешимы. Одним из тривиальных примеров является язык {n € N | a^n}, то есть язык слов, который содержит только букву «a». Этот язык может быть сопоставлен регулярным выражением a*. поэтому он является обычным языком и, следовательно, разрешимым.
Как sepp2k указывает, a* - это обычный язык, поэтому разрешимый.
Все конечные языки являются регулярными. Некоторые бесконечные языки являются регулярными. Только бесконечные языки могут быть неразрешимыми.
Чтобы быть неразрешимым, на языке, на котором TM терпит неудачу, должны быть отдельные строки. В самом деле, должно быть бесконечно много таких строк (в противном случае плохо управляемые могут обрабатываться логикой конкретного случая).
Для того чтобы язык был бесконечным, необходимо, но недостаточно для неразрешимости.