Изменения

|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 \mathrm{R0, 1\} : x \in L \Leftrightarrow f(x) = 1</tex>.

|definition = Функция <tex>f : N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''вычислимойКласс всех разрешимых (рекурсивных) языков''' (англ. ''computableClass of decidable (recursive) languages''), если существует программа часто обозначается буквой <tex>p : \forall n \in D(f) \Rightarrow p(n) = f(n), \forall n \notin D(f) \Rightarrow p(n) = \bot mathrm{R} </tex>.

|id=uni|definition = Язык <tex>L</tex> называется ''разрешимым'Универсальный язык''' (англ. ''universal language'', если существует такая вычислимая функция ) <tex>f : \Sigma^* U = \to {\{0langle p, 1x \} : x rangle \in L |\leftrightarrow fp(x) = 1\} </tex>.

{{ОпределениеНа словах, ''универсальный язык'' можно определить следующим образом:|id=uni|definition='''Универсальный язык''' (англ{{---}} это язык всех пар "программа и её вход" таких, что программа на входе возвращает 1, входные данные программы и сама программа должны быть расположены над одним алфавитом. ''universal language'') Так как программа {{---}} это набор строк, занумеровав которые, можем получить биекцию "число" <tex>\ U = \{\langle p, x \rangle \ |\ p(x) = 1\} to</tex>.}}"строка"

== Примеры разрешимых множеств множества =={{ЛеммаУтверждение

{{ЛеммаУтверждение

Множество всех рациональных чисел, меньших числа ''<tex>e'' </tex> (основания натуральных логарифмов)или <tex>\pi</tex>, разрешимо.

Воспользуемся известной формулой Для чисел <tex>e, \pi</tex> существуют различные техники нахождения их точного представления, одна их которых описана в статье [http://www.mathpropress.com/stan/bibliography/spigot.pdf «A Spigot Algorithm for the Digits of Pi»]. Авторами алгоритма и его нарицателями являются американские математики Стенли Рабинович (Stanley Rabinowitz) и Стен Вэгон (Stan Wagon), которые создали свой алгоритм для вычисления нахождения цифр числа ''e'' <tex> = \sum \limits_{n=0}^{\infty} 1/n! pi</tex>в 1995 году. Сама же идея алгоритма вышла из-под пера некого Сейла (Sale) ещё в 1968 году, с помощью которой ''и предназначался тот алгоритм для нахождения цифр числа <tex>e'' может быть вычислено с произвольной точностью</tex>. Приведем программу, разрешающую данный вопрос:

'''if''' (<tex>int[] \ eDigits = getDigits(e) \ // \ array \ of \ digits \ e r</tex>< 2) '''return''' 1 '''if''' (<tex>int[] \ rDigits = getDigits(r) \ // \ array \ of \ digits \ r </tex>> 3) '''return''' 0 <tex> \mathrm{'''for}</tex> '''(i = 0 to eDigits.length();; ++i) '''if''' (getDigit(<tex> \mathrm{if} e</tex> (rDigits[, i] ) > eDigits[i]) getDigit(<tex> \mathrm{return} \ 0 r</tex> , i)) '''return''' 1 '''if''' (getDigit(<tex> \mathrm{if} e</tex> (rDigits[, i] ) < eDigits[i]) getDigit(<tex> \mathrm{return} \ 1 r</tex>, i)) '''return''' 0Так как число ''e'' иррационально(не существует его рационального представления), то ответ будет найден.

== Примеры неразрешимых множеств множества ==

{{ЛеммаУтверждение

'''if''' <tex> \mathrm{if} \ u(\langle x, x \rangle) == 1 </tex> <tex>\mathrm{'''while} \ ''' (true </tex>) <tex> \mathrm{'''else} </tex>''' <tex>\mathrm{'''return} \ ''' 1 </tex>

* Методические указания к курсу ”Сложность вычислений” Гамова А[http://www.Нmathpropress.com/stan/bibliography/spigot.pdf «A Spigot Algorithm for the Digits of Pi»]