Диагональный метод - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:19:06Z

rollbackEdits.php mass rollback

171.25.193.80 в 05:27, 1 сентября 2022

2022-09-01T05:27:50Z

Demid.Kucherenko: /* Литература */

2014-01-13T11:39:26Z

‎Литература

Demid.Kucherenko в 11:38, 13 января 2014

2014-01-13T11:38:04Z

Demid.Kucherenko в 11:31, 13 января 2014

2014-01-13T11:31:46Z

Demid.Kucherenko в 11:30, 13 января 2014

2014-01-13T11:30:38Z

Demid.Kucherenko в 10:57, 13 января 2014

2014-01-13T10:57:36Z

178.66.15.59 в 10:54, 13 января 2014

2014-01-13T10:54:44Z

192.168.0.2 в 14:15, 24 января 2012

2012-01-24T14:15:39Z

192.168.0.2 в 23:31, 17 декабря 2011

2011-12-17T23:31:06Z

← Предыдущая		Версия 16:19, 4 сентября 2022
Строка 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>

← Предыдущая		Версия 05:27, 1 сентября 2022
Строка 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>

← Предыдущая		Версия 11:39, 13 января 2014
Строка 18:		Строка 18:

	''В. А. Успенский'' '''Лекции о вычислимых функциях''' — М.: ГИФМЛ, 1960, с. 203		''В. А. Успенский'' '''Лекции о вычислимых функциях''' — М.: ГИФМЛ, 1960, с. 203
−
−	~~[[Категория: Теория формальных языков]]~~
−	~~[[Категория: Теория вычислимости]]~~

@@ Строка 2: / Строка 2: @@
 |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>
 }}
 Аналогично определяется универсальная функция для класса всюду определенных вычислимых функций одного аргумента.
 {{Теорема

@@ Строка 11: / Строка 11: @@
 |proof = От противного. Пусть <tex>U(n, x)</tex> — всюду определенная вычислимая универсальная функция для класса всюду определенных вычислимых функций одного аргумента. Воспользуемся теперь диагональным методом. Рассмотрим всюду определенную вычислимую функцию одного аргумента <tex>d(x) = U(x, x) + 1</tex>. <tex>\exists n \in N : d(x) = U(n, x)</tex> в силу того, что <tex>U(n, x)</tex> — универсальная для соответствующего класса функций. Так как <tex>d(x)</tex> всюду определена, то она не зависает на аргументе <tex>n</tex>. Значит <tex>d(n) = U(n, n)</tex>, но в то же время <tex>d(n) = U(n, n) + 1</tex>. Противоречие.
 }}
-Отметим, что функция <tex>u(n) = U(n, n)</tex> называется диагональной функцией (отсюда и пошло название метода).
+Отметим, что функция <tex>u(n) = U(n, n)</tex> называется диагональной (отсюда и пошло название метода).
 == Литература ==
 [http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf ''Н. К. Верещагин,  А. Шень.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.''' — М.: МЦНМО, 1999, с. 16]

@@ Строка 1: / Строка 1: @@
 {{Определение
-|definition = Функция <tex>U : N \times N \rightarrow N \cup \lbrace \bot \rbrace</tex> называется '''универсальной''' для класса [[Вычислимые функции|вычислимых функций]] одного аргумента, если <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>
 }}
 Аналогично определяется универсальная функция для класса всюду определенных вычислимых функций одного аргумента.

@@ Строка 5: / Строка 5: @@
 {{Теорема
 |statement = Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.
-|proof = Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию <tex>U(n, x) = p_n(x)</tex>, где <tex>p_n</tex> — <tex>n</tex>-ая программа в указанной нумерации. <tex>\forall</tex> вычислимой функции <tex>f</tex> <tex>\exists n \in N : f(x) = p_n(x) = U(n, x)</tex>. <tex>\forall n \in N</tex> <tex>U_n(x) = U(n, x) = p_n(x)</tex>, очевидно, является вычислимой функцией. Значит <tex>U(n, x)</tex> — универсальная функция для класса вычислимых функций одного аргумента. Очевидно, что <tex>U(n, x)</tex> вычислима. Действительно, для того, чтобы вычислить <tex>U(n, x)</tex> достаточно вернуть вывод программы <tex>p_n</tex> на входе <tex>x</tex>.
+|proof = Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию <tex>U(n, x) = p_n(x)</tex>, где <tex>p_n</tex> — <tex>n</tex>-ая программа в указанной нумерации. <tex>\forall</tex> вычислимой функции <tex>f</tex> <tex>\exists n \in N : f(x) = p_n(x) = U(n, x)</tex>. <tex>\forall n \in N</tex> <tex>U_n(x) = U(n, x) = p_n(x)</tex>, очевидно, является вычислимой функцией. Значит <tex>U(n, x)</tex> — универсальная функция для класса вычислимых функций одного аргумента. Очевидно, что <tex>U(n, x)</tex> вычислима. Действительно, для того, чтобы вычислить <tex>U(n, x)</tex>, достаточно вернуть вывод программы <tex>p_n</tex> на входе <tex>x</tex>.
 }}
 {{Теорема