Является ли C++ рекурсивно перечислимым языком?

Question

Является ли C++ рекурсивно перечислимым языком?

Я знаю, что C++ не разрешим. Но это рекурсивно перечислимо?

Давайте определим набор допустимых программ на C++ как любую четко определенную программу в соответствии с текущими стандартами C++.

Можно ли построить компилятор, который всегда может определить действительные программы на C++ за конечное время?

Или это ко-рекурсивно перечислимо?

Можно ли построить компилятор, который всегда может идентифицировать недействительные программы на C++ за конечное время?

Или нет?

2

c++ computation-theory turing-complete decidable

Источник

15 мар '14 в 05:13

1 ответ

Другие вопросы по тегам c++ computation-theory turing-complete decidable

user472522 15 мар '14 в 05:38 2014-03-15 05:38 · Answer 1 · 2014-03-15 05:38

Можно ли построить компилятор, который всегда может определить действительные программы на C++ за конечное время?

Да. При наличии достаточного количества времени и ресурсов компилятор C++ должен иметь возможность завершить компиляцию любой допустимой программы C++. Рекурсивно перечислимый язык требует машины Тьюринга, которая всегда завершается и дает положительный ответ, когда строка находится в языке, и компилятор делает это по существу.

Можно ли построить компилятор, который всегда может идентифицировать недействительные программы на C++ за конечное время?

Нет. Язык шаблонов C++ завершен по Тьюрингу, поэтому вы можете написать в нем бесконечную рекурсию. Из-за проблемы остановки невозможно определить, будет ли программа когда-либо завершать компиляцию, поэтому невозможно определить, будет ли программа C++ когда-либо успешно компилироваться.

Однажды я написал бесконечную рекурсию в шаблонах C++ и попытался скомпилировать с помощью gcc. Оказывается, у gcc есть настраиваемый предел глубины рекурсии.