What's The Mapping Reduction Function
<p>This is (I think) easy problem from Complexity Theory. </p>

<pre><code>#Consider the language E over the binary alphabet
#consisting of strings representing even non-negative
#integers (with leading zeros allowed).  
#I.e. E = {x | x[-1] == '0'}.
#
#Reduce E to the language {'Even'} by implementing
#the function R
def R(x):
    #Code


def main():
    #test cases
    assert(R('10010') in ['Even'])
    assert(R('110011') not in ['Even'])

if __name__ == '__main__':
    main()
</code></pre>

<p>According to Mapping Reduction def:<br>
"Language A is mapping reducible to language B, written A â¤ mB,
if there is a computable function f : Î£ â ââÎ£ â , where for every w,
w â A ââ f (w) â B.
The function f is called the reduction from A to B."<br>
A computable mapping function would be f(n) = 2n (or x &lt;&lt; y in Python), but in that case, those assertions doesn't make sense, because every R(x) should be in {'Even'}...?</p>

<p>So basically you have <code>E</code> as the binary representations of integers, even numbers only. This is indicated by the last digit (integer 1) being <code>0</code>. All other digits represent multiples of 2 and therefore do not matter.</p>

<p>The target "language" consists just of the string <code>"Even"</code>. That is, every even number must map to the word <code>"Even"</code>.</p>

<p>So the assignment is practically: if <code>x</code> represents an even binary number, return <code>"Even"</code>, otherwise return something else.</p>

<p>The most straightforward way is to check the definition of an even binary number:</p>

<pre><code>def R(x):  # shortest/fastest option
    return 'Even' if x[-1] == 0 else ''

def Rdocs(x):
    """
    Map any of {x | x[-1] == '0'} to {'Even'}

    Uses the definition {x | x[-1] == '0'}
    """
    if x[-1] == '0':  # check that x satisfies definition of even binary
        return 'Even'
    return ''
</code></pre>

<p>One can also do this with an explicit mapping:</p>

<pre><code>translate = {'0': 'Even', '1': ''}
def Rmap(x, default=''):
    """
    Map any of {x | x[-1] == '0'} to {'Even'}

    Uses a literal mapping of x[-1]
    """
    return translate[x[-1]]
</code></pre>

<p>Alternatively, you can convert the binary to a number. Python's <code>int</code> type also takes binary literals:</p>

<pre><code>def Rbin(x):
    """
    Map any of {x | x[-1] == '0'} to {'Even'}

    Uses python builtin to evaluate binary
    """
    return '' if int(x, 2) % 2 else 'Even'
</code></pre>

<p>I guess technically speaking, <code>R(x)</code> should be <strong>only</strong> defined for every <code>x</code> in <code>{x | x[-1] == '0'}</code>, unless you assume the empty word is implicitly contained in every language. Your unit tests suggest it must return something, however. You may want to return <code>'Odd'</code> or <code>None</code> instead of the empty word.</p>

python complexity-theory turing-machines