Какие операции необходимо выполнить, чтобы выполнить произвольные аналоговые вычисления ? Достаточно ли будет сложение, вычитание, умножение и деление? Кроме того, кто-нибудь знает точно, какие проблемы можно решить с помощью аналоговых вычислений, но не с...
Я слышал, что девиз взаимодействия более мощный, чем алгоритмы от Питера Вегнера . Основа идеи заключается в том, что (классическая) машина Тьюринга не может обрабатывать взаимодействие, то есть взаимодействие (вход / выход) с внешним миром / средой. Как это может быть так? Как может быть что-то...
Я начинаю читать книгу о вычислительной сложности и машинах Тьюринга. Вот цитата: Алгоритм (т. Е. Машина) может быть представлен в виде битовой строки, как только мы определимся с каноническим кодированием. Это утверждение представлено как простой факт, но я не могу его понять. Например, если у...
Не существует общего аналитического решения задачи о n-теле, которое может дать аналитическую функцию, которую можно использовать для определения состояния системы из n-тела в произвольный момент времени t с точной точностью. Однако существуют некоторые частные случаи систем с n телами, для которых...
Проблема, распознают ли два нажимных автомата один и тот же язык, неразрешима. Проблема того, распознает ли автомат с нажатием кнопки пустой язык, разрешима, следовательно, также решаемо, распознает ли он данный конечный язык. Неразрешимо, является ли язык, принятый автоматом нажатия, регулярным....
В этом вопросе мы рассматриваем только машины Тьюринга, которые останавливаются на всех входах. Если k∈Nk∈Nk \in \mathbb{N} то через TkTkT_k мы обозначаем машину Тьюринга, код которой равен kkk . Рассмотрим следующую функцию s(x,y)=min{k∣|L(Tk)∩{x,y}|=1}s(x,y)=min{k∣|L(Tk)∩{x,y}|=1}s(x,y) = \min\{k...
Указанные языки и , скажем , что их конкатенация является однозначной , если для всех слов , существует ровно один разложение с и , и неоднозначном иначе. (Я не знаю, есть ли установленный термин для этого свойства - трудная вещь для поиска!) В качестве тривиального примера, конкатенация с самим...
Обратите внимание, что это вопрос, связанный с обучением на курсе CS в университете, это НЕ домашняя работа, и его можно найти здесь под экзаменом осень 2011 года2. Вот два вопроса, на которые я смотрю с прошлого экзамена. Похоже, они связаны, первое: Позволять FINITECFG={<G>∣G is a Context...
Множество является счетным, если оно имеет биекцию с натуральными числами, и вычислимо перечислимо (ce), если существует алгоритм, который перечисляет его членов. Любое не конечное вычислимо перечислимое множество должно быть счетным, поскольку мы можем построить биекцию из перечисления. Есть ли...
Для языка LLL определите множество длин как множество длин слов в : L L S ( L ) = { | ты | | U ∈ L }LLLLLLL S (L)={ | ты | |U∈L}LS(L)={|u|∣u∈L}\mathrm{LS}(L) = \{|u| \mid u \in L \} Какие наборы целых чисел могут быть набором длины обычного...
Я использую цифровой компьютер, чтобы написать это сообщение. У такой машины есть свойство, которое, если подумать, на самом деле весьма примечательно: это одна машина, которая, при правильном программировании, может выполнять любые возможные вычисления . Конечно, вычислительные машины того или...
Счетные машины с двумя или более счетчиками обычно показаны эквивалентными машинам Тьюринга в курсах по теории вычислений. Однако я не видел формального анализа того, какие языки можно распознать с помощью машины с одним счетчиком. Являются ли эти языки эквивалентными языкам, не зависящим от...
Существуют ли неразрешимые свойства линейных ограниченных автоматов (избегая трюка с пустым языком множеств)? Как насчет детерминированного конечного автомата? (отложить в сторону неразрешимость). Я хотел бы получить пример (если возможно) неразрешимой проблемы, которая определена без явного...
В одной из лекций профессор упомянул, что современные компьютеры не имеют такой вычислительной мощности, как машина Тьюринга, потому что у них нет бесконечной памяти, и, поскольку ни у одного компьютера нет бесконечной памяти, машина Тьюринга недостижима и просто представляет верхний предел....
Я искал интересные и легко излагаемые открытые проблемы вычислимости (понятные студентам, изучающим первый курс по вычислимости), чтобы привести примеры открытых проблем (и, очевидно, я хочу, чтобы студенты могли понять проблему, не требуя слишком много нового определения, а также быть интересным...
Интересно, почему следующий язык находится в ?RR\mathrm R LM1={⟨M2⟩∣∣M2 is a TM, and L(M1)=L(M2), and |⟨M1⟩|>|⟨M2⟩|}LM1={⟨M2⟩|M2 is a TM, and L(M1)=L(M2), and |⟨M1⟩|>|⟨M2⟩|}L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a TM, and } L(M_1)=L(M_2), \text{ and } |\langle M_1\rangle|...
У меня есть эти вопросы из старого экзамена, который я пытаюсь решить. Для каждой задачи, вход является кодирование некоторой машины Тьюринга MMM . Для целого числа c>1c>1c>1 и следующих трех задач: Правда ли, что для каждого входа xxx M не передает |x|+c|x|+c|x|+c позиции при работе на xxx ?...
Если действительно равен , как это улучшит наши алгоритмы, чтобы быстрее вычислять целые числа? Другими словами, какое понимание даст нам этот факт для лучшего понимания целочисленной факторизации?PP{\sf P}NPNP{\sf...
Я хочу знать, разрешима ли следующая проблема: Экземпляр: NFA A с n государствами Вопрос: существует ли некоторое простое число p такое, что A принимает некоторую строку длины p. Я считаю, что эта проблема неразрешима, но я не могу доказать это. Решающий орган может легко иметь алгоритм для...
Такие языки, как являются сокращением много-один. Нетрудно видеть, что имеет полные проблемы. С. Шмитц [1] рассматривает некоторые классы между и . Они представляют полные проблемы для этих классов при специально созданных...