Есть 2020 физиков и 2020 математиков. Некоторые из них знакомы между собой, знакомства взаимны. По итогам года 200 человек получили премии. При этом у ...
Показать, что если множество ошибок $$C \subseteq B^n$$ состоит не более чем из $$n2^{n/2}$$ наборов, то найдется полиномиальный код, который исправля ...
Дано множество U из n элементов. Каким числом способов в нем можно выбрать три подмножества A, B и C, так, чтобы выполнялись следующие условияn=7, |AU ...
Докажите, что любое бесконечное рекурсивное множество A ⊆ N можно разбить на два непересекающихся бесконечных рекурсивных подмножества, т.е. существую ...
Функция f : N → N называется строго возрастающей на множестве B ⊆ N, если f определена намножестве B (т.е. для любого x ∈ B значение f(x) определено) ...
Пусть A ⊆ N рекурсивно перечислимо, а B ⊆ N рекурсивно. Докажите, что множество A ∩ Bрекурсивно перечислимо. Приведите пример рекурсивно перечислимого ...
Докажите, что множество всех “промежутков” между простыми числами, т.е. множество всех на-туральных чисел, которые представляются в виде разности двух ...
Верно ли, что если машина Тьюринга M за время своего вычисления посещает одну и ту жеконфигурацию дважды, то это вычисление не завершается (т.е. машин ...