Сокращение таблицы истинности

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

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

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

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

Поскольку каждая редукция таблицы истинности является редукцией по Тьюрингу, если A сводится по таблице истинности к B ( A ≤ _tt B ), то A также сводится по Тьюрингу к B ( A ≤ _T 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}

,

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

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

использованная литература

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

Эта статья по математической логике - незавершенная . Вы можете помочь Википедии, расширив ее .