0
голосов
1
ответ
89 показов
Доказать, что множество РП
Функция f : N → N называется строго возрастающей на множестве B ⊆ N, если f определена намножестве B (т.е. для любого x ∈ B значение f(x) определено) ...
0
голосов
1
ответ
102 показа
Рекурсивно перечислимое множество
Докажите, что множество 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
ответов
58 показов
Рекурсивно перечислимое множество
Пусть A ⊆ N рекурсивно перечислимо, а B ⊆ N рекурсивно. Докажите, что множество A ∩ Bрекурсивно перечислимо. Приведите пример рекурсивно перечислимого ...
0
голосов
0
ответов
48 показов
Доказать, что множество РП
Докажите, что множество всех “промежутков” между простыми числами, т.е. множество всех на-туральных чисел, которые представляются в виде разности двух ...
0
голосов
1
ответ
80 показов
Докажите примитивную рекурсивность функции
Пусть функция g(x) примитивно рекурсивна. Докажите примитивнуюрекурсивность функцииf(x) = система: 1, если g(y) < g(y + 1) для всех y <= x; 0, и ...
0
голосов
0
ответов
51 показ
Рекурсивно перечислимое множество
Докажите, что множество A = {x | {0, 1, . . . , 2020} ⊆ Wx}, где Wx = dom φx = {y | φx(y) ↓},рекурсивно перечислимо, но не рекурсивно.
0
голосов
0
ответов
50 показов
Рекурсивное перечислимое множество
Пусть A ⊆ N рекурсивно перечислимо, а B ⊆ N рекурсивно. Докажите, что множество A ∪ Bрекурсивно перечислимо. Приведите пример рекурсивно перечислимого ...
0
голосов
0
ответов
40 показов
Рекурсивное множество и строго возрастающая функция [закрыт]
Пусть A ⊆ N рекурсивно, а f : N → N тотальная строго возрастающая вычислимая функция, т.е.f(x) < f(y) для всех x < y. Докажите, что множество f( ...
1
голос
1
ответ
66 показов
Асимптотика рекуррентной последовательности
Последовательность A(1)=1, A(N)=1+A(N-A(A(N-1)) 1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7... при больших N хорошо описывается уравнением Q*n^a.Задача найт ...
0
голосов
0
ответов
113 показов
Проблема Поста
Зафиксируем алфавит. Дано конечное множество квадратиков. На каждом квадратике написаны два непустых слова, одно сверху, другое снизу. Например https: ...
0
голосов
1
ответ
154 показа
Докажите, что множество не является рекурсивно перечислимым
Докажите, что множество $%\{p:\phi_p(x) \text{ останавливается для всех } x\}$% не является рекурсивно перечислимым, т.е. что не существует программы ...
0
голосов
0
ответов
170 показов
Докажите, что множество рекурсивно перечислимо
Докажите, что множество $%\{\langle a,b\rangle:\phi_a()\text{ и } \phi_b()\text{ определены и равны}\}$% является областью определения функции $%\phi_ ...
0
голосов
0
ответов
141 показ
Докажите, что $%A\equiv_m B$%
Пусть $%A,B$% - множества, чья симметрическая разность конечна. Докажите, что $%A\le_m B$% и $%B\le_m A$%
0
голосов
0
ответов
112 показов
$%m$%-приводимость
Пусть $%A,B\subseteq N$% ($%N$% - натуральные числа). Будем писать $%A\le_m B $%, если существует тотальная вычислимая функция $%f:N\to N$% такая что ...
27 вопросов
Связанные метки
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.