Вопросы по теме 'turing-machines'
Что находится слева от ввода в машине Тьюринга?
Например, если я нахожусь в конце ввода и смещаюсь влево, как я узнаю, что нахожусь в самом начале ленты? Если их больше |_| до ввода, то мне было бы легко сказать, что я снова в начале, но я не знаю, есть ли они. Это не вопрос домашнего задания, я...
135 просмотров
schedule
11.05.2022
Машины Тьюринга и схемы машин
Артур Дент, используя технологию космической эры, еще не доступную на Земле, разработал алгоритм, который определяет, останавливается или нет TM M1 при запуске на пустой ленте. Но позже он обнаружил, что смысл жизни, вселенной и всего остального -...
455 просмотров
schedule
20.07.2022
Контекстно-зависимый язык с недетерминированной машиной Тьюринга
как я могу показать, что язык является контекстно-зависимым с помощью недетерминированной машины Тьюринга?
я знаю, что язык, который принимается автоматом с линейной привязкой (LBA), является контекстно-зависимым языком. А LBA — это...
1193 просмотров
schedule
26.05.2023
Можно ли программировать графику в AWK?
Я предполагаю, что это вопрос о том, что значит быть завершенным по Тьюрингу. Awk — это язык программирования, и я слышал, что с ним можно делать что угодно, но разве нет физических ограничений? Я имею в виду, вы, вероятно, не можете удалить файлы с...
600 просмотров
schedule
27.08.2023
Какие все известные языки не могут принять машины Тьюринга?
Для примера язык машин Тьюринга которые не принимают свою собственную кодировку, не могут быть приняты ни одной машиной Тьюринга.
5384 просмотров
schedule
06.06.2022
Есть ли простой способ решения вопросов, связанных с созданием машины Тьюринга?
Я понял логику машины Тьюринга. Когда мне дают машину Тьюринга, я могу понять, как она работает и как останавливается. Но когда просят построить машину Тьюринга, это сложнее.
Есть ли простой способ найти ответ на такие вопросы, как:
Construct...
722 просмотров
schedule
23.05.2024
Может ли язык принимать бесконечные числа
У меня есть вопрос, может ли язык принимать бесконечные числа
Я должен уменьшить Lempty до Linf
where Lempty ={e|L(Pe) is null}
Linf={e|L(Pe) is infinite}
так я могу определить программу P, как это
"
input n
Run Pe on 1...n for n...
168 просмотров
schedule
16.06.2022
Машины Тьюринга
Я читаю книгу о языках и автоматах, и я не понимаю машины Тьюринга. Я без проблем научился использовать DFA NFA и Pushdown Automata. Может кто-нибудь объяснить, что это делает?
B = {w#w|w ∈ {0, 1}*}
Следующий рисунок содержит несколько снимков...
1182 просмотров
schedule
17.02.2022
Поддержка машины Тьюринга
У меня есть язык:
(XF*X|F)*
над алфавитом:
{X,F}
Как я могу заставить/спроектировать машину Тьюринга для распознавания этого языка? Любое руководство или совет будут высоко оценены
52 просмотров
schedule
22.06.2023
Является ли этот язык регулярным или нет?
У меня есть язык {4^(w⋅g)34^(g)|w,g∈NAT} над алфавитом {0,1}.
Мне нужно выяснить, является ли этот язык узнаваемым, разрешимым, свободным от контекста, регулярным или ни одним из них.
Как мне это сделать или узнать?
Спасибо
82 просмотров
schedule
26.06.2023
Описание действия машины Тьюринга
Я пытаюсь ответить в третьей части на следующий вопрос:
Я нарисовал следующую диаграмму состояний:
Согласно решению, машина «добавляет 1 к двоичному числу с его младшим битом в крайнем левом положении на ленте». Я не понимаю, что это...
636 просмотров
schedule
14.12.2023
Создание конкретной машины Тьюринга
У меня возникли некоторые проблемы с упражнением, которое просит нарисовать машину Тьюринга, которая решает, что язык L2 = {w ∈ {0,1}∗|w содержит четное количество единиц}.
У кого-нибудь есть решение для сравнения с тем, что есть у меня?
Спасибо
67 просмотров
schedule
14.10.2022
Откуда мы знаем, что NP-полные задачи являются самыми сложными в NP?
Я понимаю, что если вы можете сделать полиномиальное сокращение времени из «каждой» проблемы, это доказывает, что проблема по крайней мере так же сложна, как и любая проблема в NP. Кроме того, как мы узнаем, что обнаружили все проблемы в NP? Не...
746 просмотров
schedule
12.07.2022
Распознаваемый по Тьюрингу язык разрешим или нет?
Может ли распознаваемый по Тьюрингу язык быть разрешимым, если можно перечислить его строки неубывающей длины?
Я думаю, это не потому, что вы можете уйти в бесконечность, и это сделает ее неразрешимой, верно?
417 просмотров
schedule
11.08.2022
Язык, принятый машиной Тьюринга с бесполезным состоянием?
Какой язык принимает машина Тьюринга, состояние которой не входит на вход I?
Конкретно,
Если состояние принятия - это состояние, в которое он никогда не входит, тогда должен ли L={пусто}?
Если состояние отклонения — это состояние, в...
970 просмотров
schedule
08.05.2022
Машина Тьюринга для приема строки из трехсимвольного алфавита
Мне нужно создать машину Тьюринга, которая принимает язык a^1 b^j c^k, где i >= j >= k, но я даже не знаю, как начать. Машины Тьюринга в этом контексте по какой-то причине мне трудно понять.
229 просмотров
schedule
27.06.2022
