Изменения

|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>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимой''' ('англ. ''computable function'''), если существует программа <tex>p : \forall n \in D(f) \Rightarrow p(n) = f(n), \forall n \notin D(f) \Rightarrow p(n) = \bot </tex>.}} {{Определение|definition = Язык <tex>L</tex> называется ''разрешимым'', если существует такая функция <tex>f : \Sigma^* \to {0, 1} : x \in L \leftrightarrow f(x) = 1</tex> {{---}} вычислима.

|definition='''Универсальный язык''' ('англ. ''universal language''') <tex>\ U = \{\langle p, x \rangle \ |\ p(x) = 1\} </tex>.