Truth table reduction

I'm finding out algorithm concept and also the educator asked an inquiry that perplexes me.

Do $A$ and also $B$ exist such that $A$ is not to $B$, yet $B$ is fact - table reducible to $A$?

2022-07-25 20:42:49
Source Share
Answers: 1

Following Brian M. Scott's hint I post this as an answer.

The question is probably just an exercise in thinking about the definition.

Take $A$ an undecidable language on an alphabet with $n$ elements (assume it does not contain $\epsilon$ the empty word), or the corresponding subset of $\mathbb N$ by interpreting words as $n$-ary expansions. $A$ may be formulas provable with Peano's axioms for arithmetic. In this case Gödel numbering of formulas gives a second way of viewing $A$ as a set of natural numbers. Gödel and Turing proved $A$ is not decidable: there is no Turing machine that stops for all input (word in the alphabet $A$ is encoded in) with the right answer, 1 if the input is in $A$ and 0 if not. (Remark: The language is recursively enumerable so there is a TM which accepts all and only words in $A$, but then it will not stop on some input -which therefore is not in $A$, but this machine will not tell.)

Take $B$ a decidable language, for instance all nonempty words, or the empty set.

Now $B$ truth-table-reduces to $A$ simply outputing the easily-computed (without calling on the oracle) answer, i.e. always accepting in the first example of $B$ above. But $A$ does not so reduce to $B$ because truth-table calls to computable oracles can be implemented as Turing machines, by adding the TM working to output oracle answers for $B$ and the truth-table call procedure, to a putative TM deciding $A$ with $B$ as oracle. This would give a TM deciding $A$, and we know this is impossible.

2022-07-25 22:33:05