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

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

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

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

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

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

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

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

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

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

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

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

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

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