Я встречал много определений рекурсивных и рекурсивно перечислимых языков. Но я не мог понять, кто они.
Может кто-нибудь сказать мне, что они простыми словами?
На самом деле, нет. Вы должны прочитать несколько книг. Возможно, мы можем рекомендовать некоторые из них.
Тем не менее, язык является рекурсивным, если есть машина Тьюринга, которая всегда может ответить «да» или «нет», если данная строка является частью этого языка. Если мы отменим это требование, чтобы просто сказать «да» для строк языка (он может работать вечно, если это не так), то у нас будет рекурсивно перечислимый язык. Нетрудно понять, что рекурсивный язык может быть выбран машиной Тьюринга, в то время как рекурсивно перечислимый язык может иметь свои строки в списке (например, при параллельном запуске бесконечного числа машин Тьюринга - да, это возможно, см. dove-tailing - на всех строках алфавита и выводит строку, если соответствующий TM принимает). Есть много, много эквивалентных определений.
Проблема является рекурсивной или разрешимой, если машина может вычислить ответ.
Проблема рекурсивно перечислима или полуразрешима, если машина может быть уверена, что ответ положительный.
Язык представляет собой набор строк. Возможно, бесконечной мощности.
Язык является рекурсивным перечислимым, если существует TM, который продолжает выводить строки, которые принадлежат языку (и только такие строки), так что в конечном итоге каждая строка в языке будет в выводе.
Язык рекурсивен, если вышеупомянутая TM не только выводит все строки в языке, но и делает это по порядку! (скажем, лексикографически).
Я уверен, что вы можете легко думать о рекурсивных языках (и создать TM, который выводит их по порядку). Довольно сложно придумать рекурсивные перечислимые языки (которые не являются рекурсивными), если вы не прочитаете еще немного о неразрешимости и диагонализации. Но такие языки существуют.
Рекурсивные языки разрешимы некоторыми машинами Тьюринга, т. Е. Есть ТМ, который может, если любая входная строка (над соответствующим алфавитом) правильно ответить «да», если строка на языке, или «нет», если это не так.
Рекурсивно перечислимые языки распознаются только, т. Е. Существует машина Тьюринга, которая принимает, когда строка находится в языке, но может зацикливаться вечно, если строка отсутствует в языке.
источник
Я чувствую, что основное различие между рекурсивными и рекурсивно перечислимыми языками состоит в том, что машина рекурсивного Тьюринга останавливается в неконечном состоянии, если она не принимает строку
Рекурсивно перечислимая машина Тьюринга, если она не принимает строку, может остановиться в неконечном состоянии или в цикле навсегда, что не относится к рекурсивным языкам
источник
==> Язык является рекурсивным, если существует машина Тьюринга, которая принимает каждую строку в языке и отклоняет ее, если ее нет в языке. например, давайте возьмем машину Тьюринга M и строку w: если строка w является членом машины Тьюринга M, то M останавливается в своем конечном состоянии, в противном случае она отклоняет вычисление. ==> ==> Язык является рекурсивным перечисляемым, если существует машина Тьюринга, которая принимает каждую строку в языке и отклоняет ее, если ее нет в языке, может быть цикл навсегда. например, давайте возьмем машину Тьюринга M и String w: если в языке есть строка w, то M останавливается в своем конечном состоянии. В противном случае он отклоняет вычисления или может выполняться вечно.
источник