Является ли язык l= {, m принимает конечное количество слов}, разрешимо?

Question

- $ l={ |L (m) \ \ finite \} $ dravidable?М тм.

Я думаю, что его относительны простые доказывают с теоремой риса.Но я заинтересован в решении, который не использует теорему риса.

Это моя попытка: Пусть f () быть функцией, которая работает следующим образом:

1. Беги с m
2. Если m принимает построить TM Mwhich accepts only the word w and return M
3. Если m rejects построить TM Mwhich accepts everything. Return M

Так, если M находится в $ a_ {tm}={ | m \ \ \ w \} $ Мы знаем, что f () находится в Л. Если M не в a, то мы знаем, что f () принимает каждое слово и поэтому бесконечности.Так f () не в л.

Это правильное сокращение сопоставления?

Answer 1

Определенная вами функция не является уменьшением вообще - это может даже останавливаться!

Проблема работает $ m $ на $ W $ : Можете ли вы быть уверены, что класс Span="Математический контейнер"> $ m $ не будет застрять в бесконечной петле на $ W $ ? Вы не можете.

Вы можете определить правильное уменьшение следующим образом: (на входе $ $ )

Создать машину $ m_ {m, w} $ , который делает следующий алгоритм и возврат в: (на входе $ s $ )

1. emulation $ m $ на $ W $ для $ | s | $ Шаги. Если $ m $ остановился в то время, отклоните $ S $ . В противном случае примите $ s $ .

Я оставлю его для того, чтобы вы доказать, что это правильное сокращение из $ h_ {Tm} $ на $ l $ (это хорошее упражнение!)