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

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

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

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

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

Помогите, пожалуйста, доказать: Докажите, что пара вычислимо перечислимых множеств {n|φn (0) ↓= 0} и {n|φn (0) ↓= 1} неотделима, где φ - универсальная ...
0
голосов
0
ответов
80 показов

Найдите вычислимую частичную функцию $%f$% и вычислимое множество $%X\subset N$% такие что $%f(N)=N$% но $%f(X)$% не вычислимо
1
голос
1
ответ
104 показа

Пусть $%A=\{x:\phi_x\text{ всюду определена }\}$%$%B=\{x: \phi_x\text{ всюду определена и постоянна}\}$%Почему $%A\equiv_m B$%?Например, попробуем док ...
0
голосов
0
ответов
80 показов

Пусть рекурсивно перечислимое множество A перечислимо монотонно неубывающей функцией f. Тогда А вычислимо.Доказательство. Если А конечно, то это верно ...
0
голосов
0
ответов
72 показа

Докажите, что существует вычислимая функция $%f: \mathbb N\to \mathbb N$% такая что $%\varphi_{f(k)}=p_k$%, где $%p_k$% - функция из этого вопросаОпят ...
0
голосов
0
ответов
78 показов

Докажите, что если два множества А и В принадлежат одному классу иерархии Сигма к-ое, то разность А\В принадлежит классу П(к+1)
1
голос
0
ответов
233 показа

Докажите, что функция$$f(x) = \begin{cases}100, & \text{если } \phi_x(x) = 59 \\59, & \text{иначе}\end{cases}$$ невычислима
0
голосов
0
ответов
229 показов

Докажите, что существует такое натуральное i, что φ_i(x) = i + x для всех натуральных x.
1
голос
1
ответ
318 показов

Докажите, что любые два непересекающихся коперечислимых множества A, B ⊂ N отделимы некоторым разрешимым множеством. (Множество A ⊂ N называется копер ...
1
голос
1
ответ
289 показов

Докажите, что множества {i | φ_i(0) не определено} и {i | φ_i(0) = 1} не отделимы разрешимым множеством.
1
голос
0
ответов
258 показов

Найдите тотальную вычислимую функцию f: N → N и разрешимое множество A ⊂ N, для которых множество f(A) неразрешимо.
42 вопроса
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru