http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&feedformat=atom&user=178.66.15.59&* 2026-05-21T00:19:32Z Вклад участника MediaWiki 1.30.0 http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B8%D0%B0%D0%B3%D0%BE%D0%BD%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%BC%D0%B5%D1%82%D0%BE%D0%B4&diff=35561 2014-01-13T10:54:44Z

<p>178.66.15.59: </p> <hr /> <div>{{Определение<br /> |definition = Функция &lt;tex&gt;U : N \times N \rightarrow N \cup \lbrace \bot \rbrace&lt;/tex&gt; называется '''универсальной''' для класса [[Вычислимые функции|вычислимых функций]] одного аргумента, если &lt;tex&gt;\forall n \in N&lt;/tex&gt; &lt;tex&gt;U_n(x) = U(n, x)&lt;/tex&gt; является вычислимой функцией и &lt;tex&gt;\forall&lt;/tex&gt; вычислимой функции &lt;tex&gt;f&lt;/tex&gt; &lt;tex&gt;\exists n \in N : f(x) = U(n, x)&lt;/tex&gt;<br /> }}<br /> Аналогично определяется универсальная функция для класса всюду определенных вычислимых функций одного аргумента.<br /> {{Теорема<br /> |statement = Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.<br /> |proof = Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию &lt;tex&gt;U(n, x) = p_n(x)&lt;/tex&gt;, где &lt;tex&gt;p_n&lt;/tex&gt; — &lt;tex&gt;n&lt;/tex&gt;-ая программа в указанной нумерации. &lt;tex&gt;\forall&lt;/tex&gt; вычислимой функции &lt;tex&gt;f&lt;/tex&gt; &lt;tex&gt;\exists n \in N : f(x) = p_n(x) = U(n, x)&lt;/tex&gt;. &lt;tex&gt;\forall n \in N&lt;/tex&gt; &lt;tex&gt;U_n(x) = U(n, x) = p_n(x)&lt;/tex&gt;, очевидно, является вычислимой функцией. Значит &lt;tex&gt;U(n, x)&lt;/tex&gt; — универсальная функция для класса вычислимых функций одного аргумента. Очевидно, что &lt;tex&gt;U(n, x)&lt;/tex&gt; вычислима. Действительно, для того, чтобы вычислить &lt;tex&gt;U(n, x)&lt;/tex&gt;, достаточно вернуть вывод программы &lt;tex&gt;p_n&lt;/tex&gt; на входе &lt;tex&gt;x&lt;/tex&gt;.<br /> }}<br /> {{Теорема<br /> |statement = Для класса всюду определенных вычислимых функций одного аргумента не существует всюду определенной вычислимой универсальной функции.<br /> |proof = От противного. Пусть &lt;tex&gt;U(n, x)&lt;/tex&gt; — всюду определенная вычислимая универсальная функция для класса всюду определенных вычислимых функций одного аргумента. Воспользуемся теперь диагональным методом. Рассмотрим всюду определенную вычислимую функцию одного аргумента &lt;tex&gt;d(x) = U(x, x) + 1&lt;/tex&gt;. &lt;tex&gt;\exists n \in N : d(x) = U(n, x)&lt;/tex&gt; в силу того, что &lt;tex&gt;U(n, x)&lt;/tex&gt; — универсальная для соответствующего класса функций. Так как &lt;tex&gt;d(x)&lt;/tex&gt; всюду определена, то она не зависает на аргументе &lt;tex&gt;n&lt;/tex&gt;. Значит &lt;tex&gt;d(n) = U(n, n)&lt;/tex&gt;, но в то же время &lt;tex&gt;d(n) = U(n, n) + 1&lt;/tex&gt;. Противоречие.<br /> }}<br /> == Литература ==<br /> [http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf ''Н. К. Верещагин, А. Шень.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.''' — М.: МЦНМО, 1999, с. 16]<br /> <br /> ''В. А. Успенский'' '''Лекции о вычислимых функциях''' — М.: ГИФМЛ, 1960, с. 203<br /> <br /> [[Категория: Теория формальных языков]]<br /> [[Категория: Теория вычислимости]]</div>

178.66.15.59