Диагональный метод — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
Строка 1: Строка 1:
{| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
 
|+
 
|-align="center"
 
|'''НЕТ ВОЙНЕ'''
 
|-style="font-size: 16px;"
 
|
 
24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
 
 
Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
 
 
Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
 
 
Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
 
 
''Антивоенный комитет России''
 
|-style="font-size: 16px;"
 
|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
 
|-style="font-size: 16px;"
 
|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
 
|}
 
 
 
{{Определение
 
{{Определение
 
|definition = Функция <tex>U : N \times N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''универсальной (universal function)''' для класса [[Вычислимые функции|вычислимых функций]] одного аргумента, если <tex>\forall n \in N</tex> <tex>U_n(x) = U(n, x)</tex> является вычислимой функцией и <tex>\forall</tex> вычислимой функции <tex>f</tex> <tex>\exists n \in N : f(x) = U(n, x)</tex>
 
|definition = Функция <tex>U : N \times N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''универсальной (universal function)''' для класса [[Вычислимые функции|вычислимых функций]] одного аргумента, если <tex>\forall n \in N</tex> <tex>U_n(x) = U(n, x)</tex> является вычислимой функцией и <tex>\forall</tex> вычислимой функции <tex>f</tex> <tex>\exists n \in N : f(x) = U(n, x)</tex>

Текущая версия на 19:19, 4 сентября 2022

Определение:
Функция [math]U : N \times N \rightarrow N \cup \lbrace \bot \rbrace[/math] называется универсальной (universal function) для класса вычислимых функций одного аргумента, если [math]\forall n \in N[/math] [math]U_n(x) = U(n, x)[/math] является вычислимой функцией и [math]\forall[/math] вычислимой функции [math]f[/math] [math]\exists n \in N : f(x) = U(n, x)[/math]

Менее формально, для универсальной функции должно выполняться следующее: "сечение" функции [math] U_n [/math] является вычислимой функцией и все вычислимые функции одного аргумента встречаются среди [math]U_n[/math] (отсюда универсальность). Универсальная функция нужна, например, для того, чтобы показать, что существует перечислимое неразрешимое множество (на самом деле это множество таких [math] n [/math], для которых [math] U(n, n) [/math] определено).

Аналогично определяется универсальная функция для класса всюду определенных вычислимых функций одного аргумента.

Теорема:
Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.
Доказательство:
[math]\triangleright[/math]
Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию [math]U(n, x) = p_n(x)[/math], где [math]p_n[/math][math]n[/math]-ая программа в указанной нумерации. [math]\forall[/math] вычислимой функции [math]f[/math] [math]\exists n \in N : f(x) = p_n(x) = U(n, x)[/math]. [math]\forall n \in N[/math] [math]U_n(x) = U(n, x) = p_n(x)[/math], очевидно, является вычислимой функцией. Значит [math]U(n, x)[/math] — универсальная функция для класса вычислимых функций одного аргумента. Очевидно, что [math]U(n, x)[/math] вычислима. Действительно, для того, чтобы вычислить [math]U(n, x)[/math], достаточно вернуть вывод программы [math]p_n[/math] на входе [math]x[/math].
[math]\triangleleft[/math]
Теорема:
Для класса всюду определенных вычислимых функций одного аргумента не существует всюду определенной вычислимой универсальной функции.
Доказательство:
[math]\triangleright[/math]
От противного. Пусть [math]U(n, x)[/math] — всюду определенная вычислимая универсальная функция для класса всюду определенных вычислимых функций одного аргумента. Воспользуемся теперь диагональным методом. Рассмотрим всюду определенную вычислимую функцию одного аргумента [math]d(x) = U(x, x) + 1[/math]. [math]\exists n \in N : d(x) = U(n, x)[/math] в силу того, что [math]U(n, x)[/math] — универсальная для соответствующего класса функций. Так как [math]d(x)[/math] всюду определена, то она не зависает на аргументе [math]n[/math]. Значит [math]d(n) = U(n, n)[/math], но в то же время [math]d(n) = U(n, n) + 1[/math]. Противоречие.
[math]\triangleleft[/math]

Отметим, что функция [math]u(n) = U(n, n)[/math] называется диагональной (отсюда и пошло название метода).

Литература

Н. К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции. — М.: МЦНМО, 1999, с. 16

В. А. Успенский Лекции о вычислимых функциях — М.: ГИФМЛ, 1960, с. 203