теория вычислений — является ли C ++ рекурсивно перечислимым языком?
Я знаю, что C ++ не разрешим. Но это рекурсивно перечислимо?
Давайте определим набор допустимых программ на C ++ как любую четко определенную программу в соответствии с текущими стандартами C ++.
Можно ли построить компилятор, который всегда может определить действительные программы на C ++ за конечное время?
Или это ко-рекурсивно перечислимо?
Можно ли построить компилятор, который всегда может определить недействительным С ++ программы за конечное время?
Или нет?
Решение
Можно ли построить компилятор, который всегда может определить действительные программы на C ++ за конечное время?
Да. При наличии достаточного количества времени и ресурсов компилятор C ++ должен иметь возможность завершить компиляцию любой допустимой программы C ++. Рекурсивно перечислимый язык требует машины Тьюринга, которая всегда завершается и дает положительный ответ, когда строка находится в языке, и компилятор делает это по существу.
Можно ли построить компилятор, который всегда может идентифицировать недействительные программы на C ++ за конечное время?
Нет. Язык шаблонов C ++ завершен по Тьюрингу, поэтому вы можете написать в нем бесконечную рекурсию. Из-за проблемы остановки невозможно определить, будет ли программа когда-либо завершать компиляцию, поэтому невозможно определить, будет ли программа C ++ когда-либо успешно компилироваться.
Однажды я написал бесконечную рекурсию в шаблонах C ++ и попытался скомпилировать с помощью gcc. Оказывается, у gcc есть настраиваемый предел глубины рекурсии.
Другие решения
Других решений пока нет …