n输入single output automaton数量为$2^{(2n)}$的推导方法咨询

嘿，我来帮你梳理这个问题～首先大概率是你在输入LaTeX的时候笔误啦，冯·诺依曼在那篇讲义里给出的正确数量应该是$2^{2n}$，而不是$2^{{2n}$。不过没关系，我先给你推导正确的数量逻辑，再顺便说说如果是$2}{2n}$的话对应的是什么场景。

核心推导（对应$2^{2n}$的正确情况） #

要理解这个数量，得先从单输出自动机的定义入手：

• 这类自动机是组合逻辑自动机（没有内部状态，输出完全由当前输入决定），有$n$个二进制输入（每个输入只能是0或1），1个二进制输出（0或1）。
• 首先计算所有可能的输入组合：$n$个二进制输入，每个输入有2种选择，所以总共有$2^{n$种不同的输入状态（比如n=2时，输入组合是(0,0),(0,1),(1,0),(1,1)，共4种，也就是$2}2=4$）。
• 对于每一种输入组合，输出都可以独立选择0或1——也就是说，每个输入状态到输出的映射都是自由的，没有约束。
• 那总共有多少种不同的映射方式呢？每个输入状态有2种输出选择，一共$2^{n$个输入状态，所以总数量就是$2$乘以自己$2}n$次，也就是$2^{2n}$。

举个小例子验证：

• 当n=1时，输入组合有2种（0和1），每个对应2种输出，总共有$2^2=4$种自动机：恒输出0、恒输出1、输入等于输出（缓冲器）、输入取反（非门），完全符合数量。
• 当n=2时，输入组合有4种，总自动机数量是$2^4=16$，这也和2输入布尔函数的总数一致。

如果确实是$2^{2n}$的情况？ #

如果冯·诺依曼这里真的写的是$2^{2n}$，那对应的应该是另一类受限的自动机场景：

• 比如自动机的输出是每个输入的独立二元选择的组合，但这种情况更接近“n个独立开关控制输出”，但严格来说不符合单输出自动机的常规定义；
• 或者是输入并非二进制，每个输入有4种状态，此时n个输入的组合数是$4ⁿ⁼²{2n}$，但这和讲义里的定义描述不匹配。

所以几乎可以肯定是笔误，正确的数量推导逻辑就是上面说的“每个输入组合独立映射到输出，总映射数是2的输入组合数次方”。

备注：内容来源于stack exchange，提问作者Usman Nizami