Машина Тьюринга, которая возвращается в ранее обнаруженное состояние со своей головкой чтения / записи в той же ячейке той же самой ленты, будет зациклена. Такая машина не останавливается. Может ли кто-нибудь привести пример никогда не останавливавшейся машины, которая не...
При рассмотрении компьютерных моделей вычислений иерархия Хомского обычно характеризуется (по порядку) конечными автоматами, автоматами со спуском, линейными связанными автоматами и машинами Тьюринга. Для первого и последнего уровней 1 (обычные языки и рекурсивно перечислимые языки) не имеет...
Недавно я услышал интересную аналогию, которая гласит, что доказательство Тьюринга неразрешимости проблемы остановки очень похоже на парадокс Рассела. Поэтому мне стало интересно: математикам в конечном итоге удалось согласовать теорию множеств, перейдя от наивной формулировки поля Кантора к более...
Рассмотрим проблемы решения, изложенные на каком-то «разумном» формальном языке Скажем, формулы в арифметике Пеано высшего порядка с одной свободной переменной в качестве системы отсчета, но я в равной степени заинтересован и в других моделях вычислений: диофантовых уравнениях, словесных задачах...
Я знаю, что такое вычисления в некотором расплывчатом смысле (это то, что делают компьютеры), но я бы хотел более строгое определение. Dictionary.comОпределения вычислений, вычислений, вычислений и вычислений являются круговыми, поэтому это не помогает. Wikipediaопределяет вычисление как «любой тип...
Есть много способов определить сложность Колмогорова , и обычно все эти определения они эквивалентны с точностью до аддитивной постоянной. То есть, если K1K1K_1 и K2K2K_2 являются функциями сложности Колмогорова (определяемыми через разные языки или модели), то существует постоянная ccc такая, что...
В книге Эндрю У. Аппеля « Реализация современного компилятора в ML» он говорит в главе 17, что теория вычислимости показывает, что всегда можно изобрести новые оптимизирующие преобразования, и продолжает доказывать, что полностью оптимизирующий компилятор решит проблему остановки: Программа Q,...
Пусть . Мне нужно решить, является ли F разрешимым или рекурсивно перечислимым. Я думаю, что это можно решить, но я не знаю, как это доказать.F= { ⟨ М⟩ : M - это ТМ, который останавливается для каждого входа максимум за 50 шагов }F={⟨M⟩:M is a TM which stops for every input in at most 50 steps}F =...
Я аспирант, изучающий курс теории вычислений, и у меня возникли серьезные проблемы с созданием контента, как только меня об этом попросят. Я могу следовать учебнику (Введение в теорию вычислений Майкла Сипсера) и лекциям; однако когда меня просят что-то доказать или придумать формальное описание...
Требуется ли, чтобы NP-трудная задача была вычислимой? Я так не думаю, но я не
Я прочитал страницу Википедии для правила 110 в клеточных автоматах, и я более или менее знаю, как они работают (набор правил решает, где рисовать следующие 1 или 0). Я только что прочитал, что они завершены по Тьюрингу, но я даже не могу понять, как бы вы «запрограммировали» «правило 110»?...
Является ли машина Тьюринга без возможности записи на пустые ячейки менее мощной, чем стандартная Тьюринг? Я думаю, что ответ - да, но я не могу найти вычисление, которое может сделать стандартная машина Тьюринга, но эта машина не может. Есть...
Как проверить, возвращают ли два алгоритма (скажем, сортировка слиянием и наивная сортировка) один и тот же результат для любого входа, когда набор всех входов бесконечен? Обновление: Спасибо, Бен, за описание того, как это невозможно сделать алгоритмически в общем случае. Ответ Дейва - это краткое...
Установка: регулярные выражения с обратными ссылками одинарный язык (1-символьный алфавит) В этом параметре разрешима следующая проблема: Если задано регулярное выражение с обратными ссылками, определяет ли оно регулярный язык? Например, (aa+)\1определяет обычный язык, а (aa+)\1+не -. Можем ли мы...
Проблема остановки не может быть решена в общем случае. Можно придумать определенные правила, которые ограничивают разрешенные входы, и можно ли решить проблему остановки для этого особого случая? Например, кажется вероятным, что язык, который не допускает циклы, например, будет очень легко...
Существует ли вычислимая функция такая, что:f:N→Qf:N→Qf:\mathbb{N}\rightarrow \mathbb{Q} Для всехt∈N:0≤f(t)<Xt∈N:0≤f(t)<Xt\in\mathbb{N}: 0\le f(t) < X limt→∞f(t)=Xlimt→∞f(t)=X\lim\limits_{t\rightarrow\infty} f(t) = X Где - неисчислимое действительное число.XXX Единственная ссылка на этот...
Память используется для многих вещей, как я понимаю. Он служит дисковым кешем и содержит инструкции программ, их стек и кучу. Вот мысленный эксперимент. Если кто-то не заботится о скорости и времени, которые требуются компьютеру для выполнения хруста, то какой минимальный объем памяти можно иметь,...
Набор Мандельброта - прекрасное существо в математике. Существует множество красивых изображений этого набора, созданных с высокой точностью, поэтому, очевидно, этот набор в некотором смысле «вычислим». Однако меня беспокоит тот факт, что он даже не рекурсивно перечислим - просто потому, что...
Какие операции необходимо выполнить, чтобы выполнить произвольные аналоговые вычисления ? Достаточно ли будет сложение, вычитание, умножение и деление? Кроме того, кто-нибудь знает точно, какие проблемы можно решить с помощью аналоговых вычислений, но не с...
Существует ли машина Тьюринга, которая останавливается на всех входах, но это свойство не доказуемо по какой-то причине? Мне интересно, если этот вопрос был изучен. Обратите внимание, что «недоказуемое» может означать «ограниченную» систему доказательств (которая в слабом смысле думает, что ответ...