0
голосов
0
ответов
21 показ

Проверьте множество и его дополнение на перечислимость:a) X = {n ∈ N | U_n принимает только простые значения};b) Y = {(n, m) ∈ N^2 | dom Um ∩ dom Un = ...
0
голосов
0
ответов
23 показа

Докажите, что найдется n ∈ N, удовлетворяющая условию:a) ∀x U(n, x) = n^(x^n), причем n > 2020;b) ∀x U(n, x) \simeq U(n/5, x), где / означает взяти ...
0
голосов
0
ответов
40 показов

Докажите, что найдутся попарно различные $%n$% и $%m$%, т. ч. для всех $%x\in\mathbb N$% верно$%U(n, x)\simeq U(x, m)$% и $%U(m, x)\simeq U(x, n) + 1$ ...
0
голосов
0
ответов
49 показов

Докажите, что множество вычислимых функций не изменится, если разрешить машине Тьюрингалюбые целочисленные сдвиги.
0
голосов
0
ответов
41 показ

Пусть фиксирован входной алфавит Σ = {0, 1}. Пусть функция f : Σ^∗ → Σ^∗ такова, что f(~x) =1, если ~x — палиндром, а иначе f(~x) = 0. Постройте машин ...
0
голосов
0
ответов
86 показов

Пусть в определении главной универсальной функции существование вычислимой функции требуется не для всех функций, а только для универсальных. Покажите ...
1
голос
1
ответ
78 показов

Задача такая - доказать, что если число $%\alpha$% перечислимо снизу, то существует последовательность $%z_{1}, z_{2}, \dots \in \mathbb{Q}$%, предел ...
1
голос
0
ответов
80 показов

Как вывести из теоремы о рекурсии (или о неподвижной точке), что существует программа, которая печатает свой текст задом наперед?При этом известно, ка ...
0
голосов
0
ответов
180 показов

Все сечения $%U_n$% некоторой вычислимой функции от двух аргументов $%U$% вычислимы. Следует ли отсюда, что сама функция двух аргументов $%U$% вычисли ...
0
голосов
0
ответов
80 показов

Докажите, что любое бесконечное разрешимое множество $$A \subseteq \mathbb{N}$$ можно разбить на два непересекающихся бесконечных разрешимых подмножес ...
0
голосов
1
ответ
115 показов

Вот доказательство того, что в бесконечном перечислимом множестве есть бесконечное разрешимое подмножество:Вопросы такие:1) Все элементы х, для которы ...
0
голосов
0
ответов
132 показа

Надеюсь, эти вопросы интереснее предыдущих тестовых вопросов:3) Почему d(x) принимает все значения? Почему последний пункт неверен? Насчет третьего пу ...
0
голосов
0
ответов
85 показов

Я смотрю видео курс Мусатова по логике (https://courses.openedu.ru/courses/course-v1:mipt+MLTA+spring_2020/courseware/0de393a9409841f484658a6cf7b098cb ...
0
голосов
0
ответов
110 показов

Здравствуйте! Помогите, пожалуйста, доказать это высказывание."Докажите что, семейство всех унарных частичных вычислимых функций, имеющих тотальное вы ...
0
голосов
0
ответов
219 показов

Помогите, пожалуйста, доказать: Докажите, что пара вычислимо перечислимых множеств {n|φn (0) ↓= 0} и {n|φn (0) ↓= 1} неотделима, где φ - универсальная ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru