Question

有一台Mini计算机，内存大小为1K，CPU主频为1M（CPU状态每秒改变10的6次方次），问在这台计算机上可运行

并且确定可以终止的程序的最长运行时间是多少？
给出思路及推理过程

Answer 1

首先程序是确定性的，就说明内存的状态不会重复，否则就永远结束不了(重复指： 比如说内存原来是 10101010101010 如果你的程序运行了一会，内存又成为 10101010101010 的话，那么你的程序肯定不会正常结束的，因为计算机的状态又回到原点了)。从这一点出发，可以知道内存的状态共有 2^8k , 然后CPU每秒改变 2^20 个状态，所以这台计算机最长出现不重复的状态2^(8k-20）秒。