Булева функция - это функция .
Известно, что логический базис является полным по Тьюрингу, поскольку он позволяет переворачивать любую последовательность или оставлять ее без изменений. То же самое можно сказать о воротах .
В этом смысле мы можем начать с начальной конфигурации машины такой что и ее с последовательными значениями :
Каждое состояние будет представлять перестановку некоторого элемента в . Этот процесс эффективно имитирует машину Тьюринга и предполагает наличие некоторого генератора значений .
Можно ли сказать, что булевы функции Тьюринга завершены?
Ответы:
Неформально язык (программирования) является тьюринговым, если каждая вычислимая функция имеет представление. Общая вычислимая функция принимает ввод произвольного размера. Булевы функции, с другой стороны, принимают ввод фиксированного размера. Следовательно, булевы функции даже не считаются потенциально полными по Тьюрингу.
Соответствующее понятие полноты здесь является полной основой связок. Набор связок ( -арные функции на булевых значениях для произвольного k ) является полным, если каждая булева функция на x 1 , … , x n (для произвольного n ≥ 1 ) может быть представлена с помощью связок. Следующие множества являются полными: базис де Моргана { ¬ , ∨ , ∧ } и базис { ¬ , ⇒ } . В отличие от { ¬ , ⊕ }К К Икс1, … , ХN n ≥ 1 { ¬ , ∨ , ∧ } { ¬ , ⇒ } { ¬ , ⊕ } не является полным: он может выражать только линейные функции.
источник
строго говоря, как ответил YF, конечные цепи не могут быть полными по Тьюрингу.
Тем не менее, стоит упомянуть лидерство в ответ на этот вопрос (и, возможно, то, что вы ищете) - тесно связанную концепцию, довольно широко используемую в теории, где схемы используются для вычисления функций таким образом, который сильнее, чем полный Тьюринга.
источник