For

C, D \subseteq B

, one writes

C \leq_{m} D

if there is a total computable function

f : B \to B

such that

x \in C ⟺ f (x) \in D

for every

x

. This is a computable many-one reduction.

ii

Solution

One writes

C \equiv_{m} D

when both

C \leq_{m} D

and

D \leq_{m} C

Fix an effective coding of machines and write

W_{w}

w

I

of codes is an index set when membership depends only on the recognized language:

W_{u} = W_{v} ⟹ (u \in I ⟺ v \in I) .

It is nontrivial when it is neither empty nor all of

B

There are no discussions about this article yet.

There are currently no matching articles.