构造竞赛游戏

---

hzx：任意给定计算机，我可以构造等价的DFA。
斌头：好，我给一台计算机给你，存储空间8bits，每个bit有两种状态，你要构造有多少个状态的DFA？
hzx：我只需要最多$2^8$个状态。
斌头：那我这台计算机刚好有$2^8 + 1$个状态，你看，这机器长这个模样。
hzx：那我就构造$2^8+1$个状态的DFA。
斌头：不好意思，数错了，是$2^8+2$个状态...
hzx：没关系，你有多少状态我就构造多少个状态出来给你。
斌头：数不清怎么办？
hzx：没关系，总归是有限状态，不然你叫什么有限状态图灵机？

请问，最后谁会赢得这次构造游戏？

我相信我会赢。因为确实，计算机的状态没人数得出来，否则就不会存在“停机问题”了。

给定计算机，不会数不过来的

@hzx__ How？

@bintou

计算机的行为由当前状态决定——下一步要执行什么代码，取决于正在被执行的代码段，以及ip寄存器的值，如果text段的内容相同，cs:ip寄存器的相同，指令使用的值也相同，那么下一步的行为就是确定的

老师同意以上这句话吗

@hzx__
一个算法，给定输入，输出固定。不用说得那么复杂。

同意。所以呢？

@bintou

输入字符表是$\{0,1\}$ ，将所有计算机接受的输入全部编码成bit 串后读入计算机，每次读一个0或者一个1。

我们能不能把计算机输出输入的过程归约为以上过程呢