Привет!
Назрела пара вопросов, на которые пока не могу ответить:
1. Доказать или опровергнуть: Turing-recognizable язык может быть "занумерован" без повторений, то есть то есть одна и та же строка не пояляется на выходе дважды.
2. Доказать или опровергуть. Turing-recognizable язык замкнут относительно подмножества. Вроде бы не верно, а какой контр-пример?
09.09.03 22:42: Перенесено модератором из 'Прочее' — _MM_
Turing-recognizable -- это такое экзотическое название для разрешимого, что ли?
Видимо нет, поскольку в таком случае оба утверждения тривиальны.
