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

Функция BB не вычислима, поскольку доказано, что для любой вычислимой функции f существует n такое, что BB (n + c)> f (n + c). Тем не менее, некото ...
0
голосов
0
ответов
43 показа

Нужно построить машину тьюринга с полиномиальным временем выполнения, проверяющую, является ли слово палиндромом. Есть идея сравнивать первый и послед ...
0
голосов
0
ответов
100 показов

Реализовать машину Тьюринга со стандартной заключительной конфигурацией для выполнения следующей задачи. На вход подаётся число в двоичной записи в ал ...
0
голосов
0
ответов
70 показов

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

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

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

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

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

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

Опишите машину Тьюринга, которая вычисляет функцию f, такую что f(x) есть слово х, из которого вычеркнуты все вхождения слова 101 (в частности, вхожде ...
1
голос
1
ответ
216 показов

В каких случаях можно гарантировать, что вычисление на машине Тьюринга никогда не остановиться?а) Машина перебирает все пары натуральных (x,y), вычисл ...
1
голос
0
ответов
305 показов

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

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

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

Постройте m-сводимость множества описаний машин тьюринга, которые останавливаются на пустом входе, к множеству описаний машин, которые останавливаются ...
на странице153050
Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru