Изменения
→Основные определения
== Основные определения ==
{{Определение
|definition= '''Рекурсивный язык''' (англ. ''recursive language'') <tex>L</tex> {{---}} язык, для которого существует программа <tex>\{p \ | \ \forall w \in L \Rightarrow p(w) = 1, \forall w \notin L \Rightarrow p(w) = 0\}</tex>.}}
{{Определение
|definition = Язык <tex>L</tex> называется '''разрешимым''', если существует такая [http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D1%8B%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D0%B5_%D1%84%D1%83%D0%BD%D0%BA%D1%86%D0%B8%D0%B8 [Вычислимые функции | вычислимая] (англ. ''computable'') ] функция <tex>f : \Sigma^* \to \{0, 1\} : x \in L \Leftrightarrow f(x) = 1</tex>.
}}
Если мы рассматриваем язык <tex>L</tex> как проблему, то проблема называется ''разрешимой'', если язык <tex>L</tex> ''рекурсивный''. В противном случае проблема называется ''неразрешимой''. Но часто данные понятия просто отождествляются.
{{Определение
}}
Так как программа {{---}} это набор строк, занумеровав которые, можем получить биекцию "число" <tex>\to</tex> "строка"