http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=217.118.78.44&feedformat=atom
Викиконспекты - Вклад участника [ru]
2024-03-28T20:19:12Z
Вклад участника
MediaWiki 1.30.0
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A2%D0%B8%D0%BF%D1%8B_%D0%B4%D0%B8%D1%84%D1%84%D0%B5%D1%80%D0%B5%D0%BD%D1%86%D0%B8%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D1%85_%D1%83%D1%80%D0%B0%D0%B2%D0%BD%D0%B5%D0%BD%D0%B8%D0%B9&diff=49664
Типы дифференциальных уравнений
2015-10-21T12:51:27Z
<p>217.118.78.44: /* Способ решения методом Владимира Красноцветова */</p>
<hr />
<div>==Уравнение с разделенными переменными==<br />
{{Определение|definition= уравнение вида <tex>M(x)dx + N(y)dy = 0 \:\: (1)</tex> называется уравнением с разделенными переменными}}<br />
<b>Решение:</b> <br />
<tex>(1) \:\: \Leftrightarrow \:\: M(x)dx = -N(y)dy</tex> далее интегрируем правую и левую части<br />
==Уравнение с разделяемыми переменными==<br />
{{Определение|definition= уравнение вида <tex>M_{1}(x)N_{1}(y)dx + M_{2}(x)N_{2}(y)dy = 0 \:\: (2)</tex> называется уравнением с разделяемыми переменными}}<br />
<b>Решение:</b> (2) разделим на <tex>N_{1}(y)M_{2}(x) \neq 0</tex> и оно сведется к (1). в случае = 0 могут существовать осбые решения.<br />
==Однородные уравнения==<br />
{{Определение|definition = уравнение вида <tex>M(x, y)dx + N(x, y)dy = 0 \:\: (3)</tex>, где M и N - однородные функции одного измерения, называется однородным уравнением}}<br />
{{Определение | definition= <tex>f(x, y) - </tex> однородная функция измерения n <tex>\Leftrightarrow \: f(\lambda x, \lambda y) = \lambda^{n}f(x, y)</tex> }}<br />
<b>Решение:</b> произвести замену <tex>t = \frac{y}{x}</tex><br />
<br />
{{Определение | definition= <tex dpi=150>\frac{dy}{dx}=f(\frac{y}{x})</tex> - один из видов однородного уравнения. }}<br />
==Уравнения приводящиеся к однородным==<br />
{{Определение|definition= уравнение вида <tex dpi = 150>\frac{dy}{dx}= f(\frac{a_{1}x + b_{1}y + c_{1}}{a_{2}x + b_{2}y + c_{2}}) (4)</tex> называется уравнением приводящимся к однородному}}<br />
{{Утверждение|statement = <br />
Решением уравнения <tex>(4)</tex> является:<br />
1) <tex>\begin{vmatrix}<br />
a_{1} & b_{1}\\ <br />
a_{2} & b_{2}<br />
\end{vmatrix} \neq 0 \Rightarrow \left\{\begin{matrix}<br />
x = u + \alpha \\ <br />
y = v + \beta <br />
\end{matrix}\right. </tex><br />
<br />
<tex> (\alpha, \beta) : \left\{\begin{matrix}<br />
a_{1}x + b_{1}y + c_{1} = 0\\ <br />
a_{2}x + b_{2}y + c_{2} = 0<br />
\end{matrix}\right.</tex><br />
<br />
Тогда получаем однородное уравнение.<br />
<br />
2) <tex>\begin{vmatrix}<br />
a_{1} & b_{1}\\ <br />
a_{2} & b_{2}<br />
\end{vmatrix} = 0 \Rightarrow <br />
</tex> пусть <tex>a_{1} x + b_{1} y + c_{1} = t<br />
</tex><br />
<br><br />
<br />
Тогда получаем уравнение с разделяющимися переменными.<br />
<br />
| proof = Докажем 1), второй доказывается аналогично.<br />
Подставим замену: <br><br />
<tex>a_{1}x + b_{1}y + c_{1} = a_{1}(u + \alpha) + b_{1}(v + \beta) + c_{1} = a_{1}\alpha + b_{1}\beta + c_{1} + a_{1}u + b_{1}v =</tex> <tex>a_{1}u + b_{1}v = 0 </tex><br />
Получили однородное уравнение.<br />
}}<br />
<br />
==Линейное уравнение первого порядка==<br />
{{Определение|definition= уравнение вида <tex>\frac{dy}{dx} = p(x) y + q(x)(5)</tex> называется линейным уравнением <tex>I</tex> порядка}}<br />
<br />
{{Определение|definition= Если <tex>q(x) = 0</tex>, то уравнение <tex>(5) </tex> называется однородным линейным уравнением <tex>I</tex> порядка}}<br />
<br />
===Способ решения методом Бернулли===<br />
Пусть <tex> y(x) = u(x) v(x)</tex>, тогда:<br />
<br />
<tex> u'(x) v(x) + u(x) v'(x) = p(x) u(x) v(x) + q(x) </tex><br />
<br />
<tex><br />
u'(x) v(x) + u(x) [ v'(x) - p(x) v(x)] = q(x)<br />
</tex>, назовем это уравнение <tex>(5a)</tex><br />
<br />
Пусть <tex> v(x) </tex> таково, что:<br />
<br />
<tex> v'(x) - p(x) v(x) = 0 </tex><br />
<br />
Тогда:<br />
<br />
<tex>\frac{dv(x)}{dx} - p(x) v(x) = 0 </tex>. Домножим на <tex> \frac{dx}{dv(x)} </tex><br />
<tex>\frac{dv}{v} - p(x) dx = 0 </tex>. Отсюда получаем:<br />
<br />
<tex>ln(v) = \int p(x)dx + C</tex><br />
<br />
<tex>v(x) = e^{C+ \int p(x)dx} = C e^{\int p(x)dx}</tex><br />
<br />
Пусть <tex> C = 1</tex>. Тогда из <tex>(5a)</tex> получаем:<br />
<br />
<tex> u'(x) e^{\int p(x)dx} = q(x) </tex><br />
<br />
<tex> u(x) = \int q(x) e^{\int p(x)dx} dx + C_{1} </tex>. Тогда<br />
<br />
<tex>y(x) = e^{\int p(x)dx} [ \int q(x) e^{\int p(x)dx} dx + C_{1}] </tex><br />
<br />
===Способ решения методом Лагранжа===<br />
Рассмотрим:<br />
<br />
<tex> \frac{dx}{dy} = p(x) y </tex><br />
<br />
Рассмотрим общее однородное(O.O) и общее неоднородное решение(O.H):<br />
<tex> y_{O.O} = C e^{\int p(x)dx}</tex> (из док-ва Бернулли)<br />
<br />
Пусть:<br />
<br />
<tex> y_{O.H} = C(x) e^{\int p(x)dx}</tex><br />
<br />
<tex> C'(x) e^{\int p(x)dx} + C(x) p(x) e^{\int p(x)dx} = p(x) C(x) e^{\int p(x)dx} + q(x) </tex> <br />
<br />
<tex> C'(x) = q(x) e^{-\int p(x)dx} </tex><br />
<br />
<tex> C(x) = \int q(x) C(x) e^{\int p(x)dx} dx + C_{1} </tex><br />
<br />
<tex>y(x) = e^{\int p(x)dx} [ \int q(x) e^{\int p(x)dx} dx + C_{1}] </tex><br />
<br />
===Способ решения методом Игоря Сушенцева===<br />
Запомнить формулу:<br><br />
<tex>y(x) = e^{\int p(x)\mathrm dx} \left[ \int q(x) e^{\int p(x)\mathrm dx} dx + C_{1} \right] </tex><br />
<br />
==Уравнение в полных дифференциалах==<br />
{{Определение| definition= Уравнение вида: <tex>M(x, y)dx + N(x, y)dy = 0 \:\: (6)</tex> называется уравнением в полных дифференциалах, если <tex>(6) = du(x, y)</tex>}}<br />
т.к. <tex>du(x, y) = 0 \Leftrightarrow u(x, y) = C \: -</tex> общий интеграл.<br />
{{Теорема|statement = Пусть <tex>M(x, y), N(x, y) \in C(G)</tex>, где G - односвязная область, и <tex>\frac{\partial M(x,y)}{\partial y}, \: \frac{\partial N(x, y)}{\partial x} \in C(G)</tex>; <br> Тогда <tex>Mdx + Ndy = du \: \Leftrightarrow \frac{\partial M(x, y)}{\partial y} \equiv \frac{\partial N(x, y)}{\partial x} </tex>| proof = сами доказывайте.}}<br />
<b>Решение:</b> <tex>u(x, y) = \int_{x_{0}}^{x}M(x, y)dx + \int_{y_{0}}^{y}N(x_{0}, y)dy = C \: - </tex> Общее решение.<br />
<br />
==Уравнение, приводящееся к уравнениию в полных дифференциалах==<br />
в условиях предыдущего определения, но <tex>\frac{\partial M}{\partial y} \not\equiv \frac{\partial N}{\partial x}</tex>. Домножим (6) на <tex>\mu(x, y): \:</tex> <br> <tex>M \frac{\partial \mu}{\partial y} + \mu \frac{\partial M }{\partial y} = N \frac{\partial \mu}{\partial x} + \mu \frac{\partial N}{\partial x} \: \Rightarrow \: M \frac{\partial \mu}{\partial y} - N \frac{\partial \mu}{\partial x} = \mu (\frac{\partial N}{\partial x} - \frac{\partial M}{\partial y}) \: (*)</tex> <br> <br />
{{Утверждение|statement= Пусть <tex>\exists \omega (x, y) \in C'(G): \:\:</tex> <tex dpi = "165"> \frac{\frac{\partial M}{\partial y} - \frac{\partial N}{\partial x}}{ N \frac{\partial \omega}{\partial x} - M \frac{\partial \omega}{\partial y}} = \psi(\omega) \: \Rightarrow \mu = e^{\int \psi(\omega)d\omega}</tex>|<br />
proof= Пусть <tex dpi = "145">\mu = h(\omega) \: \Rightarrow \: M \frac{dh}{d\omega}\frac{\partial \omega}{\partial y} - N \frac{dh}{d\omega}\frac{\partial \omega}{\partial x} = h(\omega)(\frac{\partial N}{\partial x} - \frac{\partial M}{\partial y})</tex> <br><br>перегреппируем: <tex dpi = "165">\frac{dh}{d\omega} = h(\omega)\frac{\frac{\partial N}{\partial x} - \frac{\partial M}{\partial y})}{M\frac{\partial \omega}{\partial y} - N \frac{\partial \omega}{\partial x}} \: \Rightarrow</tex><br><tex dpi = "145">\frac{dh}{d\omega} = h(\omega)\psi(\omega)</tex><br />
<tex dpi = "145">\mu(x, y) = h(\omega) = e^{\int\psi(\omega)d\omega}</tex>}}<br />
только как решать все равно не понятно.<br><br />
Но. <br><br />
Если <tex>\mu</tex> зависит только от x или только от y, можно выразить ее в явном виде:<br><br />
<tex dpi = "150"> \mu(x) = e^{\int \frac{\frac{\partial M}{\partial y} - \frac{\partial N}{\partial x}}{N} dx}</tex><br><br />
<tex dpi = "150"> \mu(y) = e^{-\int \frac{\frac{\partial M}{\partial y} - \frac{\partial N}{\partial x}}{M} dy}</tex><br />
<br />
==Уравнение Бернулли==<br />
{{Определение| definition= уравнение вида <tex>\frac{dy}{dx} = p(x) y + q(x)y^m, \: m \in \mathbb{R} \setminus \left \{ 0, 1 \right \}\:</tex>, называется уравнением Бернулли.}}<br />
<b>Решение:</b><br><br />
<tex>y^{-m}y' = p(x)y^{1-m}+q(x), y \neq 0</tex><br><br />
<tex>(\frac{y^{1-m}}{1-m})' - p(x)y^{1-m}= q(x)</tex>, пусть <tex>z(x) = y^{1-m} \: \Rightarrow</tex><br><br />
<tex>z'(x) - p(x)(1 - m)z(x) = (1 - m)q(x) \: - </tex>линейное относительно z уравнение.<br />
==Уравнение Риккати==<br />
{{Определение|definition= Уравнение вида <tex>\frac{dy}{dx} = p(x)y + q(x) + r(x)y^{2}\:\: (9)</tex>, где <tex>p, q, r \in C(a,b)\:</tex> называется уравнением Риккати}}<br />
<b>Решение:</b><br><br />
Пусть <tex>y_{1}(x)\: - </tex> частное решение уравнения (9), тогда <tex>y(x) = z(x) + y_{1}</tex><br><br />
<tex>z' + y'_{1} = p(z + y_{1}) + q + r(z + y_{1})^{2}</tex><br><br />
<tex>z' = pz + rz^{2} + 2rzy_{1}\: - </tex> уравнение (8)<br />
==Уравнения 1-го порядка не разрешенные относительно 1-й производной==<br />
===x явно зависит от y'===<br />
<b>Решение:</b><br><br />
Пусть <tex>x = \phi(y')\:\: (10)</tex><br />
<br>Перейдем к параметрической системе:<br />
<br><tex><br />
\left\{\begin{matrix}<br />
x = \phi(t)<br />
\\y' = t<br />
\end{matrix}\right.</tex><br><br />
<tex>dy = t dx = t \phi'(t)</tex><br><br />
<tex><br />
\left\{\begin{matrix}<br />
y = \int t\phi'(t)dt<br />
\\x = \phi(t)<br />
\end{matrix}\right.</tex><br />
<br><br />
===y явно зависит от y'===<br />
<b>Решение:</b><br><br />
Пусть <tex>y = \phi(y')\:\: (11)</tex><br />
<br>Переходим к системе:<br />
<tex><br />
\left\{\begin{matrix}<br />
y = \phi(t)<br />
\\y' = t<br />
\end{matrix}\right.</tex><br><br />
<tex>dx = \frac{\phi'(t)dt}{t}</tex><br><br />
<br />
<tex><br />
\left\{\begin{matrix}<br />
x = \int \frac{\phi(t)dt}{t}<br />
\\y = \phi(t)<br />
\end{matrix}\right.</tex><br />
===уравнение Лагранжа===<br />
{{Определение|definition= уравнение вида <tex>y = \phi(y')x + \psi(y')\:\: (12)</tex>, называется уравнением Лагранжа}}<br />
<b>Решение:</b><br><br />
Переходим к системе:<br><br />
<tex><br />
\left\{\begin{matrix}<br />
y = \phi(t)x + \psi(t)<br />
\\y' = t<br />
<br />
\end{matrix}\right.</tex><br><br />
<tex>dy = (\phi'(t)x + \psi'(t))dt + \phi(t)dx = tdx</tex><br><br />
<tex>(\phi'(t)x+ \psi'(t))dt + (\phi(t) - t)dx = 0</tex><br><br />
<tex>\Rightarrow \: ]x = F(t, C), \: \phi(t) - t \neq 0</tex><br><br />
<tex>\left\{\begin{matrix}<br />
x = F(t, C)<br />
\\y = \phi(t)F(t, C) + \psi(t)<br />
\end{matrix}\right.</tex><br><br />
===Уравнение Клеро===<br />
{{Определение|definition= уравнение вида <tex>y = xy' + \psi(y')\:\: (13)</tex>, называется уравнением Клеро}}<br />
<b>Решение:</b><br><br />
Пусть <tex>y' = t \: \Rightarrow \: dy = tdx = (x + \psi'(t))dt + tdx \: \Rightarrow \: (x + \psi'(t))dt = 0 </tex><br />
<br><br />
Тогда либо <tex>dt = 0 \: (1)</tex>, либо <tex>x + \psi'(t) = 0 \: (2)</tex><br />
<br><br />
<tex>(1):\: t = C \Rightarrow y = xC + \psi(C)</tex> {{---}} общее решение.<br />
<br><br />
<tex>(2):\: \left\{\begin{matrix}<br />
x = -\psi'(t)\\y = -\psi'(t)t + \psi(t) <br />
\end{matrix}\right.</tex></div>
217.118.78.44
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A3%D1%81%D0%BF%D0%B5%D0%BD%D1%81%D0%BA%D0%BE%D0%B3%D0%BE-%D0%A0%D0%B0%D0%B9%D1%81%D0%B0&diff=42068
Свойства перечислимых языков. Теорема Успенского-Райса
2014-12-12T14:22:53Z
<p>217.118.78.44: /* Источники информации */</p>
<hr />
<div>== Определения ==<br />
<br />
Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> RE </tex>.<br />
{{Определение<br />
|definition='''Свойством языков''' называется множество <tex> A \subset RE </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство называется '''тривиальным''', если <tex> A = \varnothing </tex> или <tex> A = RE </tex>.<br />
}}<br />
{{Определение<br />
|definition='''Язык свойства''' <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство <tex> A </tex> называется '''разрешимым''', если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].<br />
}}<br />
<br />
== Теорема Успенского-Райса ==<br />
{{Теорема<br />
|statement=<br />
Язык никакого нетривиального свойства не является разрешимым.<br />
|proof=<br />
Приведём доказательство от противного.<br />
<br />
Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.<br />
<br />
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным). <br />
<br />
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.<br />
<br />
Рассмотрим вспомогательную программу:<br />
<tex>g_{i,x}(y):</tex><br />
if U(i, x) == 1<br />
'''return''' <tex>p_X(y)</tex><br />
else<br />
while True<br />
<br />
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:<br />
<tex>US(\langle i, x \rangle )</tex><br />
'''return''' <tex>p_A ( g_{i,x} ) </tex><br />
<br />
Заметим, что<br />
<tex><br />
L(g_{i,x}) = \begin{cases}<br />
X, & U(i, x) = 1; \\<br />
\varnothing, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex><br />
<br />
Следовательно, <br/> <tex> <br />
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}<br />
p_A(p_X), & U(i, x) = 1; \\<br />
p_A(p_\varnothing ), & U(i, x) \neq 1; \\<br />
\end{cases} = \begin{cases}<br />
1, & U(i, x) = 1; \\<br />
0, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex> {{---}} программа, разрешающая универсальное множество. Получили противоречие.<br />
}}<br />
<br />
== Источники информации ==<br />
* Rice, H. G. "Classes of Recursively Enumerable Sets and Their Decision Problems." Trans. Amer. Math. Soc. 74, 358-366, 1953.<br />
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]<br />
<br />
[[Категория: Теория вычислимости]]<br />
[[Категория: Теория формальных языков]]</div>
217.118.78.44
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A3%D1%81%D0%BF%D0%B5%D0%BD%D1%81%D0%BA%D0%BE%D0%B3%D0%BE-%D0%A0%D0%B0%D0%B9%D1%81%D0%B0&diff=42067
Свойства перечислимых языков. Теорема Успенского-Райса
2014-12-12T14:21:07Z
<p>217.118.78.44: /* Источники информации */</p>
<hr />
<div>== Определения ==<br />
<br />
Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> RE </tex>.<br />
{{Определение<br />
|definition='''Свойством языков''' называется множество <tex> A \subset RE </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство называется '''тривиальным''', если <tex> A = \varnothing </tex> или <tex> A = RE </tex>.<br />
}}<br />
{{Определение<br />
|definition='''Язык свойства''' <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство <tex> A </tex> называется '''разрешимым''', если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].<br />
}}<br />
<br />
== Теорема Успенского-Райса ==<br />
{{Теорема<br />
|statement=<br />
Язык никакого нетривиального свойства не является разрешимым.<br />
|proof=<br />
Приведём доказательство от противного.<br />
<br />
Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.<br />
<br />
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным). <br />
<br />
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.<br />
<br />
Рассмотрим вспомогательную программу:<br />
<tex>g_{i,x}(y):</tex><br />
if U(i, x) == 1<br />
'''return''' <tex>p_X(y)</tex><br />
else<br />
while True<br />
<br />
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:<br />
<tex>US(\langle i, x \rangle )</tex><br />
'''return''' <tex>p_A ( g_{i,x} ) </tex><br />
<br />
Заметим, что<br />
<tex><br />
L(g_{i,x}) = \begin{cases}<br />
X, & U(i, x) = 1; \\<br />
\varnothing, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex><br />
<br />
Следовательно, <br/> <tex> <br />
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}<br />
p_A(p_X), & U(i, x) = 1; \\<br />
p_A(p_\varnothing ), & U(i, x) \neq 1; \\<br />
\end{cases} = \begin{cases}<br />
1, & U(i, x) = 1; \\<br />
0, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex> {{---}} программа, разрешающая универсальное множество. Получили противоречие.<br />
}}<br />
<br />
== Источники информации ==<br />
* Weisstein, Eric W., "Rice's theorem", MathWorld.<br />
* [https://en.wikipedia.org/wiki/Rice%27s_theorem Wikipedia — Rice's theorem]<br />
<br />
[[Категория: Теория вычислимости]]<br />
[[Категория: Теория формальных языков]]</div>
217.118.78.44
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A3%D1%81%D0%BF%D0%B5%D0%BD%D1%81%D0%BA%D0%BE%D0%B3%D0%BE-%D0%A0%D0%B0%D0%B9%D1%81%D0%B0&diff=42066
Свойства перечислимых языков. Теорема Успенского-Райса
2014-12-12T14:18:15Z
<p>217.118.78.44: /* Источники информации */</p>
<hr />
<div>== Определения ==<br />
<br />
Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> RE </tex>.<br />
{{Определение<br />
|definition='''Свойством языков''' называется множество <tex> A \subset RE </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство называется '''тривиальным''', если <tex> A = \varnothing </tex> или <tex> A = RE </tex>.<br />
}}<br />
{{Определение<br />
|definition='''Язык свойства''' <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство <tex> A </tex> называется '''разрешимым''', если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].<br />
}}<br />
<br />
== Теорема Успенского-Райса ==<br />
{{Теорема<br />
|statement=<br />
Язык никакого нетривиального свойства не является разрешимым.<br />
|proof=<br />
Приведём доказательство от противного.<br />
<br />
Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.<br />
<br />
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным). <br />
<br />
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.<br />
<br />
Рассмотрим вспомогательную программу:<br />
<tex>g_{i,x}(y):</tex><br />
if U(i, x) == 1<br />
'''return''' <tex>p_X(y)</tex><br />
else<br />
while True<br />
<br />
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:<br />
<tex>US(\langle i, x \rangle )</tex><br />
'''return''' <tex>p_A ( g_{i,x} ) </tex><br />
<br />
Заметим, что<br />
<tex><br />
L(g_{i,x}) = \begin{cases}<br />
X, & U(i, x) = 1; \\<br />
\varnothing, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex><br />
<br />
Следовательно, <br/> <tex> <br />
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}<br />
p_A(p_X), & U(i, x) = 1; \\<br />
p_A(p_\varnothing ), & U(i, x) \neq 1; \\<br />
\end{cases} = \begin{cases}<br />
1, & U(i, x) = 1; \\<br />
0, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex> {{---}} программа, разрешающая универсальное множество. Получили противоречие.<br />
}}<br />
<br />
== Источники информации ==<br />
* Weisstein, Eric W., "Rice's theorem", MathWorld.<br />
<br />
[[Категория: Теория вычислимости]]<br />
[[Категория: Теория формальных языков]]</div>
217.118.78.44
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A3%D1%81%D0%BF%D0%B5%D0%BD%D1%81%D0%BA%D0%BE%D0%B3%D0%BE-%D0%A0%D0%B0%D0%B9%D1%81%D0%B0&diff=42065
Свойства перечислимых языков. Теорема Успенского-Райса
2014-12-12T14:17:17Z
<p>217.118.78.44: /* Источники информации */</p>
<hr />
<div>== Определения ==<br />
<br />
Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> RE </tex>.<br />
{{Определение<br />
|definition='''Свойством языков''' называется множество <tex> A \subset RE </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство называется '''тривиальным''', если <tex> A = \varnothing </tex> или <tex> A = RE </tex>.<br />
}}<br />
{{Определение<br />
|definition='''Язык свойства''' <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство <tex> A </tex> называется '''разрешимым''', если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].<br />
}}<br />
<br />
== Теорема Успенского-Райса ==<br />
{{Теорема<br />
|statement=<br />
Язык никакого нетривиального свойства не является разрешимым.<br />
|proof=<br />
Приведём доказательство от противного.<br />
<br />
Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.<br />
<br />
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным). <br />
<br />
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.<br />
<br />
Рассмотрим вспомогательную программу:<br />
<tex>g_{i,x}(y):</tex><br />
if U(i, x) == 1<br />
'''return''' <tex>p_X(y)</tex><br />
else<br />
while True<br />
<br />
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:<br />
<tex>US(\langle i, x \rangle )</tex><br />
'''return''' <tex>p_A ( g_{i,x} ) </tex><br />
<br />
Заметим, что<br />
<tex><br />
L(g_{i,x}) = \begin{cases}<br />
X, & U(i, x) = 1; \\<br />
\varnothing, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex><br />
<br />
Следовательно, <br/> <tex> <br />
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}<br />
p_A(p_X), & U(i, x) = 1; \\<br />
p_A(p_\varnothing ), & U(i, x) \neq 1; \\<br />
\end{cases} = \begin{cases}<br />
1, & U(i, x) = 1; \\<br />
0, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex> {{---}} программа, разрешающая универсальное множество. Получили противоречие.<br />
}}<br />
<br />
== Источники информации ==<br />
* <tex>Weisstein, Eric W., "Rice's theorem", MathWorld. </tex><br />
<br />
[[Категория: Теория вычислимости]]<br />
[[Категория: Теория формальных языков]]</div>
217.118.78.44
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A3%D1%81%D0%BF%D0%B5%D0%BD%D1%81%D0%BA%D0%BE%D0%B3%D0%BE-%D0%A0%D0%B0%D0%B9%D1%81%D0%B0&diff=42064
Свойства перечислимых языков. Теорема Успенского-Райса
2014-12-12T14:13:17Z
<p>217.118.78.44: </p>
<hr />
<div>== Определения ==<br />
<br />
Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> RE </tex>.<br />
{{Определение<br />
|definition='''Свойством языков''' называется множество <tex> A \subset RE </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство называется '''тривиальным''', если <tex> A = \varnothing </tex> или <tex> A = RE </tex>.<br />
}}<br />
{{Определение<br />
|definition='''Язык свойства''' <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство <tex> A </tex> называется '''разрешимым''', если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].<br />
}}<br />
<br />
== Теорема Успенского-Райса ==<br />
{{Теорема<br />
|statement=<br />
Язык никакого нетривиального свойства не является разрешимым.<br />
|proof=<br />
Приведём доказательство от противного.<br />
<br />
Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.<br />
<br />
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным). <br />
<br />
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.<br />
<br />
Рассмотрим вспомогательную программу:<br />
<tex>g_{i,x}(y):</tex><br />
if U(i, x) == 1<br />
'''return''' <tex>p_X(y)</tex><br />
else<br />
while True<br />
<br />
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:<br />
<tex>US(\langle i, x \rangle )</tex><br />
'''return''' <tex>p_A ( g_{i,x} ) </tex><br />
<br />
Заметим, что<br />
<tex><br />
L(g_{i,x}) = \begin{cases}<br />
X, & U(i, x) = 1; \\<br />
\varnothing, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex><br />
<br />
Следовательно, <br/> <tex> <br />
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}<br />
p_A(p_X), & U(i, x) = 1; \\<br />
p_A(p_\varnothing ), & U(i, x) \neq 1; \\<br />
\end{cases} = \begin{cases}<br />
1, & U(i, x) = 1; \\<br />
0, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex> {{---}} программа, разрешающая универсальное множество. Получили противоречие.<br />
}}<br />
<br />
== Источники информации ==<br />
<br />
[[Категория: Теория вычислимости]]<br />
[[Категория: Теория формальных языков]]</div>
217.118.78.44
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A3%D1%81%D0%BF%D0%B5%D0%BD%D1%81%D0%BA%D0%BE%D0%B3%D0%BE-%D0%A0%D0%B0%D0%B9%D1%81%D0%B0&diff=42063
Свойства перечислимых языков. Теорема Успенского-Райса
2014-12-12T14:12:23Z
<p>217.118.78.44: </p>
<hr />
<div>== Определения ==<br />
<br />
Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> RE </tex>.<br />
{{Определение<br />
|definition='''Свойством языков''' называется множество <tex> A \subset RE </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство называется '''тривиальным''', если <tex> A = \varnothing </tex> или <tex> A = RE </tex>.<br />
}}<br />
{{Определение<br />
|definition='''Язык свойства''' <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство <tex> A </tex> называется '''разрешимым''', если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].<br />
}}<br />
<br />
== Теорема Успенского-Райса ==<br />
{{Теорема<br />
|statement=<br />
Язык никакого нетривиального свойства не является разрешимым.<br />
|proof=<br />
Приведём доказательство от противного.<br />
<br />
Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.<br />
<br />
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным). <br />
<br />
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.<br />
<br />
Рассмотрим вспомогательную программу:<br />
<tex>g_{i,x}(y):</tex><br />
if U(i, x) == 1<br />
'''return''' <tex>p_X(y)</tex><br />
else<br />
while True<br />
<br />
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:<br />
<tex>US(\langle i, x \rangle )</tex><br />
'''return''' <tex>p_A ( g_{i,x} ) </tex><br />
<br />
Заметим, что<br />
<tex><br />
L(g_{i,x}) = \begin{cases}<br />
X, & U(i, x) = 1; \\<br />
\varnothing, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex><br />
<br />
Следовательно, <br/> <tex> <br />
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}<br />
p_A(p_X), & U(i, x) = 1; \\<br />
p_A(p_\varnothing ), & U(i, x) \neq 1; \\<br />
\end{cases} = \begin{cases}<br />
1, & U(i, x) = 1; \\<br />
0, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex> {{---}} программа, разрешающая универсальное множество. Получили противоречие.<br />
}}<br />
<br />
[[Категория: Теория вычислимости]]<br />
[[Категория: Теория формальных языков]]</div>
217.118.78.44
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A3%D1%81%D0%BF%D0%B5%D0%BD%D1%81%D0%BA%D0%BE%D0%B3%D0%BE-%D0%A0%D0%B0%D0%B9%D1%81%D0%B0&diff=42062
Свойства перечислимых языков. Теорема Успенского-Райса
2014-12-12T14:09:15Z
<p>217.118.78.44: /* Определения */</p>
<hr />
<div>== Определения ==<br />
<br />
Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> RE </tex>.<br />
{{Определение<br />
|definition='''Свойством языков''' называется множество <tex> A \subset RE </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство называется '''тривиальным''', если <tex> A = \varnothing </tex> или <tex> A = RE </tex>.<br />
}}<br />
{{Определение<br />
|definition='''Язык свойства''' <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p \mid L(p) \in A \rbrace </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство <tex> A </tex> называется '''разрешимым''', если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].<br />
}}<br />
<br />
== Теорема Успенского-Райса ==<br />
{{Теорема<br />
|statement=<br />
Язык никакого нетривиального свойства не является разрешимым.<br />
|proof=<br />
Приведём доказательство от противного.<br />
<br />
Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.<br />
<br />
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным). <br />
<br />
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.<br />
<br />
Рассмотрим вспомогательную программу:<br />
<tex>g_{i,x}(y):</tex><br />
if U(i, x) == 1<br />
'''return''' <tex>p_X(y)</tex><br />
else<br />
while True<br />
<br />
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:<br />
<tex>US(\langle i, x \rangle )</tex><br />
'''return''' <tex>p_A ( g_{i,x} ) </tex><br />
<br />
Заметим, что<br />
<tex><br />
L(g_{i,x}) = \begin{cases}<br />
X, & U(i, x) = 1; \\<br />
\varnothing, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex><br />
<br />
Следовательно, <br/> <tex> <br />
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}<br />
p_A(p_X), & U(i, x) = 1; \\<br />
p_A(p_\varnothing ), & U(i, x) \neq 1; \\<br />
\end{cases} = \begin{cases}<br />
1, & U(i, x) = 1; \\<br />
0, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex> {{---}} программа, разрешающая универсальное множество. Получили противоречие.<br />
}}</div>
217.118.78.44
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A3%D1%81%D0%BF%D0%B5%D0%BD%D1%81%D0%BA%D0%BE%D0%B3%D0%BE-%D0%A0%D0%B0%D0%B9%D1%81%D0%B0&diff=42061
Свойства перечислимых языков. Теорема Успенского-Райса
2014-12-12T14:07:14Z
<p>217.118.78.44: </p>
<hr />
<div>== Определения ==<br />
<br />
Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> RE </tex>.<br />
{{Определение<br />
|definition='''Свойством языков''' называется множество <tex> A \subset RE </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство называется '''тривиальным''', если <tex> A = \varnothing </tex> или <tex> A = RE </tex>.<br />
}}<br />
{{Определение<br />
|definition='''Язык свойства''' <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p | L(p) \in A \rbrace </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство <tex> A </tex> называется '''разрешимым''', если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].<br />
}}<br />
<br />
== Теорема Успенского-Райса ==<br />
{{Теорема<br />
|statement=<br />
Язык никакого нетривиального свойства не является разрешимым.<br />
|proof=<br />
Приведём доказательство от противного.<br />
<br />
Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.<br />
<br />
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным). <br />
<br />
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.<br />
<br />
Рассмотрим вспомогательную программу:<br />
<tex>g_{i,x}(y):</tex><br />
if U(i, x) == 1<br />
'''return''' <tex>p_X(y)</tex><br />
else<br />
while True<br />
<br />
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:<br />
<tex>US(\langle i, x \rangle )</tex><br />
'''return''' <tex>p_A ( g_{i,x} ) </tex><br />
<br />
Заметим, что<br />
<tex><br />
L(g_{i,x}) = \begin{cases}<br />
X, & U(i, x) = 1; \\<br />
\varnothing, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex><br />
<br />
Следовательно, <br/> <tex> <br />
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}<br />
p_A(p_X), & U(i, x) = 1; \\<br />
p_A(p_\varnothing ), & U(i, x) \neq 1; \\<br />
\end{cases} = \begin{cases}<br />
1, & U(i, x) = 1; \\<br />
0, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex> {{---}} программа, разрешающая универсальное множество. Получили противоречие.<br />
}}</div>
217.118.78.44
http://neerc.ifmo.ru/wiki/index.php?title=%D0%A1%D0%B2%D0%BE%D0%B9%D1%81%D1%82%D0%B2%D0%B0_%D0%BF%D0%B5%D1%80%D0%B5%D1%87%D0%B8%D1%81%D0%BB%D0%B8%D0%BC%D1%8B%D1%85_%D1%8F%D0%B7%D1%8B%D0%BA%D0%BE%D0%B2._%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%A3%D1%81%D0%BF%D0%B5%D0%BD%D1%81%D0%BA%D0%BE%D0%B3%D0%BE-%D0%A0%D0%B0%D0%B9%D1%81%D0%B0&diff=42060
Свойства перечислимых языков. Теорема Успенского-Райса
2014-12-12T14:06:42Z
<p>217.118.78.44: /* Определения */</p>
<hr />
<div>== Определения ==<br />
<br />
Рассмотрим множество всех [[Перечислимые_языки|перечислимых]] языков <tex> RE </tex>.<br />
{{Определение<br />
|definition='''Свойством языков''' называется множество <tex> A \subset RE </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство называется '''тривиальным''', если <tex> A = \varnothing </tex> или <tex> A = RE </tex>.<br />
}}<br />
{{Определение<br />
|definition='''Язык свойства''' <tex> A </tex> {{---}} множество программ, языки которых обладают этим свойством: <tex>L(A) \overset{\underset{\mathrm{def}}{}}{=} \lbrace p | L(p) \in A \rbrace </tex>.<br />
}}<br />
{{Определение<br />
|definition=Свойство <tex> A </tex> называется '''разрешимым''', если <tex>L(A) </tex> является [[Разрешимые_(рекурсивные)_языки|разрешимым]].<br />
}}<br />
<br />
= Теорема Успенского-Райса=<br />
{{Теорема<br />
|statement=<br />
Язык никакого нетривиального свойства не является разрешимым.<br />
|proof=<br />
Приведём доказательство от противного.<br />
<br />
Предположим, что <tex>A</tex> разрешимо и нетривиально, <tex>p_A</tex> {{---}} программа, разрешающая <tex>A</tex>.<br />
<br />
Не умаляя общности, можно считать, что <tex>\varnothing \notin A</tex> (в противном случае перейдём к <tex>RE \setminus A</tex>, которое также будет разрешимым и нетривиальным). <br />
<br />
Поскольку <tex>A</tex> непусто, то найдётся перечислимый язык <tex>X \in A</tex>. Пусть <tex>p_X</tex> {{---}} полуразрешитель <tex>X</tex>.<br />
<br />
Рассмотрим вспомогательную программу:<br />
<tex>g_{i,x}(y):</tex><br />
if U(i, x) == 1<br />
'''return''' <tex>p_X(y)</tex><br />
else<br />
while True<br />
<br />
Нетрудно понять, что в разумной модели вычислений номер этой программы можно вычислить по данным <tex>i</tex> и <tex>x</tex>. Значит, можно рассмотреть такую программу:<br />
<tex>US(\langle i, x \rangle )</tex><br />
'''return''' <tex>p_A ( g_{i,x} ) </tex><br />
<br />
Заметим, что<br />
<tex><br />
L(g_{i,x}) = \begin{cases}<br />
X, & U(i, x) = 1; \\<br />
\varnothing, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex><br />
<br />
Следовательно, <br/> <tex> <br />
US(\langle i, x \rangle ) = p_A(g_{i,x}) = \begin{cases}<br />
p_A(p_X), & U(i, x) = 1; \\<br />
p_A(p_\varnothing ), & U(i, x) \neq 1; \\<br />
\end{cases} = \begin{cases}<br />
1, & U(i, x) = 1; \\<br />
0, & U(i, x) \neq 1; \\<br />
\end{cases}<br />
</tex> {{---}} программа, разрешающая универсальное множество. Получили противоречие.<br />
}}</div>
217.118.78.44