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

Помогите построить машину Тьюринга, разрешающую язык {w ∈ {a, b}∗ | количество букв $%a$% в слове $%w$% равно $%2^n$% для некоторого $%n$%}? В начале ...
0
голосов
0
ответов
121 показ

1)Постройте машину Тьюринга, разрешающую язык $$ $${w ∈ {a, b}∗ | количество букв a в слове w равно 2^n для некоторого n.}.$$ $$ Сначала опишите поряд ...
0
голосов
0
ответов
96 показов

Опишите машину Тьюринга разрешающую язык {w ∈ {a, b}∗| у слова w четное число букв}.
0
голосов
0
ответов
74 показа

Постройте m-сводимость множества описаний машин тьюринга, которые останавливаются на пустом входе, к множеству описаний машин, которые останавливаются ...
1
голос
0
ответов
116 показов

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

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

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

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

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

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

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

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

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

Необходимо составить программу для машины Тьюринга, вычисляющую функцию $%2^{N} $%, где $%N$% задано в троичной системе счисления.Смущает очень троичн ...
0
голосов
1
ответ
299 показов
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru