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

Сколько существует монотонных булевых функций, зависящих от 4 переменных x1, x2, x3, x4?
0
голосов
1
ответ
63 показа

Определить коэффициент при x5 из разложения выражения (x3 + x - 2)8 степени
0
голосов
0
ответов
43 показа
0
голосов
0
ответов
32 показа

Докажите, что любое бесконечное рекурсивное множество A ⊆ N можно разбить на два непересекающихся бесконечных рекурсивных подмножества, т.е. существую ...
0
голосов
1
ответ
88 показов

Функция f : N → N называется строго возрастающей на множестве B ⊆ N, если f определена намножестве B (т.е. для любого x ∈ B значение f(x) определено) ...
0
голосов
1
ответ
101 показ

Докажите, что множество A = {<x,y> | Wx ∪ Wy != ∅} рекурсивно перечислимо и K <_m A, гдеK = {x | φx(x)↓}.
0
голосов
0
ответов
42 показа

Пусть f : N → N тотальная вычислимая функция. Докажите, что множество всех натуральныхчисел x таких, что f(y) < f(x) для некоторого y > x, являе ...
0
голосов
0
ответов
53 показа

Пусть A ⊆ N рекурсивно перечислимо, а B ⊆ N рекурсивно. Докажите, что множество A ∩ Bрекурсивно перечислимо. Приведите пример рекурсивно перечислимого ...
0
голосов
0
ответов
56 показов

Рассмотрим следующую частично рекурсивную функциюf(x) = μy (g(y) = x) = μy P(x, y),полученную минимизацией предиката P(x, y) ⇐⇒ (g(y) = x) по переменн ...
0
голосов
0
ответов
46 показов

Докажите, что множество всех “промежутков” между простыми числами, т.е. множество всех на-туральных чисел, которые представляются в виде разности двух ...
0
голосов
0
ответов
62 показа

Верно ли, что если машина Тьюринга M за время своего вычисления посещает одну и ту жеконфигурацию дважды, то это вычисление не завершается (т.е. машин ...
0
голосов
1
ответ
78 показов

Пусть функция g(x) примитивно рекурсивна. Докажите примитивнуюрекурсивность функцииf(x) = система: 1, если g(y) < g(y + 1) для всех y <= x; 0, и ...
0
голосов
0
ответов
43 показа

Докажите, что множество A = {(x, y) | φ_x(y)↓ или φ_x(2y)↓} рекурсивно перечислимо и K >=m A,где K = {x | φ_x(x)↓}.
0
голосов
0
ответов
50 показов

Докажите, что множество A = {x | {0, 1, . . . , 2020} ⊆ Wx}, где Wx = dom φx = {y | φx(y) ↓},рекурсивно перечислимо, но не рекурсивно.
0
голосов
0
ответов
50 показов

Пусть A ⊆ N рекурсивно перечислимо, а B ⊆ N рекурсивно. Докажите, что множество A ∪ Bрекурсивно перечислимо. Приведите пример рекурсивно перечислимого ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru