Класс вычислимости, который я беру, объясняет несколько языков, которые находятся в RE - REC (рекурсивно перечисляемые, но не рекурсивные, т.е. решаемые безостановочной машиной Тьюринга). Сначала показано, как один из них (L_d, язык машин Тьюринга, которые не принимают собственную кодировку) не находится в RE, и доказывается, что его дополнение находится в RE — REC. Затем он доказывает, что его можно свести к универсальному языку (L_u, набору всех двоичных кодов машин Тьюринга, объединенных строкой, которую он принимает). Затем он продолжает показывать, насколько L_u является RE-Hard, затем сводит его к L_PCP (проблема корреспонденции сообщений), а затем сводит это к контекстно-свободной грамматической неоднозначности. Есть ли проблемы, которые есть в RE, но не в RE-Hard? Потому что до сих пор для каждой проблемы, которую наш профессор объяснил в RE-REC, он доказал, что они сводятся друг к другу.
Существуют ли какие-либо рекурсивно перечисляемые проблемы, которые не являются RE-сложными?
Ответы (2)
Упомянутая вами проблема (с пояснением Питера Леупольда, которая должна быть интегрирована в вопрос) известна как проблема поста. Ответ положительный: в частности, все так называемые «простые» множества являются RE-множествами, которые не являются много-одно-полными.
Простой набор - это RE-набор, комплементарность которого является «иммунной». Иммунный набор — это набор, не содержащий бесконечного RE-набора. Этого достаточно, чтобы доказать, что простое множество не может быть полным, так как дополнение полного множества продуктивно, а любое продуктивное множество содержит бесконечное РЕ-подмножество, порожденное его собственной производственной функцией.
Известно несколько простых множеств. Мой любимый пример — множество неслучайных чисел в соответствии с колмогоровской сложностью, то есть множество всех чисел, которые можно более компактно выразить в виде индекса порождающей его программы (на входе 0). Доказательство того, что такое множество простое, несложно и может быть найдено в любом хорошем учебнике по вычислимости.
Ответ на ваш вопрос — да, потому что даже конечные языки — это RE. Но они ни в коем случае не жесткие в том смысле, в каком вы имеете в виду.
Может быть, ваш вопрос действительно таков: «Существуют ли какие-либо рекурсивно перечисляемые проблемы, которые не являются RE-сложными, но не рекурсивными?» Здесь ответ зависит от вашего понятия редукции. Вероятно, ваш профессор использует многократные сокращения; тогда ответ, вероятно, ДА (я не совсем уверен). Для более слабых редукций ответ НЕТ.
