Булевы функции Тьюринга завершены

9

Булева функция - это функция .е:{0,1}N{0,1}

Известно, что логический базис является полным по Тьюрингу, поскольку он позволяет переворачивать любую последовательность или оставлять ее без изменений. То же самое можно сказать о воротах .(,)s{0,1}ИксОр

В этом смысле мы можем начать с начальной конфигурации машины такой что и ее с последовательными значениями :бзнак равно(б1,...,бN)бя{0,1}ИксОрvя

бv1v2v3...

Каждое состояние будет представлять перестановку некоторого элемента в . Этот процесс эффективно имитирует машину Тьюринга и предполагает наличие некоторого генератора значений .vябvя

Можно ли сказать, что булевы функции Тьюринга завершены?

user13675
источник
1
Как этот механизм мог застрять в бесконечной петле?
Гильденстерн
Я предполагаю, что дело в том, что, хотя формализм булевой схемы изоморфен формализму Тьюринга, он не говорит вам, как создать или сгенерировать такую ​​программу ... Вам просто необходимо "знать" значения .. .vя
user13675

Ответы:

8

Неформально язык (программирования) является тьюринговым, если каждая вычислимая функция имеет представление. Общая вычислимая функция принимает ввод произвольного размера. Булевы функции, с другой стороны, принимают ввод фиксированного размера. Следовательно, булевы функции даже не считаются потенциально полными по Тьюрингу.

Соответствующее понятие полноты здесь является полной основой связок. Набор связок ( -арные функции на булевых значениях для произвольного k ) является полным, если каждая булева функция на x 1 , , x n (для произвольного n 1 ) может быть представлена ​​с помощью связок. Следующие множества являются полными: базис де Моргана { ¬ , , } и базис { ¬ , } . В отличие от { ¬ , }ККИкс1,...,ИксNN1{¬,,}{¬,}{¬,} не является полным: он может выражать только линейные функции.

Юваль Фильмус
источник
Будет ли их аналог, булевы схемы, завершен по Тьюрингу? Я предполагаю, что это так, как Кук (в своем доказательстве NP-полноты 3SAT) показал, как машины Тьюринга и логические схемы эквивалентны?
user13675
@ user13675 Нет, это точно такая же проблема. Каждая остановка машины Тьюринга может быть преобразована в эквивалентную логическую схему или формулу для каждого размера ввода, но для каждого размера вам понадобится другой.
Юваль Фильмус
5

строго говоря, как ответил YF, конечные цепи не могут быть полными по Тьюрингу.

Тем не менее, стоит упомянуть лидерство в ответ на этот вопрос (и, возможно, то, что вы ищете) - тесно связанную концепцию, довольно широко используемую в теории, где схемы используются для вычисления функций таким образом, который сильнее, чем полный Тьюринга.

NСN

ВЗН
источник