Please enable JavaScript.

Coggle requires JavaScript to display documents.

Logic (Formal arithmetic: (Arithmetical Hierarchy, Oracle Computability,…

- - - - Equivalent definitions: founded sets
        
        Every decreasing chain has the smallest element
        
        Induction principle holds
        
        Every non-empty subset contains minimal element
    - - Comparability theorem: given any two well-ordered sets, one of them is necessarily isomorphic to initial segment of another
  - - - Non-trivial additive functions from R to R exist
- - - - Правила перехода между конфигурациями:
        \(AqaB \rightarrow CrcD\)
        
        Для каждой конфигурации есть только одна следующая конфигурация!
        
        Перезаписать и остаться на месте: \(C = A, D = B\), программа содержит инструкцию \(qa \rightarrow rcN\)
        
        Перезаписать и сдвинуться вправо: \(C = Ab, B = cD,\lor B = D = \epsilon, c = \#\), программа содержит инструкцию \(qa\rightarrow rbR\)
        
        Перезаписать и сдвинуться влево: \(D = bC, A = Cс,\lor A = C = \epsilon, c = \#\), программа содержит инструкцию \(qa\rightarrow rbL\)
    - - Вычислимые функции:
        Функции, для которых существует программа, вычисляющая их за конечное количество шагов на аргументах из области определения и не останавливающаяся на всех остальных.
        Или же функция, график которой перечислим.
        
        Композиция вычислимых функций вычислима.
        
        Разрешимые множества: существует алгоритм, проверяющий принадлежность
        Множество \(A\) называется разрешимым, если существует машина Тьюринга \(M\), которая останавливается на любом входе, причём \(x \in A \implies M(x) = 1, \\ x \not\in A \implies M(x) = 0\)
        Иными словами, множество разрешимо, если существует не зацикливающаяся машина, различающая его.
        Что эквивалентно: множество А разрешимо согда вычислима его характеристическая функция (такое определение не требует никаких бесконечно долго работающих алгоритмов).
        
        \(A, B\) — разрешимы \(\implies A \cup B, A \cap B, \overline{A}, A \times B\) разрешимы. Эквивалентно, разрешимые множества замкнуты относительно конечных теоретико-множественных операций.
        
        Класс перечислимых множеств не замкнут относительно счётного пересечения:
        
        Рассмотрим некоторое перечислимое, но неразрешимое множество \(K\) и его дополнение \(\overline{K}\).
        
        \(\forall k \in \overline{K} \ N_{k} := \mathbb{N} \setminus \{k\}\) — каждое такое множество разрешимо (т.к. характеристическая функция будет просто сравнением с выброшенным элементом)
        
        \(\cap{k \in \overline{K}{N{k}} = K) — неразрешимо по построению.
        
        Теорема Поста:
        \(A\) разрешимо тогда и только тогда, когда \(A, \overline{A}\) перечислимы.
        Доказательство: Пусть \(\mathbb{M}_{1}, \mathbb{M}_{2}\) — машины, перечисляющие \(A\) и \(\overline{A}\). Построим машину \(\mathrm{N}\), различающую их. Будем запускать на каждом шаге сначала первую, а потом вторую машину на один шаг, пока одна из них не выведет нужное нам значение. Таким образом можно проверить принадлежность множеству любого натурального числа, т.к. перечислимость гарантирует, что нужно все элементы множеств рано или поздно будут выведены.
        
        Infinite set of natural numbers is decidable iff it is an image of monotone function. #
        
        S = {\(n \in \mathbb{N}\) | десятичная запись \(\mathrm{e}\) содержит n подряд идущих 9-к} разрешимо
        Доказательство:
        
        Заметим, что \(0 \in S\).
        
        Заметим, что S вполне упорядочено со стандартным порядком на \(\mathbb{N}\): \(n \in S \iff \forall m < n: \ m \in S\).
        
        Значит, характеристическая функция \(S\) всюду определена и не убывает: она либо всюду равна 1, либо, начиная с некоторого момента, всюду равна 0.
        
        Всякая всюду определённая невозрастающая арифметическая функция вычислима, следовательно, вычислима характеристическая функция \(\chi_{S}\), что эквивалентно разрешимости множества \(S\). #
        
        Если множество \(A \subset \mathbb{N}\) бесконечно и разрешимо, то существует вычислимая всюду определённая возрастающая арифметическая функция \(f\), т.ч. \(f(\mathbb{N}) = A\): #
        
        Всякое бесконечное перечислимое множество содержит бесконечное разрешимое подмножество: :warning:
        
        Существует всюду определённая невычислимая функция:
        Функция вычислима, если она реализуется программой на машине Тьюринга. Программ (как конечных последовательностей символов алфавита) — счётное множество, функций из \(\mathbb{N} \rightarrow \mathbb{N}\) — несчётное множество, следовательно, такая функция должна быть из соображений мощности.
        Более конструктивное доказательство предлагает занумеровать все программы, а затем составить бесконечную таблицу, в строках которой будут программы, в столбцах — аргументы, в клетках — результат работы программы на данном аргументе, и использовать диагональный метод Кантора. Рассмотрим диагональ и заменим в ней каждое число на следующее за ним (undefined — на 0). Получим тогда программу, отличную от всех занумерованных, что невозможно, т.к. их множество счётно и содержит все вычислимые по свойству у.в.ф. Значит, отображение \(\mathbb{N}\) на эту диагональ невычислимо по построению. #
        
        Универсальные вычислимые функции:
        \(U : \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}\) называется универсальной для семейства функций \(\mathrm{C}\) из \(\mathbb{N}\) в \(\mathbb{N}\), если
        
        \(\forall n \in \mathbb{N} \ \phi(x) = U(n, x) \in \mathrm{C}\) — как функция одной переменной лежит в семействе при всех номерах
        
        \(\forall f \in \mathrm{C} \ \exists n \in \mathbb{N}: \forall x \ f(x) = U(n, x)\) — для любой функции семейства найдётся номер
        
        На универсальную вычислимую функцию можно смотреть как на универсальный язык программирования: универсальность означает, что на этом языке можно запрограммировать реализацию любой вычислимой функции.
        In set theory, the set \(W \subset \mathbb{N} \times \mathbb{N}\) is called universal for some class of natural numbers \(\iff \forall n \in \mathbb{N} W_{n} = \{x \ | \ (n, x) \in W\}\) are contained in that class, and there are no other sets in the class.
        
        Теорема об интерпретаторе:
        Существует универсальная функция для множества всех вычислимых арифметических функций. (достаточно построить универсальную машину Тьюринга \(U(n, x) = p_{n}(x)\) для некоторой нумерации программ)
        
        Не существует универсальной вычислимой функции двух переменных для класса всех всюду определённых вычислимых функций.
        И вновь применим диагональный метод Кантора (было бы очень хорошо понять, как это доказательство придумать самому). Предположим, что такая функция существует. Выпишем бесконечную таблицу, где по оси ординат отложим номер функции, а по оси ординат — аргумнеты. Рассмотрим диагональ таблицы: функцию \(d(n) = U(n, n)\). Она тоже вычислима и всюду определена (первая часть определения). Но тогда и функция \(d'(n) = d(n) + 1\) тоже вычислима и всюду определена. Тогда, по определению (вторая его часть) универсальной функции \(\exists n_{0} \in \mathbb{N}:\ \forall x \ d'(x) = U(n_{0}, x)\).
        Подставим в полученном равенстве \(x = n_{0}\). Тогда:
        \(U(n_{0}, n_{0}) = U(n_{0}, n_{0}) + 1\), что невозможно. Значит (почему?), \(U(n, n)\) невычислима, множество \(\{n \ | \ \{U(n, n) \ определено\}\) неразрешимо, а функция \(U\) не может быть гёделевой.
        Corollary: there is a computable function, such that no computable functions differs from it on every possible input (it's exactly that diagonal function from the proof above).
        #
        
        Для любой у.в.ф. \(U\) мн-во \(H = \{ n \in \mathbb{N} \ | \ U(n, n) \) определено} перечислимо, но не разрешимо:
        Доказательство:
        Неразрешимость — следствие проблемы останова.
        Перечислимость следует из того, что можно в качестве вычислимой полухарактеристической функции взять \(\chi_{H}(x) = min(undefined, U(n, n))\).
        
        Главная (Гёделева) универсальная вычислимая функция:
        \(\forall V: \mathbb{N} \times \mathbb{N} \rightarrow \mathbb{N}, V\) — вычислима \(\implies \exists t: \mathbb{N} \rightarrow \mathbb{N}\) — всюду определённая и вычислимая: \(\forall n, x \ U(t(n), x) = V(n, x)\) В случае просто универсальной вычислимой функции в роли \(t\) выступает тождественная функция.
        Только для главных нумераций можно вычислять номер любой композиции по номерам образующих её функций.
        
        Теорема о компиляторе:
        Существует гёделева универсальная вычислимая арифметическая функция.
        Для главных универсальных функций можно доказать многие важные свойства, выполненные для Тьюринг-полных языков программирования.
        
        Теорема Райса-Успенского: нельзя распознать, при каких номерах гёделева универсальная вычислимая функция порождает функции некоторого семейства вычислимых
        Proof: Suppose the contrary and show, that it's reducible to the halting problem which is known to be undecidable.
        Пусть \(U(n, x)\) — некоторая гёделева универсальная вычислимая функция и \(\mathrm{F}\) — нетривиальное семейство вычислимых арифметических функций. Тогда множество \(\mathrm{N} = \{n \ | \ \phi(x) = U(n, x) \in \mathrm{F}\}\) неразрешимо.
        
        Предположим противное, тогда должно быть разрешимо множество \(\mathrm{K} = \{n \ | \ \{U(n, n) \ определено\}\), т.к. можно написать программу \(\pi_{n}\), которая будет пытаться вычислить сначала \(U(n, n)\) (здесь может произойти зацикливание; в таком случае можно считать, что мы имитируем нигде не определённую вычислимую функцию \(\xi_{0}\), не ограничивая общности рассуждений, из \(\mathrm{F}\)), а потом — \(\xi_{1}\), вычислимую функцию не из \(\mathrm{F}\) (а почему вдруг зацикливание не может произойти здесь? нужно потребовать, чтобы эта функция была определена хотя бы где-то; похоже, именно это требование удовлетворяется выбором \(\xi_{0}\)).
        
        \(n \in \mathrm{K} \implies id(\pi_{n}) \in \mathrm{N} \\ n \not\in \mathrm{K} \implies id(\pi_{n}) \not\in \mathrm{N}\),
        следовательно, если есть алгоритм, распознающий элементы \(\mathrm{N}\), то есть и алгоритм, распознающий \(\mathrm{K}\), в то время как оно неразрешимо. Противоречие.
        Также можно доказать, что если утверждение теоремы Райса-Успенского выполнено хотя бы для одной главной универсальной вычислимой функции, то оно верно и для всех остальных.
        
        Нельзя алгоритмические проверить, способен ли данный универсальный алгоритм вычислить такую-то функцию из вычислимого семейства.
        All non-trivial semantic properties of programs are undecidable (f.e. does the program terminate for all inputs, or does it terminate on some particular input).
        
        Множество программ, задающих нигде не определённую функцию, неперечислимо.
        Т.к. перечислимо множество программ, определённых хотя бы на одном входе, а далее работает теорема Успенского-Райса (множество программ неразрешимо) и теорема Поста (если и множество, и его дополнение перечислимы, то само множество разрешимо).
        
        Множество номеров программ, задающих всюду определённые функции, неразрешимо.
        
        m-сводимость (many-one reduction): когда задачу о принадлежности множеству \(A\) можно свести к задачу о принадлежности множеству \(B\)?
        A reduction is a way of converting one problem to another problem such that solution for the second (simpler) problem can be used to solve the first problem. As an example of m-reduction consider a situation when you need to find your way around the city. This problem can be reduced to a problem of obtaining its map.
        f — вычислима, \(A \subset \mathbb{N} \leq_{m} B \subset \mathbb{N} \iff \exists f: \mathbb{N} \rightarrow \mathbb{N}: \ ( x \in A \iff f(x) \in B)\)
        Properties:
        
        \(\forall A \subset \mathbb{N} \ A \le_{m} A\)
        
        \(A \leq_{m} B, B \leq_{m} C \implies A \leq_{m} C\)
        
        \(A \leq_{m} B \implies (\mathbb{N} \setminus A) \leq_{m} (\mathbb{N} \setminus B)\)
        
        \(A \ is \ decidable, B \neq \emptyset, B \neq \mathbb{N} \implies A \leq_{m} B\)
        
        \(A \leq_{m} B, B \ is \ decidable \implies A \ is \ decidable\)
        
        \(A \leq_{m} B, B \ is \ enumerative \implies A \ is \ enumerative\)
        
        Заметим, что отношение m-сводимости не является ни симметричным, ни антисимметричным, т.е. задаёт только предпорядок.
        Доказательства, использующие m-сводимость, опираются на главность нумерации.
        
        m-complete set:
        \(\mathrm{C}\) — family of subsets of natural numbers. \(A\) is m-complete in \(\mathrm{C}\) iff \(A \in \mathrm{C} \land \forall B \in \mathrm{C} \implies B \leq_{m} A\).
        Такие множества задают, к примеру, проблема самоприменимости и проблема остановки.
        
        Разрешимые множества сводятся к любым непустым
        
        Всякое перечислимое множество сводится к множеству из проблемы самоприменимости.
        
        Нет множества, к которому сводились бы все подмножества \(\mathbb{N}\).
        
        Полезные примеры множеств:
        
        Перечислимо, но некоперечислимо: проблема остановки, проблема самоприменимости; множество гёделевых нумеров программ, вычисляющих нигде не определённую функцию
        
        Неперечислимо, но коперечислимо: множество гёделевых нумеров программ, вычисляющих нигде не определённую функцию
        
        Неперечислимо и некоперечислимо: множество гёделевых нумеров всех программ, вычисляющих (возможно, биективные) тотальные функции; множество гёделевых номеров программ, определённых в нуле и не определённых в единице.
        
        Теорема Клини о неподвижной точке:
        Пусть \(U(n, x)\) — некоторая гёделева универсальная вычислимая функция и \(f: \mathbb{N} \rightarrow \mathbb{N}\) — всюду определённая вычислимая функция. Тогда \(\exists n_{0} \in \mathbb{N}: \ U(n_{0}, x) = U(f(n_{0}), x)\).
        Каково бы ни было вычислимое всюду определённое преобразование программ \(f\), какую-то программу \(n\) это преобразование превратит в эквивалентную: — вычисляющую ту же функцию — программу \(f(n)\)
        
        С помощью теоремы Клини можно получить другое доказательство теоремы Успенского.
        Обозначим как \(\mathrm{N}\) множество всех номеров всех функций, принадлежащих некоторому нетривиальному семейству. В силу нетривиальности, выберем элемент, лежащий и не лежащий в нём, и положим в качестве тотальной вычислимой функции ту, которая, принимая на вход элемент, принадлежащий этому множеству, возвращает тот, который в нём не лежит, и наоборот.
        Тем не менее, из условия \(\forall x \ U(n, x) \neq U(h(n), x)\) следует противоречие с теоремой Клини: у полученного отображения нет неподвижной точки. #
        
        Пусть \(U(n_{0}, x)\) — гёделева универсальная вычислимая функция. Тогда существует такое число n{0}, что \(U(n{0}, x) = n_{0}\).
        Существует такая машина Тьюринга, которая на любом входе печатает текст своей программы.
        
        1 more item...
        
        Существует неглавная нумерация, где некоторая функция имеет только один номер:
        
        Рассмотрим произвольную у.в.ф. \(U\) и множество номеров \(A\) хоть где-то определённых программ в её нумерации. Оно, как известно, перечислимо.
        
        \(A\) непусто и, как перечислимое множество, является образом некоторой тотальной вычислимой функции \(f\). Построим функцию \(W(m, x)\), которая нигде не определена, если \(m = 0\), и равна \(U(f(m-1), x)\) иначе.
        
        Докажем, что она универсальна для класса вычислимых функций: нигде не определённая имеет единственный номер, а номера остальных лежат в \(A\) по определению, значит, равны \(f(k)\) для некоторого \(m = k + 1\).
        
        Определение нельзя ослабить: существует такая арифметическая функция двух аргументов \(V(n, x)\), что каждый её слой вычислим, все вычислимые функции встречаются среди строк её таблицы, но сама она невычислима.
        В чётных строках запишем таблицу для некоторой \(U(n, x)\), в нечётных — характеристическую функцию для некоторого неперечислимого множества \(K\) (вычислимой она при этом быть не обязана).
        Если тогда \(V(n, x)\) вычислима, то и её область определения перечислима, а значит, сужение области определения на пары равных нечётных чисел также перечислимо, следовательно, должно быть перечислимо и \(K\). Противоречие.
        
        There is a computable function which can't be extended to totally computable function:
        Proof: Consider \(f(n) = U(n, n) + 1\) for universal function \(U\).
        Supposing the contrary, it follows from universality of \(U\) that such function \(g(n) = U(n_{0}, n)\) for some \(n_{0} \in \mathbb{N}\), hence \(g(n_{0}) = U(n_{0}, n_{0})\). Since \(g\) is total, \(U(n_{0}, n_{0})\) is defined, hence \(f(n_{0})\) is defined and \(U(n_{0}, n_{0}) = g(n_{0}) = f(n_{0}) = U(n_{0}, n_{0}) + 1\), hence the contradiction.
        Область определения любой такой функции — перечислимое неразрешимое множество:
        #
        
        Существует такая функция, принимающая только значения 0 и 1:
        Доказательство: \(f(n) = (U(n, n) \neq 0 \land U(n, n) \neq undefined) \\ ? \ 0 : [U(n, n) = 0 \ ? \ 1 : undefined]\)
        Предположим противное и обозначим эту функцию как \(g(n) = U(i, n)\). Поскольку она тотальна, \(g(i) = U(i, i) \neq undefined \implies f(n) \neq undefined\). Тем не менее, по построению \(U(n, n) \neq undefined \implies f(n) \neq U(n, n)\).
        
        Всякая невозрастающая всюду определённая арифметическая функция вычислима:
        Доказательство: Если функция невозрастает, то её можно разбить на участки, где она постоянна. Их конечное число, т.к. множество натуральных чисел фундировано.
        Следовательно, достаточно доказать, что, независимо от числа таких участков (а оно не превышает \(f(0)\)), функция будет вычислима.
        Значит, будем вести доказательство индукцией по \(f(0)\). Всего есть два варианта: либо \(\exists c \in \mathbb{N}: \ \forall n \in \mathbb{N} f(n) = c\), либо \(\exists m > 0, c \in \mathbb{N}: \ f(m) = c < f(0)\).
        
        Любая константа вычислима (т.к. можно записать её в унарной/двоичной системе счисления).
        
        Заметим, что для функции \(g(n) = f(n + m)\) выполнено предположение индукции, т.к. \(g(0) = f(m) < f(0)\), значит, \(f(n)\) вычислима, т.к. начальный отрезок, соответствующий \(m\), имеет конечную длину, и \(f\) постоянна на нём.
        Значит, \(f\) вычислима.
        
        Функция вычислима тогда и только тогда, когда её график перечислим: отсюда, в частности, следует, что вычислимая биекция имеет вычислимую обратную функцию.
        
        If a function \(f \rightarrow \{0, 1\}\) is determined by selecting \(f(1), f(2), ...\) independently and uniformly randomly, then \(f\) is computable with probability zero.
        Hence, computability is quite a rare property.
    - - Перечислимые множества:
        Множество \(A\), для которого существует перечислитель, печатающий все элементы \(A\) и только их.
        Из соображений мощности, т.к. программ-перечислителей не более чем счётное число, существуют неперечислимые подмножества множества натуральных чисел.
        Пример — множество номеров всюду определённых (или нигде не определённых) вычислимых функций в нумерации главной у.в.ф.
        
        Любое разрешимое множество перечислимо.
        В силу того, что мы работаем со счётными множествами, можно упорядочить универсум и последовательно перебирать все его элементы, печатая необходимые (мы можем их отличить за счёт разрешимости). #
        
        Метод Британского музея:
        Многие неразрешимые множества, тем не менее, перечислимы: в частности, можно построить машину, которая будет перебирать всевозможные последовательности формул, и тогда она рано или поздно найдёт доказательство теоремы формальной теории, если оно существует.
        Hatling set is a good example of those.
        
        Любое перечислимое множество является проекцией разрешимого.
        
        Существует перечислимое неразрешимое множество:
        Выберем область определения некоторой вычислимой функции \(f\), не имеющей всюду определённого вычислимого продолжения — оно перечислимо (как область определения вычислимой функции) и неразрешимо, т.к. иначе функция \(g(x) = f(x) \ if x \in dom(f) \ 0 \ otherwise\) была бы всюду определённым вычислимым продолжением \(f(x)\).
        
        Эквивалентные свойства:
        
        Вычислима полухарактеристическая функция (1 на \(A\), undefined на остальных). (достаточно запустить перечислитель и проверить, остановится ли он)
        
        Множество \(А\) перечислимо тогда и только тогда, когда является областью определения некоторой вычислимой функции.(например, своей полухарактеристической функции \(\chi_{0}\))
        Доказательство:
        Необходимость: перечислим множество следующей процедурой: на k-ом шаге запустить вычислимую функцию из условия на k шагов на 0, (k-1) шаг на 1, ..., 1 шаг на k. Если на каком-то из аргументов начального отрезка она остановится ровно за k шагов, напечатать этот аргумент.
        Достаточность: если полуразрешающий алгоритм остановился на x, то напечатать x.
        
        \(А\) пусто или является областью значений некоторой всюду определённой вычислимой функции (например, \(n \chi_{A}(n) \)).
        
        \(А\) конечно или является областью значений некоторой вычислимой инъекции.
        
        \(А\) является проекцией некоторого разрешимого множества \(B \subset \mathbb{N}^2 \), т.е. \(A = \{x \ | \ \exists y (x, y) \in B\}\).
        
        \(A, B\) — перечислимы \(\implies\) перечислимы:
        
        \(A \cap B, A \cup B\)
        
        \(\forall k \in \mathbb{N}, \ A^{k}\)
        
        \(A^{*}\)
        
        Алгоритм перечисления элементов множества \(S \subset \mathbb{N}\) в возрастающем порядке существует тогда и только тогда, когда \(S\) разрешимо.
        Доказательство:
        
        Необходимость: последовательно применить характеристическую функцию ко всем натуральным числам, упорядоченным стандартным образом, и вывести те, которые принадлежат \(S\).
        
        Достаточность: \(\chi_{S}(n)\) определим следующим образом: как только перечисляющий алгоритм выдаёт число \(m \geq n\), проинициализируем по правилу: \(m = n \implies \chi_{S}(n) = 1\), иначе \(\chi_{S}(n) = 0\).
        
        Если существует алгоритм, перечисляющий множество, то существует и алгоритм, перечисляющий его без повторений
        
        Существует перечислимое множество \(A \in \mathbb{N}\) и вычислимая всюду определённая арифметическая функция \(f\), такие что образ \(f(A)\) неразрешим.
        Доказательство:
        
        Возьмём множество \(H = \{ n \in \mathbb{N} \ | \ U(n, n) \) определено} для некоторой у.в.ф.
        
        Согласно третьему определению перечислимости, существует такая тотальная вычислимая функция, областью значений которой является \(H\). #
        
        Следовательно, в качестве A можно взять множество \(\mathbb{N}\).
        
        Существуют перечислимые, непересекающиеся, неотделимые множества:
        
        \(V(n, x) = \min(U(n, x), 1)\) — также у.в.ф. для класса функций \(\mathbb{N} \rightarrow \{0, 1, \ undefined\}\).
        
        Множества \(A = \{n \ | \ V(n, n) = 0\}, B = \{n \ | \ V(n, n) = 1\}\) удовлетворяют условию: они перечислимы как подмножества области значений вычислимой функции и не пересекаются.
        
        \(\not \exists D \subset \mathbb{N}: D\) — разрешимо, \(A \subset D, D \cap B = \emptyset\): в противном случае объединение характеристических функций \(D, \overline{D}\) было бы всюду определённым вычислимым продолжением \(d(n) = U(n, n)\), что невозможно по ранее доказанной теореме.
        
        Существует подмножество натуральных чисел, одновременно не являющееся ни перечислимым, ни коперечислимым:
        Доказательство: например — множество \(Tot\) номеров программ, вычисляющих всюду определённые функции.
        
        Предположим, что оно перечислимо. По определению 3, оно будет образом некоторой всюду определённой вычислимой функции \(f\).
        Положим \(g(x) = U(f(x), x) + 1\). Как композиция вычислимых, она также будет вычислима и всюду определена.
        Раз она вычислима, она входит в таблицу для у.в.ф. как строка с номером \(t\): \(g(x) = U(t, x)\).
        \(g(x)\) всюду определена, значит, \(t \in Tot\), т.к. t — номер программы, вычисляющей всюду определённую функцию.
        Отсюда следует, что \(\exists k \in \mathbb{N}: f(k) = t\).
        Тогда \(g(k) = U(f(k), k) = U(f(k), k) + 1\) по построению.
        Противоречие.
        
        Покажем, что дополнение (множество всех (строго) частично определённых функций) неперечислимо.
        Воспользуемся методом m-сводимости.
        
        Существует неразрешимое подмножество множества пар натуральных чисел, все столбцы и строки которого разрешимы: :warning:
        
        Множество программ, вычисляющих вычислимые арифметические функции одного аргумента, определённые хотя бы для одного аргумента, перечислимо:
        Доказательство:
        
        Зафиксируем некоторую универсальную вычислимую функцию для арифметических вычислимых функций одного переменного \(U(n, x)\).
        
        Будем перебирать тройки \((n, x, k)\), "номер программы — аргумент — число тактов" и выводить n, если \(U(n, x)\) остановилась ровно за k шагов. Таким образом всё множество будет (без повторений) перечислено.
        
        Иммунные и простые множества:
        Иммунное множество: бесконечное неперечислимое множество, не содержащее бесконечных перечислимых подмножеств
        Простое множество: множество, дополнение к которому имунно.
        Конструкция Поста:
        
        Построим простое множество \(S\) "с нуля". Если оно хотя бы по одному элементу будет пересекаться с каждым бесконечным перечислимым множеством, то его дополнение будет, очевидно, иммунно.
        
        Тем не менее, нельзя наобум добавлять элементы в множество: нужно удостовериться, что дополнение при этом останется бесконечным. Идея: брать только "достаточно большие" элементы: например, из \(i\)-го перечислимого множества (в некоторой нумерации) брать только те элементы, которые больше \(2i\), и не более одного из каждого множества. Тогда по окончании процедуры построения в начальном отрезке \([0; 2n-1]\) будет не более \(n\) элементов из \(S\), попавшие туда из первых \(n\) множеств (т.к. все остальные уже будут больше 2n: максимально уплотняем нумерацию множеств, из которых брали элементы, и оцениваем худший случай).
        
        Итого: \(S\) бесконечно, \(S\) имеет бесконечное дополнение, \(S\) перечислимо, \(S\) не коперечислимо (теорема Поста) и \(S\) не разрешимо.
        
        Также любое имунное множество подходит в качестве примера бесконечного неразрешимого множества, не имеющего бесконечных неразрешимых подмножеств
        
        Сумма Минковского двух неперечислимых множеств может быть перечислима (и даже разрешима):
        В качестве примера возьмём любое неперечислимое и не коперечислимое множество вместе с дополнением, дополним оба нулями. Их суммой Минковского будет всё \(\mathbb{N}\).