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

Докажите, что множество вычислимых функций не изменится, если считать, что на ленте в начальной конфигурации левее головки стоит особый символ |>, ...
0
голосов
0
ответов
129 показов

Докажите, что существует МТ, которая вычисляет биекцию c:$$\mathbb{N} \rightarrow \mathbb{N}$$Где$$c: (x, y) \rightarrow {x + y + 1\choose 2} + y$$Чис ...
0
голосов
0
ответов
127 показов

Пусть машины M_1 и M_2 вычисляют ф-ции f_1 : B -> {0, 1} и f_2 : B -> {0, 1}. Докажите, что существует МТ М, которая вычисляет дизъюнкцию f_1 ∨ ...
0
голосов
0
ответов
188 показов

Постройте по МТ M и входу x такую МТ M_x, которая останавливается на входе x тогда и только тогда, когда M останавливается на пустом входе.
0
голосов
0
ответов
71 показ

Докажите PSPACE-полноту языка V = {f : в игре в разбиение переменных для формулы fпобеждает первый игрок }. Игра устроена так: двое по очереди выбираю ...
1
голос
1
ответ
160 показов

Докажите, что функция B(n), возвращающая максимальное число блоков 01 подряд в ответе машины Тьюринга с n состояниями на пустом входе, растёт быстрее ...
0
голосов
0
ответов
110 показов

Построить машину Тьюринга, вычисляющую функцию $%g(m,n)=(m \dot{-}n)+2,\ m,n\in \mathbb{N} $%. Показать что функция $%g(m,n)$% является примитивно рек ...
0
голосов
2
ответа
152 показа

Проверить язык на рекурсивность и рекурсивную перечислимость: L5={M | M-машина Тьюринга и ∃x: |x|≡5 1, x ∈ L(M)}
0
голосов
1
ответ
252 показа

Здравствуйте! Нужна помощь с задачкой:Опишите машину Тьюринга, которая проверяет, что её вход имеет вид 0m1n02m , причём n > 0. Поясните, почему эт ...
0
голосов
1
ответ
300 показов

Необходимо составить программу для машины Тьюринга, вычисляющую функцию $%2^{N} $%, где $%N$% задано в троичной системе счисления.Смущает очень троичн ...
0
голосов
1
ответ
218 показов
0
голосов
0
ответов
241 показ

Докажите, что существует машина Тьюринга с номером n, распознающая множество {n, n+1...,2n}
0
голосов
0
ответов
254 показа
0
голосов
0
ответов
233 показа

Дана машина Тьюринга с начальным состоянием s, конечным состоянием f и набором правил:s1 => q1 1Rs0 => s0Rs* => f0 Eq1 0 => q1 0Rq1* => ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru