Универсальная функция - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:38:28Z

rollbackEdits.php mass rollback

23.128.248.38 в 03:50, 1 сентября 2022

2022-09-01T03:50:24Z

188.143.145.59: /* Определение универсальной функции */

2016-11-10T18:45:58Z

‎Определение универсальной функции

188.143.145.59: /* Определение универсальной функции */

2016-11-10T18:45:28Z

‎Определение универсальной функции

188.143.145.59: /* Существование универсальной функции */

2016-11-03T09:15:52Z

‎Существование универсальной функции

188.143.145.59: /* Определение универсальной функции */

2016-11-03T08:44:39Z

‎Определение универсальной функции

188.143.145.59 в 12:40, 1 ноября 2016

2016-11-01T12:40:14Z

188.143.145.59 в 12:38, 1 ноября 2016

2016-11-01T12:38:11Z

188.143.145.59 в 12:24, 1 ноября 2016

2016-11-01T12:24:13Z

188.143.145.59 в 12:15, 1 ноября 2016

2016-11-01T12:15:05Z

← Предыдущая		Версия 16:38, 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 Майкл Наки].
−	\|}
−
	==Определение универсальной функции==		==Определение универсальной функции==
	{{Определение		{{Определение

← Предыдущая		Версия 03:50, 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 Майкл Наки].
		+	\|}
		+
	==Определение универсальной функции==		==Определение универсальной функции==
	{{Определение		{{Определение

@@ Строка 3: / Строка 3: @@
 |definition =
 Две '''вычислимые функции''' (англ. ''computable function'') <tex>f_1</tex> и <tex>f_2</tex> равны при заданных аргументах, если при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими:
-*<tex>f_1(n) = f_2(n)</tex>
+*<tex>f_1(x) = f_2(x)</tex>
-*<tex>f_1(n) = \bot</tex> и <tex> f_2(n) = \bot</tex>
+*<tex>f_1(x) = \bot</tex> и <tex> f_2(x) = \bot</tex>
 }}
 {{Определение

@@ Строка 2: / Строка 2: @@
 {{Определение
 |definition =
-Две '''вычислимые функции''' (англ. ''computable function'') равны при заданных аргументах, если при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими.
+Две '''вычислимые функции''' (англ. ''computable function'') <tex>f_1</tex> и <tex>f_2</tex> равны при заданных аргументах, если при этих аргументах вычисляющие программы для этих функций зависают, либо равны значения, возвращаемые ими:
 }}
 {{Определение

@@ Строка 16: / Строка 16: @@
 {{Теорема
 |statement=Существует универсальная функция для класса вычислимых функций одного аргумента.
-|proof=Зафиксируем какой-либо язык программирования. Пусть программами на этом языке являются слова над алфавитом <tex>\Sigma</tex>. Программа будет иметь номер <tex>n</tex>, если ее код {{---}} <tex>n</tex>-е слово среди всех слов над алфавитом <tex>\Sigma</tex>, отсортированных сначала по возрастанию длины, а при равной длине {{---}} в лексикографическом порядке. При этом если <tex>n</tex>-я программа не компилируется, будем считать, что она всегда зависает. Рассмотрим функцию <tex>U(n,x):\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}\cup\perp</tex> такую, что <tex>U(n,x)=p_n(x)</tex>, где <tex>p_n</tex> {{---}} <tex>n</tex>-я программа. Заметим, что по определению вычислимой функции существует программа, вычисляющая ее. Но в заданной нумерации у любой программы есть номер. Таким образом для любой вычислимой функции <tex>f</tex> существует номер <tex>n: U(n,x)=f(x)</tex>. И наоборот {{---}} <tex>f_n=U(n)</tex> является вычислимой функцией. Вычисляющая программа для <tex>U</tex> содержит интерпретатор для зафиксированного языка программирования, по номеру программы (первый аргумент) восстанавливает ее код, и передает ей второй аргумент, возвращая результат ее работы. Таким образом <tex>U_n(x)=U(n,x)</tex> {{---}} вычислима для любого <tex>n\in\mathbb{N}</tex>, и <tex>\forall f(x) \exists n\in\mathbb{N}: f(x)=U(n,x)</tex>, <tex>f(x)</tex> {{---}} вычислима, значит U(n,x) {{---}} универсальная функция.
+|proof=Зафиксируем какой-либо язык программирования. Пусть программами на этом языке являются слова над алфавитом <tex>\Sigma</tex>. Программа будет иметь номер <tex>n</tex>, если ее код {{---}} <tex>n</tex>-е слово среди всех слов над алфавитом <tex>\Sigma</tex>, отсортированных сначала по возрастанию длины, а при равной длине {{---}} в лексикографическом порядке. При этом если <tex>n</tex>-я программа не компилируется, будем считать, что она всегда зависает. Рассмотрим функцию <tex>U(n,x):\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{N}\cup\perp</tex> такую, что <tex>U(n,x)=p_n(x)</tex>, где <tex>p_n</tex> {{---}} <tex>n</tex>-я программа. Заметим, что по определению вычислимой функции существует программа, вычисляющая ее. Но в заданной нумерации у любой программы есть номер. Таким образом для любой вычислимой функции <tex>f</tex> существует номер <tex>n: U(n,x)=f(x)</tex>. И наоборот {{---}} <tex>f_n=U(n)</tex> является вычислимой функцией. Вычисляющая программа для <tex>U</tex> содержит интерпретатор для зафиксированного языка программирования, по номеру программы (первый аргумент) восстанавливает ее код, и передает ей второй аргумент, возвращая результат ее работы. Таким образом <tex>U_n(x)=U(n,x)</tex> {{---}} вычислима для любого <tex>n\in\mathbb{N}</tex>, и <tex>\forall f(x) \exists n\in\mathbb{N}: f(x)=U(n,x)</tex>, <tex>f(x)</tex> {{---}} вычислима, значит <tex>U(n,x)</tex> {{---}} универсальная функция.
 }}

@@ Строка 73: / Строка 73: @@
 * [[Неотделимые множества]]
 * [[Свойства перечислимых языков. Теорема Успенского-Райса]]
+* [[Теорема о рекурсии]]
 == Источники информации ==
 * [http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf ''Н. К. Верещагин,  А. Шень.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.''' — М.: МЦНМО, 1999, с. 16. ISBN 5-900916-36-7 ]

@@ Строка 70: / Строка 70: @@
 не определённая функция имела единственный номер. Пусть <tex>U(n,x)</tex>- произвольная вычислимая универсальная функция.
 Теперь возьмем перечислимое множество <tex>D</tex> всех  <tex>U</tex>-номеров всех функций таких, что их область определения непуста. Пусть функция <tex>d</tex> есть всюду определенная функция перечисляющая множество <tex>D</tex>. Рассмотрим функцию <tex>V(i, x)</tex>, для которой <tex>V(0, x)</tex> не определено ни при каком <tex>x</tex>, а <tex>V(i+1, x) = U(d(i), x)</tex>. То есть, функция <tex>V_0</tex> нигде не определена, а функция <tex>V_{i+1}</tex> совпадает с <tex>U_{d(i)}</tex>. Очевидно, функция <tex>V</tex> вычислима и универсальна (по построению), а единственным <tex>V</tex>-номером нигде не определённой функции является число <tex>0</tex>. Тогда нумерация, соответствующая этой функции является неглавной.
-b    z
+== См. также ==
 == Источники информации ==
 * [http://www.mccme.ru/free-books/shen/shen-logic-part3-2.pdf ''Н. К. Верещагин,  А. Шень.'' '''Лекции по математической логике и теории алгоритмов. Часть 3. Вычислимые функции.''' — М.: МЦНМО, 1999, с. 16. ISBN 5-900916-36-7 ]

@@ Строка 5: / Строка 5: @@
 }}
 {{Определение
-|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>U</tex> при фиксированном <tex>n</tex>) является вычислимой функцией и для любой вычислимой функции <tex>f</tex> <tex>\exists n \in N : f(x) = U(n, x)</tex>.
+|definition = Функция <tex>U : \mathbb{N}\ \times \mathbb{N}\ \rightarrow \mathbb{N}\ \cup \lbrace \bot \rbrace</tex> называется '''универсальной '''(англ. ''universal function'') для класса [[Вычислимые функции|вычислимых функций]] одного аргумента, если <tex>\forall n \in \mathbb{N}\</tex>  <tex>U_n(x) = U(n, x)</tex> («сечение» функции <tex>U</tex> при фиксированном <tex>n</tex>) является вычислимой функцией и для любой вычислимой функции <tex>f</tex> <tex>\exists n \in \mathbb{N}\ : f(x) = U(n, x)</tex>.
 }}
 Менее формально, для универсальной функции должно выполняться следующее: «сечение»  функции <tex> U_n </tex> является вычислимой функцией и все вычислимые функции одного аргумента встречаются среди <tex>U_n</tex> (отсюда универсальность). Универсальная функция нужна, например, для того, чтобы показать, что существует перечислимое неразрешимое множество (на самом деле это множество таких <tex> n </tex>, для которых <tex> U(n, n) </tex> определено).
@@ Строка 22: / Строка 22: @@
 {{Теорема
 |statement = Для класса вычислимых функций одного аргумента существует вычислимая универсальная функция.
-|proof = Занумеруем программы нашего языка натуральными числами. Рассмотрим функцию <tex>U(n, x) = p_n(x)</tex>, где <tex>p_n</tex> — <tex>n</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>f</tex> <tex>\exists n \in \mathbb{N}\ : f(x) = p_n(x) = U(n, x)</tex>. <tex>\forall n \in \mathbb{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>.
 }}
 {{Теорема
 |statement = Для класса всюду определенных вычислимых функций одного аргумента не существует всюду определенной вычислимой универсальной функции.
-|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>. Противоречие.
+|proof = Докажем от противного. Пусть <tex>U(n, x)</tex> — всюду определенная вычислимая универсальная функция для класса всюду определенных вычислимых функций одного аргумента. Воспользуемся теперь диагональным методом. Рассмотрим всюду определенную вычислимую функцию одного аргумента <tex>d(x) = U(x, x) + 1</tex>. <tex>\exists n \in \mathbb{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> называется диагональной (отсюда и пошло название метода).

@@ Строка 32: / Строка 32: @@
 ==Главная нумерация==
 {{Определение
-|definition='''Нумерация (numbering)''' множества <tex>X-</tex> это такое всюду определенное отображение <tex> f : \mathbb{N} \rightarrow X</tex>, область значений которого есть все множество <tex>X</tex>.
+|definition= '''Нумерация''' (англ. ''numbering'') множества <tex>X-</tex> это такое всюду определенное отображение <tex> f : \mathbb{N} \rightarrow X</tex>, область значений которого есть все множество <tex>X</tex>.
 }}