Зафиксируем какой-то алфавит. Пусть $%p,q$% - программы (программа - последовательность символов алфавита, строящаяся по некоторым правилам, которые сейчас не важны). Каждая программа $%p$% определяет функцию $%[p]$% из множества слов алфавита в себя.

Пусть $%W_p$% - множество всех слов $%x$% таких, что $%[ p ] ( x ) $% определено. Такие множества называются рекурсивно перечислимыми. Докажите, что существует программа $%s$% такая что $%W_s=W_p \cup W_q$%. То есть докажите, что рекурсивно перечислимые множества замкнуты относительно объединений.

задан 16 Сен '19 4:36

изменен 16 Сен '19 4:51

Нужно параллельно запустить обе программы p, q, выполняя команды то одной из них, то другой. Когда одна из этих программ остановится, выдаём результат её вычислений.

Способ реализации ("перемешивание" команд) зависит от специфики используемого языка.

(16 Сен '19 9:27) falcao
10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×53

задан
16 Сен '19 4:36

показан
268 раз

обновлен
16 Сен '19 9:27

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru