Функциональное завершение означает завершение по Тьюрингу?

Я заметил, что И, ИЛИ, НЕ эти три логических элемента являются функционально завершенными, это означает, что я могу представить любую таблицу истин только этими тремя элементами.

Итак, я хочу знать, могу ли я представить какую-либо вычислимую функцию только с помощью этих трех вентилей?


comment
Связанный: stackoverflow.com/questions/4908893/   -  person Thilo    schedule 31.10.2016
comment
Я видел этот вопрос, прежде чем задать это, но все же я плохо понимаю. Машина Тьюринга может останавливаться или нет на определенном входе, но комбинационная (не последовательная) логическая схема всегда дает выход на конкретном входе. Вы можете не согласиться с моей точкой зрения на комбинационную схему, но комбинационная схема — это просто детерминированная система, поэтому я могу шаг за шагом оценивать входные данные, пока они не дадут результат, другими словами, я думаю, что в комбинационной схеме нет петель. . В любом случае, спасибо!   -  person Yachao Zhu    schedule 31.10.2016
comment
Я голосую за то, чтобы закрыть этот вопрос как не по теме, потому что он принадлежит cs.stackexchange.com, но будет закрыт там как тривиальный дубликат.   -  person Joshua    schedule 31.10.2016
comment
FWIW: Ответ на вопрос «Я хочу знать, могу ли я представить какую-либо вычислимую функцию только с помощью этих трех ворот» — «Нет». Таблицы истинности не могут представлять частичные функции и, следовательно, не являются полными по Тьюрингу (поскольку TC эквивалентен частично рекурсивным функциям). Они даже не являются примитивно-рекурсивными, поскольку S (преемник) не может быть представлен конечным числом битов. IIRC они должны быть такими же мощными, как DFA.   -  person Margaret Bloom    schedule 04.11.2016