Universalidade de $ (+, \ Oplus) $ sobre $ \ mathbb {z} _2 ^ n $

Question

Deixe $ \ mathbb {z} _2 ^ n $ ser o campo de bitvectors de comprimento $ n $ e definir o operador XOR $ \ OPLUS $ e o operador de adição $ + $ sobre este campo, com $ + $ ter a semântica de transbordamento usual (adição de adição módulo $ 2 ^ n $ ).

É possível expressar qualquer mapeamento $ f: \ mathbb {z} _2 ^ n \ righttarrow \ mathbb {z} _2 ^ n $ inteiramente em termos de $ \ OPLUS $ e $ + $ ? Parece que pode ser possível devido à não-linearidade da $ + $ .

---

.

Por exemplo, se fomos dados $ n= 2 $ e que $ f (0)= 3, f (1)= 1, f (2)= 3, f (3)= 1 $ , então poderíamos construir $ F $ como $ f (x)= x \ OPLUS (x + 3) $ .

Answer 1

Não.Por exemplo, você não pode expressar a função $ f (x)= x >> 1 $ .Em geral, o bit menos significativo de $ F (x) $ depende apenas do bit menos significativo da $ x$ .Você pode provar que, por indução estrutural, usando as duas seguintes propriedades: $ (A \ OPLUS B) \ BMOD 2= (A \ BMOD 2) \ OPLUS (BMOD 2) $ e $ (A + B) \ BMOD 2= (A \ BMOD 2) + (BMOD 2) \ BMOD 2 $ .