Изменения

|definition=Язык <tex>L</tex> называется '''разрешимым''' Рекурсивный язык ('''рекурсивным, recursive language)'''), если существует такая программа <tex> p L</tex>{{---}} язык, что для которого существует программа <tex> p : \forall w \in L: \Rightarrow p(w) = 1</tex>, а <tex> \forall w \notin L: \Rightarrow p(w) = 0</tex>. Класс всех разрешимых языков часто обозначается через <tex> \mathrm{R} </tex>.

Если мы рассматриваем язык <tex>L</tex> как проблему, то проблема называется ''разрешимой'', если язык <tex>L</tex> ''рекурсивный''. В противном случае проблема называется ''неразрешимой''. Но часто данные понятия просто отождествляются. {{Определение|definition=Класс всех разрешимых (рекурсивных) языков часто обозначается буквой <tex> \mathrm{R} </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>.}} {{Определение|id=uni|definition='''Универсальный язык''' ('''universal language''') <tex>\ U = \{\langle p, x \rangle \ |\ p(x) = 1\} </tex>.}} == Некоторые разрешимые множества==

<tex>p(i):</tex> '''if''' <tex> \mathrm{if} \ i \ mod \ 2 == 0 </tex> '''return''' <tex> \mathrm{return} \ 1 </tex> '''<tex>\mathrm{else'''} </tex> '''return''' <tex> \mathrm{return} \ 0 </tex> 

==Пример неразрешимого Некоторые неразрешимые множества== {{Определение|id=uni|definition=Язык <tex>\ U = \{\langle p, x \rangle \ |\ p(x) = 1\} </tex> называется '''универсальным''' ('''universal language''').}}

Приведём доказательство от противного. <br/> Пусть язык <tex> U </tex> разрешим. Тогда , тогда существует такая программа <tex> u </tex>, что : <tex> \forall \langle p, x \rangle \in U: \Rightarrow u(\langle p, x \rangle) = 1</tex>, а <tex> \forall \langle p, x \rangle \notin U: \Rightarrow u(\langle p, x \rangle) = 0</tex>. <br/> 

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

Теперь рассмотрим Рассмотрим вызов <tex> r(r) </tex>:* если Eсли <tex> u(\langle r, r \rangle) = 1 </tex>, то условие '''<tex>\mathrm{if''' }</tex> выполнится и программа зависнет. Но , но, так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 1 \Rightarrow r(r) = 1</tex>;* если Eсли <tex> u(\langle r, r \rangle) = 0 </tex>, то условие '''<tex>\mathrm{if''' }</tex> не выполнится и программа вернет <tex>1</tex>. Но , но, так как программа <tex> u </tex> разрешает универсальный язык, <tex> u(\langle r, r \rangle) = 0 \Rightarrow r(r) \ne 1</tex>.

Таким образом, из Из предположения о разрешимости универсального языка мы пришли к противоречию.

==Источники информации==