Мне нужно доказать, разрешима ли L или нет:
L={‹M> | M является TM, и объединение L(M) и H_TM находится в RE}
( H_TM={‹M,w> | M — TM, который останавливается на w} )
разрешимые языки (вычислительные модели)
comment
Этот вопрос, вероятно, следует задать на cs.stackexchange.com.
- person harold schedule 29.05.2016
Ответы (1)
Я полагаю, что ‹...> — это номер ТМ в гёделизации. L(M) — это набор слов, а H_TM — это набор пар. Таким образом, их союз не пересекается, ни один элемент не появится в обоих. Следовательно, объединение перечислимо тогда и только тогда, когда перечислимы две его части. H_TM перечислима, и поэтому перечислимость зависит только от L(M). Но быть языком ТМ означает быть разрешимым, а значит, явно перечислимым. Следовательно, условие на M в определении L всегда истинно, и, таким образом, L есть множество всех описаний TM, которое является регулярным и явно разрешимым.
person
Peter Leupold
schedule
30.05.2016
Я предполагаю, что мои обозначения были неясны: ‹M› в основном encoidng для машины Тьюринга, поэтому, когда другая машина получает такие входные данные, она может их имитировать. Более того, H_TM - это проблема остановки, которая, как вы сказали, разрешима, и я не знаю почему..
- person ChikChak; 31.05.2016
Извини! Я написал разрешимый, когда на самом деле имел в виду RE в определении L. Конечно, проблема остановки неразрешима, но она перечислима, я поправил свой ответ.
- person Peter Leupold; 31.05.2016
Я немного запутался: означает ли обозначение L(M), что M решает L? Или, может быть, оно распознает только L?
- person ChikChak; 31.05.2016
Это ваше обозначение ;-) Решение и признание означают одно и то же. Распознавание означает, что для любого ввода ТМ может решить, принадлежит он языку или нет.
- person Peter Leupold; 31.05.2016
