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

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

Дайте определение ОМТ (оракульной машины Тьюринга), используя язык предикатов.Машина Тьюринга с оракулом А: это МТ с дополнительной оракульной лентой, ...
0
голосов
1
ответ
70 показов

Пусть задана некоторая главная универсальная нумерация вычислимых функций. Докажите, что множество номеров машин Тьюринга, которые вычисляют последова ...
1
голос
1
ответ
60 показов

Опишите машину Тьюринга, проверяющую, что x есть начало последовательности 0110111001011101111000...(все числа записаны подряд по возрастанию в двоичн ...
0
голосов
0
ответов
107 показов

В каких случаях можно гарантировать, что вычисление на машине Тьюринга никогда не остановится? а) Через n^3 + 1 шаг после начала работы машина посетил ...
1
голос
0
ответов
247 показов

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

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

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

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

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

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

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

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

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

Построить машину Тьюринга, вычисляющую функцию $%g(m,n)=(m \dot{-}n)+2,\ m,n\in \mathbb{N} $%. Показать что функция $%g(m,n)$% является примитивно рек ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru