Две статьи, которые я бы включил: Д. Козен, "Индексация субрекурсивных классов" , STOC, 1978. Р. Лэднер, "О структуре полиномиальной временной сводимости" , JACM, 1975....
Насколько я понимаю, доказательство того, что P = NP или P ≠ NP, должно быть нерелятивизируемым (как в оракулах теории рекурсии). Практически все доказательства кажутся релятивизируемыми. Какие хорошие примеры , не являющиеся Релятивизуемых доказательств, из тех , что Р = NP / P ≠ NP доказательству...
Обычный способ доказать неразрешимость состоит в том, чтобы свести к минимуму RE-полную задачу, такую как проблема остановки, правильность в логике первого порядка, выполнимость диофантовых уравнений и т. Д. Известно, что существуют рекурсивно перечисляемые, но неразрешимые проблемы, которые не...
Можно ли создать единственную (не полную по Тьюрингу) механическую реализацию, скажем, Microsoft Word? Можно ли реализовать такие вещи, как итераторы, функции первого порядка, весь спектр методов программирования? Могут ли шестерни и другие механические части представлять структуры данных или даже...
HT(n)HT(n)HT(n)NnnB B ( n ) = макс. HT( н )BB(n)=maxHT(n)BB(n) = \max HT(n) Что мы можем сказать о втором по величине числе в ? Назовите это .B B 2 ( n )ЧАСT( н )HT(n)HT(n)B B2( н )BB2(n)BB_2(n) B B ( n ) B B ( n ) - B B 2 ( n )B B2( н )ВВ2(N)BB_2(n) тривиально не вычислим, так как он позволяет...
Хорошо известно, что проблема остановки является неисчислимой. Тем не менее, можно экспоненциально «сжать» информацию о проблеме остановки, так что ее распаковка является вычислимой. Точнее, можно вычислить из описания машин Тьюринга и n- битного состояния рекомендации ответ на проблему остановки...
Это, вероятно, довольно просто, но рассмотрим стандартную проблему почтовой корреспонденции: Учитывая и , найдите последовательность индексов такую, что . Это, конечно, неразрешимо.β 1 , … , β N i 1 , … , i K α i 1 ⋯ α i K = β i 1 ⋯ β i Kα1,…,αNα1,…,αN\alpha_1, \ldots,...
Я пытался обернуть голову вокруг того, что, почему и как вычислить, но я не могу понять, «почему это работает»?λλ\lambda «Интуитивно» я получаю модель вычислимости машин Тьюринга (ТМ). Но эта абстракция просто оставляет меня в замешательстве.λλ\lambda Давайте предположим, что ТМ не существуют -...
Какова простейшая вычислительная модель, для которой проблема пустоты неразрешима? Проблема пустотности для вычислительной модели (например, автомат конечного состояния, автомат с переменным нажатием, квантовый автомат с ограниченной ошибкой со счетчиком, детерминированный LBA и т. Д.) Состоит в...
Мы можем думать о колмогоровской сложности строки xxx как о длине самой короткой программы PPP и вводим , что . Обычно эти программы взяты из некоторого полного набора Тьюринга (например, может быть описанием машины Тьюринга, или это может быть программа на LISP или C). Даже когда мы смотрим на...
Бумага Лаури Хелла и Хосе Мария Turull-Torres, Вычисление запросов с помощью логики высшего порядка , TCS 355 197–214, 2006. doi: 10.1016 / j.tcs.2006.01.009 предлагает логику VO, логику переменного порядка. Это позволяет определять количество заказов по переменным. VO довольно мощный и может...
Пусть о Л -терминов быть определены следующим образом :sizesizesizeλλ\lambda ,size(x)=1size(x)=1size(x) = 1 size(λx.t)=size(t)+1size(λx.t)=size(t)+1size(λx.t) = size(t) + 1 , size(ts)=size(t)+size(s)+1size(ts)=size(t)+size(s)+1size(t s) = size(t) + size(s) + 1 . Пусть сложность -term определяется...
Обычно проще рассуждать о исчислении, где ограничение - это конечность вычислений, а не порог, подобный «вычислимому за полиномиальное количество времени». В теории формальных языков, например, вместо использования чтобы охарактеризовать апериодический моноид, проще использовать проконечные слова,...
Существуют ли разрешимые проблемы, такие, что для любого алгоритма, который решает проблему, мы можем дать ограничение по времени как функцию длины n входного экземпляра? Я пришел к этому вопросу, потому что думал о следующем: Предположим, у нас есть рекурсивно перечислимая, но неразрешимая...
Есть ли документированный способ вычисления узлов? (окружности, вложенные в трехмерное евклидово пространство). Я имею в виду тип данных для их представления и алгоритм для определения, представляют ли два экземпляра типа один и тот же узел. Если ответ положительный, как насчет сложности этой...
Как мы знаем, определение вычислительной сложности алгоритма практически не вызывает противоречий, но определение вычислительной сложности вещественных чисел или моделей вычислений над действительными значениями не в таком случае. Мы знаем модель и модель Блюма и Смалеса в книге «Вычислительный...
Следующая проблема разрешима: Имеет ли контекстная грамматика , ?GGGL(G)=∅L(G)=∅L(G) = \varnothing Следующая проблема неразрешима: Имеет ли контекстно-свободная грамматика GGG , L(G)=A∗L(G)=A∗L(G) = A^{\ast} ? Существует ли характеристика контекстно-свободных языков MMM с разрешимым равенством...
Можно ли построить алгоритм, который принимает в качестве входных данных автомат сокращения вместе с обещанием, что язык, принятый этим автоматом является детерминированным контекстно-свободным языком и выводит детерминированный автомат нажатия который принимает именно принятый язык на ?MMMЛ (...
Я знаю, что вопрос «имеет ли формула первого порядка модель» вообще неразрешим.φϕ\phi Может ли кто-нибудь дать мне ссылку или книгу, которая даст ответ для конечных моделей. Если у меня есть формула первого порядка , можно ли имеет ли конечную модель? Я почти уверен, что вопрос хорошо известен, но...
Игра «Назови наибольшее число» просит двух игроков тайно записать число, и победителем становится тот, кто записал большее число. Игра обычно позволяет игрокам записывать функции, оцененные в определенный момент, поэтому 222222222^{2^{2^{2}}} также было бы приемлемо записать. Значение функции Busy...