Вопросы по теме 'turing-machines'
Является ли этот язык разрешимым?
Я борюсь с тем, разрешимо ли это:
A = {x является элементом множества натуральных чисел | для каждого y большего, чем x, 2y является суммой двух простых чисел}
Я склонен думать, что это разрешимо, учитывая тот факт, что при вводе в машину...
1982 просмотров
schedule
16.07.2022
Разрешимость и рекурсивная перечислимость
Скажем, существуют машины Тьюринга M1, M2, M3, языки, которые они распознают, это L(M1), L(M2) и L(M3) соответственно. Следующий язык L = {(M1, M2, M3) : L(M1), L(M2) и L(M3) не равны} Является ли язык разрешимым? Рекурсивно перечислимы? Или ни то,...
1117 просмотров
schedule
21.10.2022
Я не понимаю концепцию недетерминированной машины Тьюринга
Я не понимаю концепцию недетерминированной машины Тьюринга . Думаю, я понимаю термин Недетерминированный алгоритм : (недетерминированный алгоритм — это алгоритм, который может демонстрировать различное поведение при разных запусках, в отличие от...
17302 просмотров
schedule
20.04.2022
Машина Тьюринга, принимающая строки с одинаковой начальной и конечной длиной
Мне нужна помощь в создании одноленточной детерминированной машины Тьюринга для этого языка
здесь я не уверен, как определить, какие строки примет ТМ. Как я могу заставить машину принимать строки, где a=c? потому что часть b содержит элементы...
1557 просмотров
schedule
06.10.2022
Как доказать, что данный язык не распознается
Учитывая следующий язык:
Lf = { р (м) | Язык M конечен }
Лф узнаваем? если нет, докажите с помощью приведения. В противном случае создайте NDTM, который его распознает.
Я почти уверен, что Lf нельзя распознать, но я не уверен, как это...
651 просмотров
schedule
05.10.2022
Существует ли код C++, который компилируется бесконечно долго?
Я часто слышу о том, что "исходники C++ требуют много времени и памяти для компиляции".
Я также слышал о том, что шаблон C++ завершен по Тьюрингу, поэтому он может страдать от проблемы остановки .
Я также создал проект C++, который требует 8 ГБ...
756 просмотров
schedule
05.05.2023
Какие шесть основных примитивов в Turing Complete
Я слушаю урок edX, и профессор подчеркивает, что каждую машину, способную выполнять эти шесть основных примитивов, можно назвать полной по Тьюрингу. Но каковы шесть основных примитивов?
18824 просмотров
schedule
02.06.2023
Машина Тьюринга, которая принимает другую машину Тьюринга, если она делает определенный ход
Можно ли построить turing-machine , у которого есть другая turing-machine и строку в качестве входных данных и принимает, будет ли полученная машина двигаться влево или вправо (или что-либо еще) для этой строки?
145 просмотров
schedule
24.10.2022
Если детерминированная машина Тьюринга определяет язык L, означает ли это, что она также определяет дополнение языка L?
Предположим, что существует детерминированная машина Тьюринга, например. тот, который выполняется за полиномиальное время и определяет язык L.
Означает ли это автоматически, что он также определяет дополнительный язык L?
Говоря о дополнительном...
168 просмотров
schedule
19.10.2022
В чем разница между рекурсивными и рекурсивно перечислимыми языками
Мне было интересно, в чем разница между рекурсивными и рекурсивно перечислимыми языками с точки зрения остановки и машин Тьюринга. Я знаю, что рекурсивно перечисляемые языки являются подмножеством рекурсивных языков, но я не уверен в отличии от этого.
23650 просмотров
schedule
29.04.2023
Голландский флаг на машине Тьюринга с одной лентой и сложностью n.log(n)?
Голландская национальная проблема заключается в следующем: у меня есть последовательность символов x^k (k >= 3). Моя цель — преобразовать это предложение в голландский флаг, то есть:
ХХХ дает RWB
xxxx дает RWBB
ххххх дает RWWBB
xxxxxx дает...
219 просмотров
schedule
16.11.2022
Язык, который может быть распознан ТМ, но не может быть определен ТМ?
Может ли язык, который может быть распознан ТМ, но не может быть определен ТМ?
пример языка, который может быть распознан ТМ, но не может быть определен ТМ
Будет ли ответ:
TM={<M,w> M is a TM that accepts input string w}...
535 просмотров
schedule
25.03.2023
В чем разница между ласточкиным хвостом и параллелизмом?
Я наткнулся на определение Dovetailing , о котором раньше не слышал. что пришло мне на ум, было Concurrency . Однако я не смог найти ни одного сообщения, касающегося этих двух концепций. Я также прочитал это .
Если я не ошибаюсь, ласточкин...
118 просмотров
schedule
29.07.2023
разрешимые языки (вычислительные модели)
Мне нужно доказать, разрешима ли L или нет:
L={‹M> | M является TM, и объединение L(M) и H_TM находится в RE}
( H_TM={‹M,w> | M — TM, который останавливается на w} )
84 просмотров
schedule
06.09.2022
Повышение производительности симулятора ТМ
Я пытаюсь смоделировать множество машин Тьюринга с двумя состояниями и тремя символами (лента в одном направлении). Каждая симуляция будет иметь разные входные данные и будет выполняться в течение фиксированного количества шагов. Текущим узким...
196 просмотров
schedule
24.11.2022
Может ли машина Тьюринга работать с десятичными числами?
Я могу выполнять некоторые операции на машине Тьюринга, но использую двоичные формы чисел, как это делают компьютеры. Интересно, можно ли записать на его ленту десятичные числа и произвести расчет? Заранее спасибо.
739 просмотров
schedule
04.12.2022
Как именно работают макросы в машине Тьюринга?
У меня есть скриншот из моего учебника здесь (Sudkamp, 3e), и я пытаюсь понять, как макросы используются с машиной Тьюринга. Мне трудно понять это, тем более что я никогда раньше не изучал макросы. Если кто-то может помочь с объяснением здесь, я...
707 просмотров
schedule
03.03.2024
Машина Тьюринга, стирающая ввод
У меня есть вопрос: рассмотрим машину Тьюринга Cw, которая стирает ввод, записывает w на ленту и останавливается при сканировании крайнего левого символа w. Дизайн машины Тьюринга C011
Мне нужно объяснение, в чем актуален вопрос и что делает Cw....
1193 просмотров
schedule
14.05.2022
Тьюринг о вычислимых числах - я не могу понять, как воспроизвести примеры
Я только недавно начал читать некоторые статьи по CS, и одной из первых была статья Тьюринга «О вычислимых числах», и там он приводит пример конфигурации машины для печати последовательности 010101. Я понимаю, как это должно работать, но я изо всех...
63 просмотров
schedule
01.05.2023
Машина Тьюринга для языка L={a^m b^n a^m b^n ∣ m,n≥0}
У меня возникли проблемы с созданием машины Тьюринга для языка L={a^m b^n a^m b^n ∣ m,n≥0}
Что я думал до сих пор:
Если мы начнем с пробела, строка будет пустой, и она должна быть принята, если нет, начать читать как, и я подумал, что пометить a...
2938 просмотров
schedule
27.05.2023
