Есть машины Тьюринга, которые принимают обычные языки, и есть машины Тьюринга, которые принимают языки, которые не являются обычными.Является ли язык регулярным или нет, является семантическим свойством - связано с тем, что в языке, а не с формой машины Тьюринга - поэтому, по теореме Райс, нельзя решить, является ли L (M) регулярным.
Другой способ увидеть это - предположить, что это разрешимо, а затем получить противоречие.Например, если бы это была разрешимая проблема, вы могли бы решить, принимает ли произвольный TM какие-либо строки;то есть является ли L (M) пустым языком.Для этого просто создайте новый TM, заменив halt_accept новым TM, принимающим известный нерегулярный язык.Язык этого ТМ будет нерегулярным - поэтому наш решатель будет halt_reject - тогда и только тогда, когда целевой ТМ сделал это для halt_accept на некотором входе (в этом случае он будет принимать строки, начинающиеся с этого префикса и заканчивающиеся любой строкой на нерегулярном языке),Чтобы эта конструкция действительно работала, новая TM, вероятно, должна иметь дополнительный символ во входном алфавите, чтобы разделить первую и вторую части;в противном случае различие между префиксом и нерегулярным суффиксом может быть запутано.
Пример: пусть M будет входной TM над алфавитом A, а M 'будет любой TM, которая принимает палиндромы над B. Тогда наш новый TM будет законченалфавит (объединение B union {c}), где c не является элементом ни A, ни B. Этот новый TM будет иметь то же начальное состояние, что и M ', и будет использовать те же состояния halt_accept и halt_reject, что и M'.Любой переход в M, который перешел в состояние halt_accept M, вместо этого переместится в начальное состояние M 'и переместит головку ленты к символу непосредственно справа от c, тогда как любой переход в M, который перешел в состояние halt_reject в Mвместо этого перейдет в состояние halt_reject в M '.Наш ленточный ввод в эту новую TM будет выглядеть как xcy, где x - строка над A, а y - строка над B. Предположим, что M принимает x.Тогда M перешел бы в состояние halt_accept M. Поэтому наша новая TM вошла бы в начальное состояние M 'и начала смотреть на y.Новая TM будет принимать на любом палиндроме y над B нерегулярный язык;и язык строк xcy, заканчивающийся любым палиндромом над B, не может быть обычным языком, если только такие строки не принимаются.Поскольку мы знаем, что над алфавитом B существуют палиндромы, единственный способ, которым язык мог бы быть пустым, - это если бы не было строк x над A, что заставило бы M ввести halt_accept;то есть L (M) должен быть пустым.Следовательно:
- если наша новая ТМ считается регулярной, мы знаем, что М пусто
- если наша новая ТМ решена не регулярной, мы знаем, что М непусто
Следовательно, мы можем решить, является ли М пустым, если мы можем решить, принимают ли ТМ обычные языки или нет.Это предполагает, что вы принимаете, что «L (M) пусто», во-первых, неразрешимо;в противном случае вы могли бы подумать, что другая конструкция для языка, который вы уже знаете, неразрешима.