Both sets A and B are encoding of some problems in Turing machines' alphabets. For example, the first problem can be SAT and the second problem can be HAMILTONIAN CYCLE. Then A consists of encodings of satisfiable Boolean formulas and B consists of encodings of graphs with Hamiltonian cycles. In this example, a reduction is just some function from words to words, but it is supposed to map words from A, and only them, to words from B.Suppose A and B are formal languages over the alphabets Σ and Γ, respectively. A many-one reduction from A to B is a total computable function f : Σ* → Γ* that has the property that each word w is in A if and only if f(w) is in B (that is, ).