摘要
本文证明了对任意整数k,至少存在一个语言能被k带实时图灵机接受,但不能被(k—1)带实时图灵机所接受,从而证明了k带图灵机计算能力严格强于(k-1)带实时图灵机。
We show that for any integer K,there is at least one language which is accepted by k - tape real -time Turing machine, but cannot be accepted by a (k-1)- type real - time Turing machine. Therefore, we show the computing capability of k - tape Turing machine is higher than that of (k - 1) type Turing machine.
出处
《计算机与数字工程》
2000年第1期14-16,共3页
Computer & Digital Engineering
基金
湖北省自然科学基金(98J076)
关键词
图灵机
实时图灵机
实时计算
K带
Turing machine, Real - Time Turing Machine,Real - Time computing
