Изменения

|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>.}}

Если мы рассматриваем язык <tex>p(w) = \begin{cases}1, \forall w \in L</tex> как проблему, то проблема называется ''разрешимой''\\0, если язык <tex>\forall w \notin L.\end{cases}</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>1</tex>. Далее считаем, что входные данные программы и сама программа расположены над одним алфавитом <tex>\Sigma</tex>.