什么是映射缩减函数

Question

这是（我认为）复杂性理论中的简单问题。

#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()

根据映射缩减 def:
“语言 A 是可还原为语言 B 的映射，写为 A ≤ mB，如果存在可计算函数 f : Σ ∗ −→Σ ∗ ，其中对于每个 w， w ∈ A ⇐⇒ f (w) ∈ B。函数 f 称为从 A 到 B 的归约。"
一个可计算的映射函数是 f(n) = 2n（或 Python 中的 x << y），但在那种情况下，这些断言没有意义，因为每个 R(x) 都应该在 {'Even'}...?

Answer 1

所以基本上你有 E 作为整数的二进制表示，只有偶数。这由最后一位数字（整数 1）表示为 0。所有其他数字代表 2 的倍数，因此无关紧要。

目标 "language" 仅包含字符串 "Even"。也就是说，每个偶数都必须映射到单词 "Even".

所以赋值实际上是：如果 x 表示二进制偶数，则 return "Even"，否则 return 其他。

最直接的方法是查看偶数二进制数的定义：

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 ''

也可以使用显式映射来做到这一点：

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]]

或者，您可以将二进制转换为数字。 Python 的 int 类型也采用二进制文字：

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'

我想从技术上讲，R(x) 应该 只为 {x | x[-1] == '0'} 中的每个 x 定义 ，除非你假设空词是隐含在每一种语言中。但是，您的单元测试表明它必须 return 某些东西。您可能希望 return 'Odd' 或 None 而不是空词。

什么是映射缩减函数

What's The Mapping Reduction Function

python

complexity-theory

turing-machines