给定任意TM的编码<TM>与输入w,构造这样一台TM,假如命名为 One-More-State,它干这样的工作:做与(<TM>, w)相同的工作,但是,增加多一个无效的状态。可以这样想象:One-More-State 在输入(<TM>, w)之后发了一会儿呆,或者循环了一阵子,或者延时了一秒,然后模拟(<TM>, w)的所有工作。
相信,构造One-More-State 是容易的,且不需要无限的纸带,也许只需要使用足以模拟(<TM>, w)所需要的存储即可。如果构造出来了,One-More-State 的编码也是容易的,比如就记为<One-More-State > 。
我的问题是,One-More-State 以(<One-More-State >, (<TM>, w))为输入可以吗?如果可以,One-More-State 会停机吗?One-More-State在这种输入下的运行的状态会是有限的吗?