Сокращение таблицы истинности - Truth-table reduction

В теория вычислимости, а редукция таблицы истинности это снижение из одного набора натуральные числа другому. Как «инструмент» он слабее, чем Редукция Тьюринга, поскольку не каждое сокращение по Тьюрингу между наборами может быть выполнено с помощью редукции таблицы истинности, но каждое сокращение таблицы истинности может быть выполнено с помощью редукции Тьюринга. По той же причине говорят, что это более сильная сводимость, чем сводимость по Тьюрингу, поскольку она подразумевает сводимость по Тьюрингу. А слабая редукция таблицы истинности представляет собой родственный тип редукции, названный так потому, что он ослабляет ограничения, наложенные на редукцию по таблице истинности, и обеспечивает более слабую классификацию эквивалентности; как таковая, «слабая редукция таблицы истинности» может быть на самом деле более мощной, чем редукция таблицы истинности как «инструмент», и выполнять редукцию, которую невозможно выполнить с помощью таблицы истинности.

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

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

Характеристики

Поскольку любая редукция таблицы истинности является редукцией Тьюринга, если А сводится ли таблица истинности к B (А ≤_тт B), тогда А также сводится по Тьюрингу к B (А ≤_Т B). Принимая во внимание также сводимость один-один, сводимость много-одного и слабую сводимость таблицы истинности,

${\displaystyle A\leq _{1}B\Rightarrow A\leq _{m}B\Rightarrow A\leq _{tt}B\Rightarrow A\leq _{wtt}B\Rightarrow A\leq _{T}B}$,

или, другими словами, сводимость по принципу «один-один» подразумевает сводимость по принципу «один-один», что подразумевает сводимость по таблице истинности, что, в свою очередь, подразумевает слабую сводимость по таблице истинности, что, в свою очередь, подразумевает сводимость по Тьюрингу.

Более того, А сводится ли таблица истинности к B если только А сводится ли Тьюринг к B через тотал функционал на ${\displaystyle 2^{\omega }}$. Прямое направление тривиально, а для обратного предположим ${\displaystyle \Gamma }$ - тотально вычислимый функционал. Чтобы построить таблицу истинности для вычислений А (п) просто найдите номер м так что для всех двоичных строк ${\displaystyle \sigma }$ длины м ${\displaystyle \Gamma ^{\sigma }(n)}$ сходится. Такой м должен существовать Лемма Кёнига поскольку ${\displaystyle \Gamma }$ должно быть полным на всех путях через ${\displaystyle 2^{<\omega }}$. Учитывая такой м найти уникальную таблицу истинности, которая дает ${\displaystyle \Gamma ^{\sigma }(n)}$ когда применяется к ${\displaystyle \sigma }$. Прямое направление не обеспечивает слабой сводимости таблицы истинности.

Рекомендации

• Х. Роджерс мл., 1967. Теория рекурсивных функций и эффективной вычислимости, второе издание 1987 г., MIT Press. ISBN  0-262-68052-1 (мягкая обложка), ISBN  0-07-053522-1